树与二叉树复习进程

1、树（非线性数据结构树（非线性数据结构(sh j ji u)）第一页，共26页。第二页，共26页。 A A C C G G T T2 2 B B E E L L K KT T1 1 F FD D H H I I T T3 3J J M M现实世界中，能用树的结构表示的例子：现实世界中，能用树的结构表示的例子：学校的行政关系、书的层次结构、人类的家族学校的行政关系、书的层次结构、人类的家族(jiz)(jiz)血缘血缘关系等。关系等。计算机软件技术中，能用树的结构表示计算机软件技术中，能用树的结构表示(biosh)(biosh)的例子：的例子：操作系统中的多级文件目录结构，高级语言中源程序的语法操作

2、系统中的多级文件目录结构，高级语言中源程序的语法结构等。结构等。第三页，共26页。有关树的基本术语有关树的基本术语: :结点（结点（NodeNode）：树中的元素，包含数据项及若干指向其子树）：树中的元素，包含数据项及若干指向其子树的分支。的分支。结点的度（结点的度（DegreeDegree）：结点拥有的子树数。）：结点拥有的子树数。结点的层次：从根结点开始算起，根为第一层结点的层次：从根结点开始算起，根为第一层. .叶子（叶子（LeafLeaf）：度为零的结点，也称端结点。）：度为零的结点，也称端结点。孩子（孩子（ChildChild）：结点子树的根称为该结点的孩子结点。）：结点子树的根称为

3、该结点的孩子结点。双亲（双亲（ParentParent）：孩子结点的上层结点，称为这些结点的双）：孩子结点的上层结点，称为这些结点的双亲。亲。兄弟兄弟(xingd)(xingd)（SiblingSibling）：同一双亲的孩子。）：同一双亲的孩子。深度（深度（Depth)Depth)： 树中结点的最大层次数。树中结点的最大层次数。森林（森林（ForestForest）：）：M M棵互不相交的树的集合。棵互不相交的树的集合。 A C G T2 B E L KT1 FD H I T3J M C G T2 B E L KT1 FD H I T3J M第四页，共26页。 树的存储结构可以采用具有多个指

4、针域的多重链表，结点中指针域树的存储结构可以采用具有多个指针域的多重链表，结点中指针域的个数应由树的度来决定的个数应由树的度来决定 但在实际应用但在实际应用(yngyng)(yngyng)中，这种存储结构并不方便，一般将树转中，这种存储结构并不方便，一般将树转化为二叉树表示，进行处理化为二叉树表示，进行处理 可以用树来表示算术表达式。可以用树来表示算术表达式。Edatapoint1point2point3ABCDFGHIJroot(a)(b)第五页，共26页。二叉树一种特殊的树型结构二叉树一种特殊的树型结构(jigu)(jigu)，特点是树中，特点是树中每个结点只有两棵子树，且子树有左右之分，

5、次序不每个结点只有两棵子树，且子树有左右之分，次序不能颠倒。能颠倒。因为树的每个结点的度不同，存储困难，使对树的处理因为树的每个结点的度不同，存储困难，使对树的处理算法很复杂。所以引出二叉树的讨论。算法很复杂。所以引出二叉树的讨论。第六页，共26页。 空二叉树空二叉树 仅有仅有根结点根结点 右子树右子树为空为空 左子树左子树为空为空左右子树左右子树均非空均非空第七页，共26页。二叉树的第二叉树的第i i层上至多有层上至多有2i-12i-1（i i1 1）个结点）个结点(ji din)(ji din)。深度为深度为m m的二叉树中至多含有的二叉树中至多含有2m-12m-1个结点个结点(ji di

6、n)(ji din)。若在任意一棵二叉树中，有若在任意一棵二叉树中，有n0n0个叶子结点个叶子结点(ji din)(ji din)，有，有n2n2个度为个度为2 2的结点的结点(ji din)(ji din)，则：，则：n0=n2+1n0=n2+1A AB BC CD DE EF F第八页，共26页。性质性质1 1：二叉树的第：二叉树的第i i层上至多有层上至多有2 i-12 i-1（i i 1 1）个结点。）个结点。证明：根据二叉树的特点，结论证明：根据二叉树的特点，结论(jiln)(jiln)是显然的。是显然的。性质性质2 2：深度为：深度为m m的二叉树中至多的二叉树中至多(zhdu)(

7、zhdu)含有含有2m-12m-1个结点。个结点。证明：深度为证明：深度为m m的二叉树最多有的二叉树最多有m m层，根据性质层，根据性质1 1，只要将第，只要将第1 1层到第层到第m m层层的最大结点数相加，就可得到整个二叉树中结点的最大值。的最大结点数相加，就可得到整个二叉树中结点的最大值。21-1+22-21-1+22-1+2m-1=2m-1 1+2m-1=2m-1 性质性质3 3：度为：度为0 0的结点总比度为的结点总比度为2 2的结点多一个的结点多一个(y )(y )。设：有设：有n0n0个叶子结点，有个叶子结点，有n1n1个度为个度为1 1的结点，有的结点，有n2n2个度为个度为2

