6树和二叉树(数据结构第6章)

1、第六章树和二叉树6.1树tree的概念在日常生活中，可以见到很多情形可以归结为树结构。如：家族谱系、行政管理机构、DOS和Windows 磁盘文件管理系统等。我们讨论的树和自然界的树在生长方向上正好相反，它是倒长的树，即根朝上，枝干和叶子朝下。例1:某家族谱系的一局部宏恩景可宏福意海意河意江意民意凌意山意水例2：国家行政管理机构的一局部例3: DO环口 Windows磁盘文件的一局部TC20VC6.0数据结构课件数据结构讲稿第一章第二章MyTc程序一Tc1Tc2MyVc程序Vc1Vc2树是一种层次结构，属于非线性结构。我们学过的 线性表可以灵活组织数据，但它受到线性结构的限制, 表达层次结构不

2、太方便。树的定义树T是nn?0个结点的有限集合。它满足:(1)仅有一个特定的结点，称为根root丨结点;(2)其余结点分为m(详0)个互不相交的非空有限集合T1,1 T 21-, Tm，其中每个集合自身又是一棵树，称为根的子树subtree。为了表述方便，把没有结点的树称为空树。树的定义具有递归性：即一棵树是由根及假设干 棵子树构成的，而子树又是由根及假设干棵子树构成 的，。表达树的方法通常有4种：树形、凹入、集合和广 义表(1)树形表示法、Il DI E M F (2)凹入表示法(4)广义表表示法T(A(B,C(E,F),D(G,H)树的根本术语为了对树的形态表述清楚和形象，通常引用树和人的

3、特征及术语来描述。1结点和树的度degree结点所拥有的子树的个数称为该结点的度，而树中各结点的度的最大值称为该树的度。1-.Br、 ITjr=riLeI FLg_J如：结点B、E、F、G和H的度数是0结点C和D的度数都是2结点A的度数是3;显然3也是树的度数2叶子leaf结点和分支结点度为0的结点称为叶子结点终端结点；度不为0 的结点称为分支结点非终端结点。一棵树除了叶子结点就是分支节点。IAf r% E JI FD结点B、E、F、G和H是叶子结点结点A、C和D是分支结点3孩子child结点、双亲parents又称父亲 结点、兄弟brother及堂兄弟结点树中一个结点的子树的根称为该结点的孩

4、子，该 结点称为其孩子结点的双亲结点。同一个双亲的孩子 结点互称为兄弟。双亲在同一层的结点互为堂兄弟Iab丿 c丿 d1 1FL EF .f1L G 丿.H丿如:结点B、C和D均为结点A的孩子结点；A是B、 C和D的双亲结点结点E和F为孩子C的结点；C是E和F的双 亲结点结点G和H为孩子D的结点；D是G和H的双 亲结点显然结点A没有双亲结点因为A不是子树的根结点B、C和D互为兄弟；结点E和F互为兄弟； 结点G和H互为兄弟。但结点E、F为一方和G、H 为另一方互为堂兄弟4祖先ancestor和子孙descendant结点的祖先是从根到该所经分支上的所有结点。反 之，以某结点为根的子树中的任一结点

5、称为该结点的 子孙。显然祖先和子孙关系是父子关系的延伸。.A J卩fy rL C : D E.F.G-H如：结点A是结点B、C、D、E、F、G和H的祖先； 反之，结点B、C、D、E、F、G和H是的结点A的 子孙5结点的层数level和树的深度depth，或称 高度 height结点的层次从根结点开始算起，根结点的层数为1, 其余结点的层数等于其双亲结点的层数加1。比方，如果某个结点的层数为h，那么其子树就在第h+1层。树中各个结点层数的最大值称为树的深度高度。LA一 、B.C、D ._I1r 0棵互不相交的树的IAD树的逻辑关系:1树的任一结点都可以有 0个或多个直接的后 继结点孩子，这也是非

6、线性的原因，但至多只能 有一个直接的前驱结点双亲结点；2只有根结点没有前驱，叶子结点终端结点 没有后继；3祖先与子孙关系是父子关系的延伸，它定义 了树中各结点之间的纵向次序；4在有向树中，同一组兄弟结点从左至右有长 幼之分。它定义了树中各结点之间的横向次序。树的根本操作常见的操作：建立、遍历、查询、求深度、求结点的双亲和孩子、求树的深度、求结点的层数和判空等。6.2二叉树一般的树规律性差，二叉树结构简单，存储和处理相对容易，而且一般的树可以转化为二叉树处理621二叉树的定义二叉树是nn0个结点的有限集合，除了空 树n=0之外，由一个根结点及两棵不相交的左子 树和右子树组成；二叉树每个结点的度数

7、w 2;二叉树的定义是一个递归定义。二叉树有5种根本形态：空树?只有根结点?只有右子树?只有左子树?完整二叉树二叉树的性质 性质1 :二叉树的第i层的结点数量最多为2i1i i证明：第1层的结点数目最多为1 20丨，第2层的 结点数目最多为2 21， ，那么第i层的结点数目 最多为2 1性质2:深度为k的二叉树结点数目最多为2k 1k 1 证明：当其每层的结点数到达最大值时，该二叉树的结点数最多，由性质1可知，深度为k的二叉树结 点数是：012k 1k2 2 2 . 2 2 1。性质3:在任意二叉树中，假设叶子终端结点的个数为no，度为2的结点数为n2，那么有no n2 1。证明：设n为结点总

8、数，门为1度的结点数，那么 n no m n?公式 1先分析二叉树的结点度数和分支数的关系：由于度数为2的结点有两个分支，度数为1的结点 有一个分支，度数为0的结点没有分支，所以总的分 支数为n1 2 n2 ；此外，再分析二叉树的双亲结点和分支数的关系： 除根结点之外的每个结点都是其双亲结点的一个 分支，所以总分支数为n 1，可得关系式ni 2n2 n 1 即 n ni 2n2 1公式 2；由公式1和2, 可得作厲1 证毕。如：叶子数为3C，E，F，度数为2的结点数为2A，B，满足性质3* D I EVH J又如：叶子数为2F，G，度数为2的结点数为1A，满足性质3BCI1 : *DE3=f

9、iJ满二叉树的定义：深度为k 1且结点数为2k i 的二叉树。满二叉树的结点数到达最大值。女口：深度为3的满二叉树结点到达7个完全二叉树的定义：对于满二叉树的结点，按以 下规那么编号：?从根结点开始，自上而下；?同一层自左至右。满二叉树的结点编号后，任意取满二叉树的前假设干个连续的结点所对应的二叉树，称为完全二叉树。完全二叉树中，除最后一层外，其余各层均是满的, 最后一层，结点连续出现在左边。女口：深度为4的完全二叉树又如：第2层结点不是连续出现在左侧，所以不是 完全二叉树再如：第3层未满，所以不是完全二叉树.匚D兀eG性质4:具有n个结点的完全二叉树的深度为：1 +(in log2n。证明：

10、由完全二叉树和满二叉树的关系可知，一棵深度为k的完全二叉树的结点数必介于深度为k-1和深度为k的满二叉树的结点数之间，那么有2k1 1 n 2k 1取等号的情况是：完全二叉树是深度 为k的满二叉树，由此推出2k1 n 2k 1 2k，即 k 1 log2n k，所以 k 1intlog2n性质5:如果一棵完全二叉树有n个结点，对所有 结点按层次编号即从上到下，每层从左到右从1 开始编号，那么对任意结点i K i 1，那么其双亲为inti/2;?假设2i n，那么其无左子树。假设 2i+1 n， 那么其无右子树。分析：编号为i=4的结点D，亥树的结点数n=10; 因i1，所以其双亲结点是(int

11、)(i/2)=2(即B);又因 2i=2*4 10,所以该结点有左子树，左孩子编号为2i=8 即 H;再因2i+1=9 1 ,所以其双亲 结点是(int)(i/2)=2(即B);又因2i=2*5 10, 所以该结点没有右子树。6.3 二叉树的存储结构 常用顺序存储结构和链式存储结构。6.3.1 二叉树的顺序存储结构对于完全二叉树进行结点编号后，编号可以反映 结点的分支和附属关系,可以将这些结点存入一维数 组,编号和数组下标可以对应起来。对于一般的二叉树,不易直接采用顺序存储,可 以补成完全二叉树后再用顺序存储的方法存储。以上两点是定义完全二叉树的原因之一。如：一棵普通二叉树由上图用虚结点补成的

12、完全二叉树再顺序存 储A1B2I C3I_ 4D5LjLE6J71L 84 1.p9T 1F10T11 11Il12G13 iLj位置i2345678910111213结点ABCDEFG定义:#defi ne MAXSIZE 100typedef char DataType;typedef structDataType btMAXSIZE+1;int num;SeqBTree;顺序存储结构比较适合于完全全二叉树，对于一 般的二叉树需要引进虚结点，补成完全二叉树后再顺 序存储。632二叉树的链式存储结构定义:typedef struct nodeDataType data;struct node

13、 *lchild,*rchild;BTree;此种定义称为二叉树的二叉链表。在链式结构中，通过每个结点的左右指针域，可以 找到其孩子结点，但要找双亲结点不方便，可以增加一个指针域保存双亲结点的地址，称为带双亲指针的 二叉链表。Ichilddatapare ntsrchildroot结点模式：定义：typedef struct nodeDataType data;struct node *lchild,*pare nts,*rchild;ThTree;6.4二叉树的遍历遍历首先从根结点进入，对每个结点都要遍历到 且每个结点仅遍历一次。可以采用递归方法程序简单和非递归方法程 序稍复杂。3+1 种:

14、-第一种方法:先序遍历：根，左子树，右子树 遍历的结果：A，B，C遍历的足迹：沿途经过各结点的“左部第二种方法:中序遍历：左子树，根，右子树遍历的结果：B，A，C遍历的足迹：沿途经过各结点的“下部第三种方法：后序遍历：左子树，右子树，根遍历的结果：B, C, A遍历的足迹：沿途经过各结点的“右部第四种方法：逆先序遍历：根，右，左B第五种方法:逆中序遍历:右，根，左C, A,B第六种方法： 逆后序遍历:右，左，根C, B ,A第七种方法：按层次遍历：从上根到下逐层进行，自左至右诸个结点进行 遍历的结果：A , B , C例如：对以下二叉树，分别用四种方法遍历D,1.观察：A根B , D, F根的

15、左子树C, E, G根的右子树2. 中序遍历的结果：B , F, D, A , E, G, C 观察：B, F , D根的左子树A根E, G , C根的右子树3. 后序遍历的结果：F , D, B, G , E, C , A观察：F, D, B根的左子树G , E, C根的右子树A根4. 按层次遍历的结果：A, B , C, D, E , F , G 观察：先A根，左右子树次序打乱可以证明：1当二叉树的结点各不相同，假设中序遍历序 列确定，假设再有先序或后序遍历序列也确定， 那么该二叉树唯一确定；2假设二叉树的先序遍历和后序遍历确定，那么 该二叉树不能唯一确定；女口：以下两棵不同的二叉树先序遍

16、历都是A，B，而后序遍历都是B，A。二叉树的先序遍历及其算法遍历规律：先遍历根结点，再遍历左子树，最后遍历右子树先序遍历的递归算法和程序较简单void PreOrder(BTree *bt)if(bt!=NULL)printf( “ %c ,dbat ta); /遍历根结点输出数据 PreOrder(bt lchild); /递归遍历左子树 PreOrder(bt rchild); /递归遍历右子树先序遍历的非递归算法和程序稍复杂void PreOrder1(BTree *bt)BTree *s100,*p=bt; /使用了指针数组int top=0; /使用了栈while(p!=NULL|t

17、op0)while(p!=NULL) /遍历根和左子树printf(“ %c d,apta); s+top=p; p=plchild;p=stop - ;p=p rchild; /遍历右子树6.4.2 二叉树的中序遍历 遍历规律：先遍历左子树， 再遍历根结点， 最后遍 历右子树。中序遍历的递归算法和程序较简单void InOrder(BTree *bt)if(bt!=NULL)InOrder(bt lchild); /递归遍历左子树printf(“%c ,dbatta); /遍历根结点输出数据InOrder(bt rchild); /递归遍历右子树中序遍历的非递归算法和程序稍复杂void In

18、Order1(BTree *bt)BTree *s100,*p=bt;int top=0;while(p!=NULL|top0) while(p!=NULL)s+top=p;p=p lchild; /遍历左子树 p=stop - ;printf(“%c,p data);p=p rchild; /遍历根和 右子树6.4.3 二叉树的后序遍历遍历规律： 先遍历左子树， 再遍历右子树， 最后遍 历根结点。后序遍历的递归算法和程序较简单void PostOrder(BTree *bt)if(bt!=NULL)PostOrder(bt lchild); /递归遍历左子树PostOrder(bt rchi

19、ld); /递归遍历右子树printf( “%c ,dbatta); /遍历根结点输出数据后序遍历的非递归算法和程序稍复杂void PostOrder1(BTree *bt)BTree *s1100,*p=bt;int s2100,b,top=0;dowhile(p!=NULL) /遍历左子树s1top=p;s2top+=0;p=p lchild;if(top0)b=s2-top; p=s1top;if(b=0)s1top=p;s2top+=1;p=p rchild; /遍历右子树else printf( “ %cdata,p); p=NULL; /遍历根while(top0);6.4.4 二

20、叉树的按层次遍历先遍历根结点，再遍历根结点的孩子结点，再遍历孩子结点的孩子结点，。具体如下：? 设置一个队列，将其置空，假设树非空，先将根 结点入队；? 重复下述操作，直至队列为空：队首结点出队，遍历该结点；假设该结点有左子树，那么将左子树的根结点入队；假设该结点有右子树， 那么将右子树的根结点入队。typedef structBTree *sMAXSIZE;int front,rear;Sequence; /顺序队列类型void ScanLevel(BTree *t)/ 按层次遍历二叉树 非递归 Sequence que;/ 定义队列 que.front=que.rear=0;/ 初始化队列

21、 if(t!=NULL)/ 树非空，将根结点入队 que.rear+; que.sque.rear=t;printf( 二叉树的层次结点是： ); while(que.front!=que.rear)/ 队列非空 que.front+;/ 队头出队 t=que.sque.front;printf(%c ,t data); / 遍历结点if(t lchild!=NULL)/ 左孩子入队que.rear+;que.sque.rear=t lchild;if(t rchild!=NULL)/ 右孩子入队que.rear+;que.sque.rear=t rchild;根据按层次遍历的思想，创立二叉树

22、；由于二叉树的结点构成比较复杂，创立和遍历时 必须有规律才能在机器上实施，这就想到以前讲过的 完全二叉树，完全二叉树结点有对应的编号，然后按 层次逐个输入各结点的编号和数据，直至结束。假设 输入非根结点，根据其编号偶数为左子树结点，奇 数为右子树结点 ，将其链接到其双亲结点的相应指 针域上。例如：上述曾经讨论过的二叉树用添加虚结点的方法补成一棵完全二叉树且对结点编号;3C 一 . . .45门匸789 Q|Of l1 l2 l3G这里带的结点是虚结点；除根结点外，左子树结点 都是偶数编号，右子树结点都是奇数编号。BTree *CreateTree()FILE *fp;BTree *t,*p,*

23、seqMAXSIZE;DataType x;int i;fp=fopen(p6 -1.dat,r);printf( 输入二叉树的层次结点： n); fscanf(fp,%d %c,&i,&x);printf(%d %cn,i,x)if(x!=)/ 建立根结点t=(BTree *)malloc(sizeof(BTree);t data=x;t lchild=NULL;t rchild=NULL;else return NULL;seqi=t;fscanf(fp,%d %c,&i,&x);printf(%d %cn,i,x); while(x!=)p=(BTree *)malloc(sizeof(

24、BTree);p data=x;p lchild=NULL;p rchild=NULL;seqi=p;if(i%2=0)seqi/2 lchild=p;/ 建立左子树 else seqi/2 rchild=p;/ 建立右子树 fscanf(fp,%d %c,&i,&x);printf(%d %cn,i,x);fclose(fp);printf(n);return t;程序 p6-1.c 二叉树的层次建立和遍历 输入时注意结点的编号 作为结束标志匚訂Q3 CO訂CO C输入文件编号和内容，作为结束标志：1A2B3C 5D6E10F13G0 作为结束标志#define MAXSIZE 100 #i

25、n clude typedef char DataType; typedef struct nodeDataType data; struct node *lchild,*rchild;BTree;typedef structBTree *sMAXSIZE; int front,rear;Sequence;BTree *CreateTree()FILE *fp;BTree *t,*p,*seqMAXSIZE;DataType x;int i;fp=fopen(p6 -1.dat,r);printf( 输入二叉树的层次结点： n);fscanf(fp,%d %c,&i,&x);printf(%d

26、 %cn,i,x);if(x!=)t=(BTree *)malloc(sizeof(BTree);l. ujniejJC.uvJwuudKclesoioj Tee% p%11)wuud ：(xg!gQ% p%11tdj)jueosj Jd=p|iqo乙/!bes es|e ：d 二 PI!U5s/!bes(o=2%!)4!Jd=ibesFnN 二 Pig dFnN 二 PI!U5 d Jx=eiep d J(eejig)joezis)oo|eiJuG eejig)=d (.=ix)e|!M/v KxThUXO% p%11)wuudJ(xt!t11o% p%11tdj)jueosj =!bes

27、FnN un冋 es|eFnN 二 PI!US FriN 二 PI!U5 Jx=eiep void ScanLevel(BTree *t)Sequence que;que.front=que.rear=0;if(t!=NULL)que.rear+;que.sque.rear=t;printf( 二叉树的层次结点是： );while(que.front!=que.rear)que.front+;t=que.sque.front;printf(%c ,tdata); / 遍历结点if(t lchild!=NULL)que.rear+;que.sque.rear=t lchild;if(t rchi

28、ld!=NULL)que.rear+;que.sque.rear=t rchild;void main()BTree *t;t=CreateTree();ScanLevel(t);printf(n);二叉树遍历的应用通过遍历二叉树，可以输出树中的结点数据，统计 和查找结点中的信息等。 如统计树中结点数、 叶子数、 树的深度，查找最大小结点的值等。(1) 求二叉树的结点数中序法int NodeNumber=0;/ 统计结点个数计数变量void InOrder(BTree *bt)if(bt!=NULL) InOrder(bt lchild);/ 遍历左子树NodeNumber+;/ 遍历根结点统

29、计结点 InOrder(bt rchild);/ 遍历右子树(2) 二叉树的递归建立BTree *CreateTree()/ 先序法建立BTree *t;DataType x; scanf(%c,&x); if(x= ) return NULL;elset=(BTree *)malloc(sizeof(BTree);/ 建立根结点 t data=x;t lchild=CreateTree();/ 建立左子树t rchild=CreateTree();/ 建立右子树 return t;p6-2.c递归“先序建立二叉树并用四种方法遍历先序、中序、后序和按层次AEIF注意：这棵树不是完全二叉树，但每

30、个结点要指明它的左右子树是否存在，假设不存在补上一个空结点为的是容易存储和判断。输入先序文件： ABDFCEG #define MAXSIZE 100 #include typedef char DataType;typedef struct nodeDataType data;struct node *lchild,*rchild;BTree;FILE *fp;BTree *CreatTree( ) /先序递归建立二叉树char x;BTree *t; x=fgetc(fp); if(x=)return NULL;elset=(BTree *)malloc(sizeof(BTree);t d

31、ata=x;t lchild=CreatTree();t rchild=CreatTree();return t;void PreOrder(BTree *bt) /先序递归遍历if(bt!=NULL)printf(%3c,bt data);PreOrder(bt lchild);PreOrder(bt rchild);void PreOrder1(BTree *bt) /先序非递归遍历BTree *s100,*p=bt;int top=0;while(p!=NULL|top0)while(p!=NULL)宀 pinff(=%3c=p dafa)八 s+foplrp 八 PHP -ch=5PH

32、S&pkpHP rchi-auoid -node(BTee *bo 二号书丘&逗 宀if(bfHNULL)宀-norders-ch=d)八 pinff(=%3c=bf das-)八-nordersch=dxvoid -node=(BTee *bf) /甘书亠 EyLU-B汪 宀BTree *SMAXS_ZEL*PH2in二 OPHPwhi_e(pHNUL u-fopvo)宀whi-e(pHNULL)宀 s+fopHpPHP -ch=5np=stop -;printf(%3c,pdata);p=p rchild;void PostOrder(BTree *bt) / 后序递归遍历if(bt!=N

33、ULL)PostOrder(bt lchild);PostOrder(bt rchild);printf(%3c,bt data);void PostOrder1(BTree *bt) /后序非递归遍历BTree *s1MAXSIZE,*p=bt;int s2MAXSIZE,b,top=0;dolchild;while(p!=NULL)s1top=p;s2top+=0;p=p if(top0)b=s2-top; p=s1top;if(b=0)s1top=p;s2top+=1;p=p rchild;else printf(%3c,p data); p=NULL;while(top0);void

34、LevelOrder(BTree *bt) /按层次遍历BTree *qMAXSIZE,*p;int front,rear;q1=bt;front=rear=1;while(front=rear)p=qfront;front+;printf(%3c,p data);if(p lchild!=NULL)rear+;qrear=plchild;if(p rchild!=NULL)rear+;qrear=prchild;void main()BTree *t;fp=fopen(p6 -2.dat,r);printf( 输入数据在文件中读出！ nn);t=CreatTree();fclose(fp);

35、printf( 先序递归法遍历： printf( 先序非递归法遍历： printf(nn);printf( 中序递归法遍历： printf(n);printf( 中序非递归法遍历： printf(nn);printf( 后序递归法遍历： printf(n);printf( 后序非递归法遍历： printf(nn);printf( 按层次遍历： printf(nn););PreOrder(t);printf(n);PreOrder1(t););InOrder(t););InOrder1(t););PostOrder(t););PostOrder1(t););LevelOrder(t);程序 p6

36、-3.c 家族树的建立和统计该家族的平均年龄；指定的某个家族成员的辈分；输出指定的某个辈分的所有家族成员景奇60宏恩58宏亮5弓新民661 1新主69新诚881新胜70vrvr意海430意河86意江73意凌弓 0意山6|意水6 C匚叮口匚CICOC匚。I订匚叮按先序输入其中0为虚结点：60 景奇(Ji ngqi)58 宏恩(Ho ngen)66 新民(Xi nmin)43 意海(Yihai)0 XX0 XX0 XX69 新主(Xin zhu)86 意河(Yihe)0 XX0 XX73 意江(Yijia ng)0 XX0 XX55 宏亮 (Hongliang)88 新诚 (Xincheng)55 意凌 (Yi