See Also Data Structures、Tree |
Binary Tree
Contents
在计算机科学中，二叉树是每个节点最多只有两个分支（即不存在分支度大于2的节点）的树结构。通常分支被称作“左子树”或“右子树”。二叉树的分支具有左右次序，不能随意颠倒。
1. Definitions
1.1. Recursive definition
为了定义一个二叉树，我们必须考虑到只有一个子树是空的可能性。为此，需要一个工件，在一些教科书中称为扩展二叉树。因此，递归地将扩展二叉树定义为
- 空集是一个扩展的二叉树
- 如果T1和T2是扩展二叉树，则用T1•T2表示，当这些子树为非空时，通过添加根r连接到左边的T1和右边的T2，从而得到扩展二叉树
1.2. 图论中的定义
二叉树是一个连通的无环图，并且每一个顶点的度不大于3。有根二叉树还要满足根节点的度不大于2。有了根节点之后，每个顶点定义了唯一的父节点，和最多2个子节点。然而，没有足够的信息来区分左节点和右节点。如果不考虑连通性，允许图中有多个连通分量，这样的结构叫做森林。
2. Types of binary trees
- 满二叉树(Full/Proper/Plane Binary Tree) 每个节点都有0或2个子节点的树。定义满二叉树的另一种方法是递归定义。
- 完全二叉树(Complete Binary Tree) 每一层，除了最后一层，都被完全填满了，最后一层的所有节点都尽可能地留在左边。
|
完全二叉树 |
满二叉树 |
总节点k |
2{h-1} <= k <= 2h -1 |
k = 2h -1 |
树高h |
h = log2k +1 |
h = log2(k+1) |
- 完美二叉树(Perfect Binary Tree) 所有内部节点都有两个子节点，所有的叶子都有相同的深度或水平。一个完美二叉树的例子是一个人在特定深度的祖先图，因为每个人都有两个亲生父母(一个母亲和一个父亲)。
3. Methods for storing binary trees
3.1. Nodes and references
在具有记录和引用的语言中，二叉树通常是由一个包含对其左子树和右子树的一些数据和引用的树节点结构来构造的。有时，它还包含对其唯一父元素的引用。如果一个节点的子节点少于两个，一些子指针可以设置为一个特殊的空值，或者设置为一个特殊的前哨节点。
在标记语言(ML)中，一个树节点通常是一种三元结构数据(3-tuple of data)：left/right child 和 "leaf" node。
3.2. Arrays
二叉树也可以以宽度优先级的方式存储为数组中的隐式数据结构，如果树是完全二叉树，这种方法不会浪费空间。
4. Common operations
4.1. Insertion
4.2. Deletion
4.3. Traversal
遍历即将树的所有结点访问且仅访问一次。按照根节点位置的不同分为前序遍历，中序遍历，后序遍历
前序遍历：根节点->左子树->右子树
中序遍历：左子树->根节点->右子树
后序遍历：左子树->右子树->根节点
4.3.1. Depth-first order
4.3.2. Breadth-first order
