See Also Data StructuresTree

Binary Tree

在计算机科学中,二叉树是每个节点最多只有两个分支(即不存在分支度大于2的节点)的树结构。通常分支被称作“左子树”或“右子树”。二叉树的分支具有左右次序,不能随意颠倒。

1. Definitions

1.1. Recursive definition

为了定义一个二叉树,我们必须考虑到只有一个子树是空的可能性。为此,需要一个工件,在一些教科书中称为扩展二叉树。因此,递归地将扩展二叉树定义为

1.2. 图论中的定义

二叉树是一个连通的无环图,并且每一个顶点的度不大于3。有根二叉树还要满足根节点的度不大于2。有了根节点之后,每个顶点定义了唯一的父节点,和最多2个子节点。然而,没有足够的信息来区分左节点和右节点。如果不考虑连通性,允许图中有多个连通分量,这样的结构叫做森林。

2. Types of binary trees

完全二叉树

满二叉树

总节点k

2{h-1} <= k <= 2h -1

k = 2h -1

树高h

h = log2k +1

h = log2(k+1)

3. Methods for storing binary trees

3.1. Nodes and references

在具有记录和引用的语言中,二叉树通常是由一个包含对其左子树和右子树的一些数据和引用的树节点结构来构造的。有时,它还包含对其唯一父元素的引用。如果一个节点的子节点少于两个,一些子指针可以设置为一个特殊的空值,或者设置为一个特殊的前哨节点。

在标记语言(ML)中,一个树节点通常是一种三元结构数据(3-tuple of data):left/right child 和 "leaf" node。

3.2. Arrays

二叉树也可以以宽度优先级的方式存储为数组中的隐式数据结构,如果树是完全二叉树,这种方法不会浪费空间。

binary-tree-in-array.svg

4. Common operations

4.1. Insertion

4.2. Deletion

4.3. Traversal

遍历即将树的所有结点访问且仅访问一次。按照根节点位置的不同分为前序遍历,中序遍历,后序遍历

4.3.1. Depth-first order

depth-first-order.gif

4.3.2. Breadth-first order

breadth-first-order.gif

5. Reference


CategoryDataStructure

MainWiki: Binary_Tree (last edited 2009-10-27 12:40:05 by twotwo)