8、 2的结点，的结点， 则二叉树中结点总数为：则二叉树中结点总数为：n=n0+n1+n2 n=n0+n1+n2 设所有进入分支的总数为设所有进入分支的总数为m,m,则总的结点个数为：则总的结点个数为：n=m+1n=m+1总的射出分支与总的进入分支数相等：总的射出分支与总的进入分支数相等：m=n1+2n2 m=n1+2n2 因此：因此： n0+n1+n2=n1+2n2+1 n0+n1+n2=n1+2n2+1 所以：所以： n0= n2+1 n0= n2+1 A AB BC CD DE EF F4 42 23 31 15 56 67 78 89 9101011111212131314141515A

9、AB BC CD DE EF FA AB BC CD DE EF F4 42 23 31 15 56 67 78 89 9101011111212131314141515用归纳法证明：用归纳法证明： i=1i=1，则结点数，则结点数=2=20 0 =1=1为根结点。为根结点。若已知若已知 i-1i-1层上结点数至多有层上结点数至多有2 2(i-1)-1(i-1)-1=2=2i-2i-2 个，由于二叉树每个个，由于二叉树每个结点度数最大为结点度数最大为2 2，因此第，因此第i i层上结点数最多为第层上结点数最多为第i-1i-1层上结点数层上结点数的的2 2倍，即倍，即2 22 2i-2i-2=2

10、=2i-1i-1。第九页，共26页。4 42 23 31 15 56 67 78 89 91010111112121313141415154 42 23 31 15 56 67 78 89 9101011111212完全完全(wnqun)(wnqun)二二叉树叉树4 42 23 31 15 56 67 78 89 9101011111212非完全二叉树非完全二叉树第十页，共26页。(2) (2) 链式存储链式存储(cn ch)(cn ch)结构结构T16若父结点在数组中若父结点在数组中i i下标下标(xi bio)(xi bio)处，其左孩子在处，其左孩子在2 2* *i i处，右孩子在处，右

11、孩子在2 2* *i+1i+1处。处。1111 A A B BC C F F E E D D 1 1 2 2 4 8 8 9 91010 5 5 6 6 3 3 7 71212131314141515(1) (1) 顺序存储结构顺序存储结构(1) (1) 顺序存储结构顺序存储结构2 2h h-1=-1=2 24 4-1 = 15-1 = 15用一组连续的存储单元存放二用一组连续的存储单元存放二叉树的数据元素。结点在数组叉树的数据元素。结点在数组中的相对位置蕴含着结点之间中的相对位置蕴含着结点之间的关系。的关系。0000FE000DC0BA15141312111098765432100一般二叉树

12、必须按完全二叉树的形式存储，将造成存储的浪费。一般二叉树必须按完全二叉树的形式存储，将造成存储的浪费。第十一页，共26页。rchildrchildDataDatalchildlchild A AD DB B C C E E F F 图为一般图为一般(ybn)(ybn)二叉树的二叉链二叉树的二叉链表结构表结构AECBDF第十二页，共26页。链式存储链式存储(cn ch)结构的算法描述：结构的算法描述：Typedef struct BiTNode int data; struct BiTNode *lchild, *rchild; BiTNode, * BiTree;rchildDatalchil

