[工学]51二叉树的概念.ppt

二叉树的基本术语 叶子(leaf) ：度为0的结点，也称为终端结点。 分支结点：度不为0的结点，也称为非终端结点或内部结点。 二叉树的基本术语 完全二叉树(Complete Binary Tree) 完全二叉树的建立过程中，第一个节点必然是根节点 完全二叉树(Complete Binary Tree) The second node of a complete binary tree is always the left child of the root... 完全二叉树(Complete Binary Tree) The second node of a complete binary tree is always the left child of the root... ... and the third node is always the right child of the root. 完全二叉树(Complete Binary Tree) The next nodes must always fill the next level from left to right. 完全二叉树(Complete Binary Tree) 完全二叉树(Complete Binary Tree) 完全二叉树(Complete Binary Tree) 完全二叉树(Complete Binary Tree) 完全二叉树(Complete Binary Tree) Is This Complete? Is This Complete? 二叉树的主要性质 性质4. 满二叉树定理：非空满二叉树树叶数目等于其分支结点数加1。 证明：满二叉树定理由性质3可直接推出。 性质5. 满二叉树定理推论：一个非空二叉树的空子树数目等于其结点数加1。 证明：设二叉树为T，将其所有空子树换为树叶，记新扩充满二叉树为T’。所有原来T的结点现在是T’的分支结点。根据满二叉树定理，新添加的树叶数目等于T结点个数加1。而每个新添加的树叶对应于T的一个空子树。因此T中空子树数目等于T中的结点个数加1 二叉树的主要性质 性质2. 深度为k的二叉树至多有 2k+1-1个结点（k≥0）。其中深度(depth)定义为二叉树中层数最大的叶结点的层数。 证明：由性质1可知，第i层的最大结点数为2i，所以 二叉树的主要性质 性质3. 任何一棵二叉树，若其终端结点数为n0 ，度为2的结点数为n2，则n0=n2+1 。 证明：设n1为二叉树中度为1 的结点数。该二叉树的结点总数n为度分别为0，1，2的结点数之和，即 n=n0+n1+n2 （公式5.1） 除根结点外，其余结点都有一条边进入，设边数为e，有n = e + 1。由于这些边是由度为1或2的的结点发出的，所以又有e=n1+2n2，于是得 n=e+1=n1+2n2+1 （公式5.2） 由公式5.1和5.2得 n0+n1+n2=n1+2n2+1， 即 n0=n2+1 二叉树的主要性质 性质6. 有n个结点（n0）的完全二叉树的高度为[log2 (n+1)]（深度为[log2 (n+1)] - 1）。 其中二叉树的高度(height)定义为二叉树中层数最大的叶结点的层数加1。 证明：假设高度为h，则根据性质2和完全二叉树的定义(完全二叉树忽略最下一层是一个满二叉树) ， 有 或 不等式中各项取对数，于是得到 。因为h为整数，所以h＝[log2 (n+1)]。 二叉树的主要性质 性质7. 对于具有n个结点的完全二叉树，结点按层次由左到右编号，则对任一结点i（0 ≤ i ≤ n - 1）有 （1）如果i = 0，则结点i是二叉树的根结点；若i＞0，则其父结点编号是[(i - 1)/2]。 （2）当2i + 1 ≤ n - 1时，结点i的左子结点是2i + 1，否则结点i没有左子结点。 当2i + 2 ≤ n - 1时，结点i的右子结点是2i + 2，否则结点i没有右子结点。 （3）当i为偶数且0 i n时，结点i的左兄弟是结点i - 1，否则结点i没有左兄弟。 当i为奇数且i+1 n时，结点i的右兄弟是结点i + 1，否则结点i没有右兄弟。 二叉树的主要性质 证明：这里证明(2)，(1) 和(3)即可由结论(2)推得。对于i = 0，由完全二叉树的定义，其左孩子的