《树和二叉树（数据结构第6章）.docx》由会员分享，可在线阅读，更多相关《树和二叉树（数据结构第6章）.docx（70页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第六章 树和二叉树 6.1树（tree）的概念 在日常生活中，可以见到很多情形可以归结为树结构。如：家族谱系、行政管理机构、DOS和Windows磁盘文件管理系统等。 我们讨论的树和自然界的树在生长方向上正好相反，它是倒长的树，即根朝上，枝干和叶子朝下。 例1：某家族谱系的一部分例2：国家行政管理机构的一部分例3：DOS和Windows磁盘文件的一部分C:TC20VC6.0数据结构课件 数据结构讲稿 第一章 第二章 MyTc程序 Tc1 Tc2 MyVc程序 Vc1 Vc2 树是一种层次结构，属于非线性结构。我们学过的线性表可以灵活组织数据，但它受到线性结构的限制，表达层次结构不太方便。6.1
2、.1树的定义 树T是n（n0）个结点的有限集合。它满足：(1)仅有一个特定的结点，称为根（root）结点;(2)其余结点分为m(m0)个互不相交的非空有限集合,其中每个集合自身又是一棵树，称为根的子树（subtree）。 为了表述方便，把没有结点的树称为空树。树的定义具有递归性：即一棵树是由根及若干棵子树构成的，而子树又是由根及若干棵子树构成的，。表达树的方法通常有4种：树形、凹入、集合和广义表(1) 树形表示法ABCDEFGH(2) 凹入表示法ABCEFDGH(3) 集合嵌套表示法 ACDB(4) 广义表表示法 T(A(B,C(E,F),D(G,H)6.1.3 树的基本术语 为了对树的形态表
3、述清楚和形象，通常引用树和人的特征及术语来描述。（1）结点和树的度（degree）结点所拥有的子树的个数称为该结点的度，而树中各结点的度的最大值称为该树的度。ABCDEFGH如：结点B、E、F、G和H的度数是0结点C和D的度数都是2结点A的度数是3；显然3也是树的度数（2）叶子（leaf）结点和分支结点度为0的结点称为叶子结点（终端结点）；度不为0的结点称为分支结点（非终端结点）。一棵树除了叶子结点就是分支节点。ABCDEFGH如: 结点 B、E、F、G和H是叶子结点结点A、C和D是分支结点（3）孩子（child）结点、双亲（parents又称父亲）结点、兄弟（brother）及堂兄弟结点树中
4、一个结点的子树的根称为该结点的孩子，该结点称为其孩子结点的双亲结点。同一个双亲的孩子结点互称为兄弟。双亲在同一层的结点互为堂兄弟。ABCDEFGH如:结点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、结点的子孙。显然祖先和子孙关系是父子关系的延伸。ABCDEFGH 如：结点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层。树中各个结点层数的最大值称为树的深度（高度）。ABCDEFGH如:结点A的层数为1；结点B、C和D的层数为2；结点E、F、G和H的层数为3树的深度（高度）为3。（6）有序树（orderedtree）和无序树（unor
6、deredtree）若一棵树中结点的各子树从左到右是有次序的，即若交换了某结点各子树的相对位置就构成不同的树，则称这棵树为有序树，否则称为无序树。（7）路径（path）从树中的一个结点到另一个结点的路途ABCDEFGH 如：A-C-E,A-D-H等 但B-A-D-G不是路径，因为树不能这样遍历。（8）森林（forest）：m（m0）棵互不相交的树的集合ABCDEFGHABCD树的逻辑关系：（1）树的任一结点都可以有0个或多个直接的后继结点（孩子，这也是非线性的原因），但至多只能有一个直接的前驱结点（双亲结点）；（2）只有根结点没有前驱，叶子结点（终端结点）没有后继；（3）祖先与子孙关系是父子关
7、系的延伸，它定义了树中各结点之间的纵向次序；（4）在有向树中，同一组兄弟结点从左至右有长幼之分。它定义了树中各结点之间的横向次序。6.1.4树的基本操作常见的操作：建立、遍历、查询、求深度、求结点的双亲和孩子、求树的深度、求结点的层数和判空等。6.2 二叉树一般的树规律性差，二叉树结构简单，存储和处理相对容易，而且一般的树可以转化为二叉树处理。6.2.1二叉树的定义二叉树是n（n0）个结点的有限集合，除了空树（n=0）之外，由一个根结点及两棵不相交的左子树和右子树组成；二叉树每个结点的度数2；二叉树的定义是一个递归定义。二叉树有5种基本形态：空树 只有根结点 只有右子树 只有左子树 完整二叉树
8、 6.2.2 二叉树的性质性质1：二叉树的第i层的结点数量最多为。ABCDEFG证明：第1层的结点数目最多为1（），第2层的结点数目最多为2（），则第i层的结点数目最多为。性质2：深度为k的二叉树结点数目最多为。证明：当其每层的结点数达到最大值时，该二叉树的结点数最多，由性质1可知，深度为k的二叉树结点数是：。性质3：在任意二叉树中，若叶子（终端）结点的个数为，度为2的结点数为，则有。证明：设n为结点总数，为1度的结点数，则（公式1）先分析二叉树的结点度数和分支数的关系：由于度数为2的结点有两个分支，度数为1的结点有一个分支，度数为0的结点没有分支，所以总的分支数为；此外，再分析二叉树的双亲结
9、点和分支数的关系：除根结点之外的每个结点都是其双亲结点的一个分支，所以总分支数为，可得关系式，即（公式2）；由公式1和2，可得，证毕。如：叶子数为3（C，E，F），度数为2的结点数为2（A，B），满足性质3。 又如：叶子数为2（F，G），度数为2的结点数为1（A），满足性质3。 满二叉树的定义：深度为k（k1）且结点数为的二叉树。满二叉树的结点数达到最大值。如：深度为3的满二叉树结点达到7个 A1B2C3D4E5F6G7完全二叉树的定义：对于满二叉树的结点，按下列规则编号：从根结点开始，自上而下；同一层自左至右。满二叉树的结点编号后，任意取满二叉树的前若干个连续的结点所对应的二叉树，称为完全二
10、叉树。完全二叉树中，除最后一层外，其余各层均是满的，最后一层，结点连续出现在左边。如：深度为4的完全二叉树 又如：第2层结点不是连续出现在左侧，所以不是完全二叉树 再如：第3层未满，所以不是完全二叉树性质4：具有n个结点的完全二叉树的深度为：1+。证明：由完全二叉树和满二叉树的关系可知，一棵深度为k的完全二叉树的结点数必介于深度为k-1和深度为k的满二叉树的结点数之间，则有（取等号的情况是：完全二叉树是深度为k的满二叉树），由此推出，即，所以性质5：如果一棵完全二叉树有n个结点，对所有结点按层次编号（即从上到下），每层从左到右从1开始编号，则对任意结点i（1in），有： 若i=1，则其为根，没
11、有双亲。若i1，则其双亲为(int)(i/2); 若2in（即它有左子树），则其左子树编号为2i;若2in，则其无左子树。若2i+1n（即它有右子树），则其右子树的编号为2i+1; 若2i+1n，则其无右子树。分析：编号为i=4的结点D，该树的结点数n=10；因i1，所以其双亲结点是(int)(i/2)=2(即B)；又因2i=2*410，所以该结点有左子树，左孩子编号为2i=8（即H）；再因2i+1=910, 所以该结点有右子树，右孩子编号为2i+1=9（即I）再分析：编号为i=5的结点E，因i1，所以其双亲结点是(int)(i/2)=2(即B)；又因2i=2*510，所以该结点有左子树，左孩
12、子编号为2i=10（即J）；再因2i+1=1110, 所以该结点没有右子树。6.3 二叉树的存储结构常用顺序存储结构和链式存储结构。6.3.1 二叉树的顺序存储结构对于完全二叉树进行结点编号后，编号可以反映结点的分支和从属关系，可以将这些结点存入一维数组，编号和数组下标可以对应起来。对于一般的二叉树，不易直接采用顺序存储，可以补成完全二叉树后再用顺序存储的方法存储。以上两点是定义完全二叉树的原因之一。 如：一棵普通二叉树 由上图用虚结点（）补成的完全二叉树再顺序存储 位置1 2345678910111213结点ABCDEFG定义：#define MAXSIZE 100typedef char
13、DataType;typedef struct DataType btMAXSIZE+1; int num;SeqBTree;顺序存储结构比较适合于完全全二叉树，对于一般的二叉树需要引进虚结点，补成完全二叉树后再顺序存储。6.3.2 二叉树的链式存储结构lchild data rchild 结点模式： rootA E B C D G F 定义：typedef struct node DataType data; struct node *lchild,*rchild;BTree; 此种定义称为二叉树的二叉链表。在链式结构中，通过每个结点的左右指针域，可以找到其孩子结点，但要找双亲结点不方便，可
14、以增加一个指针域保存双亲结点的地址，称为带双亲指针的二叉链表。lchild data parents rchild结点模式： rootA C B ED F G 定义：typedef struct node DataType data; struct node *lchild,*parents,*rchild;ThTree;6.4 二叉树的遍历遍历首先从根结点进入，对每个结点都要遍历到且每个结点仅遍历一次。可以采用递归方法（程序简单）和非递归方法（程序稍复杂）。 ABC遍历二叉树，可有6+1种方法（实际采用3+1种）：第一种方法：先序遍历：根，左子树，右子树 遍历的结果：A，B，C遍历的足迹：沿
15、途经过各结点的“左部”第二种方法：中序遍历：左子树，根，右子树 遍历的结果：B，A，C遍历的足迹：沿途经过各结点的“下部”第三种方法：后序遍历：左子树，右子树，根 遍历的结果：B，C，A遍历的足迹：沿途经过各结点的“右部”第四种方法：逆先序遍历：根，右，左 A，C，B第五种方法：逆中序遍历：右，根，左 C，A，B第六种方法：逆后序遍历：右，左，根 C，B，A 第七种方法：按层次遍历：从上（根）到下逐层进行，自左至右诸个结点进行。遍历的结果：A，B，C 例如：对下列二叉树，分别用四种方法遍历 1. 先序遍历的结果：A，B，D，F，C，E，G观察：A（根）B，D，F（根的左子树） C，E，G（根的
16、右子树） 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）若二叉树的先序遍历和后序遍历确定，则该二叉树不能唯一确定； 如：下列两棵不同的二叉树先序遍历都是（A，B），而后序遍历都是（B，A）。 6.4.1 二
17、叉树的先序遍历及其算法 遍历规律：先遍历根结点，再遍历左子树，最后遍历右子树。 先序遍历的递归算法和程序（较简单） void PreOrder(BTree *bt) if(bt!=NULL) printf(“%c ”,btdata); /遍历根结点（输出数据）PreOrder(btlchild); /递归遍历左子树PreOrder(btrchild); /递归遍历右子树 先序遍历的非递归算法和程序（稍复杂） void PreOrder1(BTree *bt) BTree *s100,*p=bt; /使用了指针数组 int top=0; /使用了栈 while(p!=NULL|top0) whi
18、le(p!=NULL) /遍历根和左子树 printf(“%c ”,pdata); s+top=p; p=plchild; p=stop-;p=prchild; /遍历右子树 6.4.2 二叉树的中序遍历遍历规律：先遍历左子树，再遍历根结点，最后遍历右子树。中序遍历的递归算法和程序（较简单） void InOrder(BTree *bt) if(bt!=NULL) InOrder(btlchild); /递归遍历左子树 printf(“%c ”,btdata); /遍历根结点（输出数据）InOrder(btrchild); /递归遍历右子树 中序遍历的非递归算法和程序（稍复杂） void In
19、Order1(BTree *bt) BTree *s100,*p=bt; int top=0; while(p!=NULL|top0) while(p!=NULL)s+top=p;p=plchild; /遍历左子树 p=stop-;printf(“%c ”,pdata);p=prchild; /遍历根和右子树 6.4.3 二叉树的后序遍历遍历规律：先遍历左子树，再遍历右子树，最后遍历根结点。后序遍历的递归算法和程序（较简单） void PostOrder(BTree *bt) if(bt!=NULL) PostOrder(btlchild); /递归遍历左子树PostOrder(btrchil
20、d); /递归遍历右子树printf(“%c ”,btdata); /遍历根结点（输出数据） 后序遍历的非递归算法和程序（稍复杂） void PostOrder1(BTree *bt) BTree *s1100,*p=bt; int s2100,b,top=0; do while(p!=NULL) /遍历左子树s1top=p;s2top+=0;p=plchild; if(top0) b=s2-top; p=s1top; if(b=0)s1top=p;s2top+=1;p=prchild; /遍历右子树else printf(“%c ”,pdata); p=NULL; /遍历根 while(to
21、p0); 6.4.4 二叉树的按层次遍历先遍历根结点，再遍历根结点的孩子结点，再遍历孩子结点的孩子结点，。具体如下： 设置一个队列，将其置空，若树非空，先将根结点入队； 重复下述操作，直至队列为空： 队首结点出队，遍历该结点； 若该结点有左子树，则将左子树的根结点入队；若该结点有右子树，则将右子树的根结点入队。typedef structBTree *sMAXSIZE;int front,rear;Sequence; /顺序队列类型void ScanLevel(BTree *t)/按层次遍历二叉树（非递归）Sequence que;/ 定义队列que.front=que.rear=0;/初始化
22、队列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(tlchild!=NULL)/左孩子入队que.rear+;que.sque.rear=tlchild;if(trchild!=NULL)/右孩子入队que.rear+;que.sque.rear=trchild; 根据按层次遍历的思想，创建二叉树; 由于二叉树的结点构成比较复
23、杂，创建和遍历时必须有规律才能在机器上实施，这就想到以前讲过的完全二叉树，完全二叉树结点有对应的编号，然后按层次逐个输入各结点的编号和数据，直至结束。若输入非根结点，根据其编号（偶数为左子树结点，奇数为右子树结点），将其链接到其双亲结点的相应指针域上。例如：上述曾经讨论过的二叉树 用添加虚结点的办法补成一棵完全二叉树且对结点编号； 这里带的结点是虚结点；除根结点外，左子树结点都是偶数编号，右子树结点都是奇数编号。BTree *CreateTree()FILE *fp;BTree *t,*p,*seqMAXSIZE;DataType x;int i;fp=fopen(p6-1.dat,r);pr
24、intf(输入二叉树的层次结点：n);fscanf(fp,%d %c,&i,&x);printf(%d %cn,i,x);if(x!=)/建立根结点t=(BTree *)malloc(sizeof(BTree);tdata=x;tlchild=NULL;trchild=NULL;else return NULL;seqi=t; fscanf(fp,%d %c,&i,&x);printf(%d %cn,i,x); while(x!=) p=(BTree *)malloc(sizeof(BTree);pdata=x;plchild=NULL;prchild=NULL;seqi=p;if(i%2=0
25、)seqi/2lchild=p;/建立左子树else seqi/2rchild=p;/建立右子树 fscanf(fp,%d %c,&i,&x);printf(%d %cn,i,x);fclose(fp);printf(n);return t;程序p6-1.c 二叉树的层次建立和遍历 输入时注意结点的编号（作为结束标志）输入文件（编号和内容， 作为结束标志）：1A2B3C5D6E10F13G0 /作为结束标志#define MAXSIZE 100#includetypedef char DataType;typedef struct nodeDataType data;struct node *
26、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 %cn,i,x);if(x!=)t=(BTree *)malloc(sizeof(BTree);tdata=x;tlchild=NULL;trchild=NULL
27、;else return NULL;seqi=t; fscanf(fp,%d %c,&i,&x);printf(%d %cn,i,x); while(x!=)p=(BTree *)malloc(sizeof(BTree);pdata=x;plchild=NULL;prchild=NULL;seqi=p;if(i%2=0)seqi/2lchild=p;else seqi/2rchild=p; fscanf(fp,%d %c,&i,&x);printf(%d %cn,i,x);fclose(fp);printf(n);return t;void ScanLevel(BTree *t)Sequenc
28、e 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(tlchild!=NULL)que.rear+;que.sque.rear=tlchild;if(trchild!=NULL)que.rear+;que.sque.rear=trchild;void main()BTree *t;t=CreateTree();ScanL
29、evel(t); printf(n);6.4.5二叉树遍历的应用通过遍历二叉树，可以输出树中的结点数据，统计和查找结点中的信息等。如统计树中结点数、叶子数、树的深度，查找最大（小）结点的值等。(1) 求二叉树的结点数（中序法） int NodeNumber=0;/统计结点个数计数变量 void InOrder(BTree *bt) if(bt!=NULL) InOrder(btlchild);/遍历左子树 NodeNumber+;/遍历根结点（统计结点） InOrder(btrchild);/遍历右子树 (2) 二叉树的递归建立BTree *CreateTree()/先序法建立BTree *t
30、;DataType x;scanf(%c,&x);if(x=) return NULL; elset=(BTree *)malloc(sizeof(BTree);/建立根结点tdata=x;tlchild=CreateTree();/建立左子树trchild=CreateTree();/建立右子树return t; p6-2.c递归“先序”建立二叉树并用四种方法遍历（先序、中序、后序和按层次）。 注意：这棵树不是完全二叉树，但每个结点要指明它的左右子树是否存在，若不存在补上一个空结点（）为的是容易存储和判断。输入（先序）文件：ABDFCEG#define MAXSIZE 100#include
31、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);tdata=x;tlchild=CreatTree();trchild=CreatTree();return t;void PreOrder(BTree *bt)/先序递归遍历if(
32、bt!=NULL)printf(%3c,btdata); PreOrder(btlchild);PreOrder(btrchild);void PreOrder1(BTree *bt)/先序非递归遍历 BTree *s100,*p=bt; int top=0; while(p!=NULL|top0) while(p!=NULL)printf(%3c,pdata); s+top=p; p=plchild; p=stop-;p=prchild; void InOrder(BTree *bt)/中序递归遍历if(bt!=NULL)InOrder(btlchild);printf(%3c,btdata
33、);InOrder(btrchild);void InOrder1(BTree *bt)/中序非递归遍历 BTree *sMAXSIZE,*p=bt; int top=0; while(p!=NULL|top0) while(p!=NULL)s+top=p;p=plchild; p=stop-;printf(%3c,pdata);p=prchild; void PostOrder(BTree *bt)/后序递归遍历if(bt!=NULL)PostOrder(btlchild);PostOrder(btrchild);printf(%3c,btdata);void PostOrder1(BTre
34、e *bt)/后序非递归遍历 BTree *s1MAXSIZE,*p=bt; int s2MAXSIZE,b,top=0; do while(p!=NULL)s1top=p;s2top+=0;p=plchild; if(top0) b=s2-top; p=s1top; if(b=0)s1top=p;s2top+=1;p=prchild; else printf(%3c,pdata); p=NULL; while(top0);void LevelOrder(BTree *bt)/按层次遍历BTree *qMAXSIZE,*p;int front,rear;q1=bt;front=rear=1;w
35、hile(front=rear)p=qfront;front+;printf(%3c,pdata);if(plchild!=NULL)rear+;qrear=plchild; if(prchild!=NULL)rear+;qrear=prchild;void main()BTree *t;fp=fopen(p6-2.dat,r);printf(输入数据在文件中读出！nn);t=CreatTree();fclose(fp);printf(先序递归法遍历： );PreOrder(t);printf(n);printf(先序非递归法遍历：);PreOrder1(t);printf(nn);print
36、f(中序递归法遍历： );InOrder(t);printf(n);printf(中序非递归法遍历：);InOrder1(t);printf(nn);printf(后序递归法遍历： );PostOrder(t);printf(n);printf(后序非递归法遍历：);PostOrder1(t);printf(nn);printf(按层次遍历： );LevelOrder(t);printf(nn);程序p6-3.c 家族树的建立和统计该家族的平均年龄； 指定的某个家族成员的辈分； 输出指定的某个辈分的所有家族成员。按先序输入（其中0为虚结点）：60 景奇(Jingqi)58 宏恩(Hongen)
37、66 新民(Xinmin)43 意海(Yihai)0 XX0 XX0 XX69 新主(Xinzhu)86 意河(Yihe)0 XX0 XX73 意江(Yijiang)0 XX0 XX55 宏亮(Hongliang)88 新诚(Xincheng)55 意凌(Yiling)0 XX0 XX0 XX70 新胜(Xinsheng)66 意山(Yishan)0 XX0 XX66 意水(Yishui)0 XX0 XX/建立二叉树家族，求家族平均年龄和辈份#define MAX 100#includetypedef structint age;char name20;DataType;typedef str
38、uct nodeDataType data;struct node *lchild,*rchild;BTree;FILE *fp;int TotalAge,TotalNumber;BTree *CreateTree();void Traversing(BTree *t);void PreOrder(BTree *t);void NodeLevel(BTree *t,int h,DataType x);void OutPutLevelNode(BTree *t,int h);void visitstring(BTree *t,int h);void main()BTree *root;DataType x;int h;fp=fopen(p6-3.dat,r);root=CreateTree();fclose(fp);TotalAge=0;TotalNumber=0;PreOrder(root);if(TotalNumb