13、drchildDatalchildrchildDatalchild第十三页，共26页。树的结点个数至少为树的结点个数至少为1 1，而二叉树的结点个数可以，而二叉树的结点个数可以(ky)(ky)为为0 0。树中结点的最大度数没有限制，二叉树结点最大度数为树中结点的最大度数没有限制，二叉树结点最大度数为2 2。树的结点子树无左、右之分，二叉树的结点子树有明确的左、树的结点子树无左、右之分，二叉树的结点子树有明确的左、 右之分。右之分。 二叉树二叉树树树第十四页，共26页。子之间的联系；子之间的联系；以根结点为轴心，将整个树顺时针转以根结点为轴心，将整个树顺时针转4545度。度。第十五页，共26页。

14、 A B CD E G H FI(a)ABEFCDGHI(d) I A B C DE F G H(b)ABCDEFGHI(c)第十六页，共26页。ADCBEFHIGJEFADCBHIGJADCBEFHIGJADCBEFHIGJ方法：方法：将各棵树分别转成二叉树；将各棵树分别转成二叉树；把每棵树的根结点用线连起来；把每棵树的根结点用线连起来；以第一棵树的根结点作为二叉树的以第一棵树的根结点作为二叉树的根结点，按顺时针方向根结点，按顺时针方向(fngxing)(fngxing)旋转。旋转。第十七页，共26页。中序遍历中序遍历(L D R):(L D R):按中序遍历左子树，访问根结点，按按中序遍历

15、左子树，访问根结点，按中序遍历右子树。中序遍历右子树。后序遍历后序遍历(L R D):(L R D):按后序遍历左子树，按后序遍历右子按后序遍历左子树，按后序遍历右子树，访问根结点。树，访问根结点。二叉树为空时，执行空操作，即空二叉二叉树为空时，执行空操作，即空二叉树已遍历完。树已遍历完。第十八页，共26页。先序遍历先序遍历(bin l)(bin l)：D L RD L R中序遍历中序遍历(bin l)(bin l)：L D RL D R后序遍历后序遍历(bin l)(bin l)：L R DL R DA AD DB BC CT T1 1T T2 2T T3 3D L RD L RA AD L

16、 RD L RD L RD L R B B D D C CD L RD L R以先序遍历以先序遍历(bin (bin l)D L Rl)D L R为例演示为例演示遍历遍历(bin l)(bin l)过程过程 ABDCABDCBDACBDAC DBCA DBCA第十九页，共26页。先序遍历先序遍历(bin l)(bin l)二叉树的递归算法：二叉树的递归算法： void PreOderTraverse(BiTree T)void PreOderTraverse(BiTree T) if(T! =NULL) if(T! =NULL) printf (T-data); printf (T-data)

17、; PreOrderTraverse(T-lchild); PreOrderTraverse(T-lchild); PreOrderTraverser(T-rchild); PreOrderTraverser(T-rchild); 第二十页，共26页。第二十一页，共26页。/ /* *建立建立(jinl)(jinl)二叉链表，并进行二叉树的遍历二叉链表，并进行二叉树的遍历* */ /#include stdio.h#include stdio.h#include stdlib.h#include stdlib.hstruct btnodestruct btnode int d; int d;

18、struct btnode struct btnode * *lchild;lchild; struct btnode struct btnode * *rchild;rchild;intrav(struct btnode intrav(struct btnode * *bt)bt) if(bt!=NULL) if(bt!=NULL) pretrav(bt-lchild); pretrav(bt-lchild); printf(%dn,bt-d); printf(%dn,bt-d); pretrav(bt-rchild); pretrav(bt-rchild); return; return;

19、 main()main() struct btnode struct btnode * *bt,bt,* *h;h; bt=create(h,0); bt=create(h,0); pretrav(bt); pretrav(bt); struct btnode *create(bt,k)struct btnode *bt;int k; char b; struct btnode *p,*t; printf(input b:); scanf(%d,&b); if(b!=0) p=(struct btnode *)malloc(sizeof(struct btnode); p-d=b;p-lchild=NULL;p-rchild=NULL; if(k=0) t=p; if(k=1) bt-lchild=p; if(k=2) bt-rchild=p; create(p,1); create(p,2); return