算法与数据结构课件PPT第四章

第4章 树和二叉树

4.1 二叉树的基本概念

1.二叉树的基本概念

二叉树是结点的有限集合，这个集合或者为空集，或者为一个称

为根和两棵不相交的左子树和右子树(但无环路结构)组成的一种层次

关系的数据结构。

2.二叉树的基本术语

[1]父结点，子结点，兄弟结点，叶子结点

[2]树边，路径，结点的度，二叉树的深度

[1]满二叉树：每一层上的所有节点都有两个子节点(除最后一层的叶子结点)。

[2]完全二叉树：每一分支上的最后一层结点要么左右两边都有结点(满二叉树)或者

要么都集中在左边(可以不具有右子树)。

[3]扩充二叉树：在二叉树中出现空的子树(包括叶子)上增加空的叶子结点，使其成

为满二叉树称之为扩充二叉树。

A

D E

A

F

CB

D E

满二叉树

性质3：对任何一棵非空二叉树，如果叶结点数为n，度为2的结点数为m，则n=m+1(叶

子结点个数=度为2的结点数+1)。

性质4：具有n个结点的完全二叉树，其深度k=�log

性质5：如果有n个结点的完全二叉树按层次从0开始，则对任一结点i(0� i�n-1)有：

[1]i=0，序号结点i是根；i>0, 其双亲结点是�(i- 1)/2�。

[2]2i+1�n-1，序号为i的结点的左子女结点的序号为2i+1。

[3]2i+2�n-1，序号为i的结点的右子女结点的序号为2i+2。

性质6：在满二叉树中，叶结点的个数比分支结点的个数多1。

再访问左子树(根→左→右)

后访问右子树(根→左→右)

[2]若二叉树非空，中序遍历二叉树LDR:

先访问左子树(根→左→右)

再访问根结点(根→左→右)

后访问右子树(根→左→右)

[3]若二叉树非空，后序遍历二叉树LRD:

先访问左子树(根→左→右)

再访问右子树(根→左→右)

后访问根结点(根→左→右)

LDR遍历：C B D A E G F

LRD遍历：C D B G F E A

[1]先序次序遍历二叉树DLR

void PreOrder_Recursion(BinTree T)

{if(T=NULL)

return; /*递归调用的结束条件*/

visit(root(T)) /*访问根结点的数据域*/

preOrder_Recursion(leftChild(T)) /*先序递归遍历左子树*/

preOrder_Recursion(rightchild(T))}/*先序递归遍历右子树*/

2.二叉树深度遍历的算法