上海金融学院信息管理系

树上海金融学院信息管理系树上海金融学院信息管理系1第五章树5.1树的基本概念一、树的定义：树是由一个结点或多个结点组成的有限集T，它满足下面两个条件：（１）有一个特定的结点，称为根结点；（２）其余的结点分成m（m≥0）个互不相交的有限集T0,T1,T2,…,Tm-1。其中每个集合又都是一棵树。称T0,T1,T2,…,Tm-1为根结点的子树。第五章树5.1树的基本概念25.1树的基本概念k1k0k2k3k4k5k6k7k8k9k105.1树的基本概念k1k0k2k3k4k5k6k7k8k935.1树的基本概念二、基本概念o一棵树至少有一个结点。o叶子结点没有子树；非叶子结点至少有一棵子树。o结点的子树的个数为该结点的次数。显然，叶子结点的次数为０。o树中的各结点次数的最大值，为该树的次数。上一页的树为３次树。o树T是一棵m次树，若它的非叶子结点的次数均为m，则称T为一棵m次完全树。5.1树的基本概念二、基本概念45.1树的基本概念o若结点ki和kj被一条线段所连接，ki在上端，kj在下端，则ki是kj的父结点，kj为ki的子结点。o同为某结点的子结点，则称为兄弟结点。o根结点所在的层次为０；其他结点所在层次等于它的父结点所在层次加１。o树中结点的最大层次，称为该树的深度，或高度。5.1树的基本概念o若结点ki和kj被一条线段所连接，k55.1树的基本概念o若结点ki能自上而下地通过树中结点到达结点kj，则称ki到kj存在一条路径。路径可用结点序列来表示。注意：位于不同子树中的两个结点之间不存在路径。o路径长度等于这条路径上的结点个数减１。o从根结点到树中的其余结点的路径称为树枝。其路径长度称为树枝长度。5.1树的基本概念o若结点ki能自上而下地通过树中结点到65.1树的基本概念o在路径（k0,k1,k2,…,kn-1,kn）中，k0,k1,k2,…,kn-1为kn的祖先，k1,k2,…,kn-1,kn为k0的后代。o若在给定的m次树中，每个结点的每棵子树规定了序号（一般从左到右），次序不能交换，则该树为有序树。否则，称为无序树。5.1树的基本概念o在路径（k0,k1,k2,…,75.1树的基本概念三、树结构的应用１．表示层次关系：家庭结构２．有序树表示某种顺序关系（１）句子结构（２）算术表达式p.1045.1树的基本概念三、树结构的应用85.2树的存储结构树是不同于线性表的非线性结构，不能用一维数组或线性链表来存储树。树的结点的一般形式：data:存储结点值，可有多个分量（包括键）。pointers:指针，可有多个分量，表现结点之间的非线性关系。datapointers5.2树的存储结构树是不同于线性表的非线性结构，不能用95.2树的存储结构１.树的标准形式存储结构若树是m次树，则结点的数据结构为：pointers有m个字段，依次存放子结点的地址。若某个序号的子结点不存在，则置空。datachild0,child1,child2,…,childm-2,childm-1pointers5.2树的存储结构１.树的标准形式存储结构datachi10１.树的标准形式存储结构标准形式若为３次树，则结点的类型描述为：structnode{intdata;structnode*child[3];};typedefstructnodeNODE;NODE*root1;１.树的标准形式存储结构标准形式115.2树的存储结构2.树的逆形式存储结构结点的数据结构为：parent是一个指针，指向父结点。只有根结点没有父结点，根结点的parent字段置空。dataparent5.2树的存储结构2.树的逆形式存储结构datapa122.树的逆形式存储结构逆形式结点的类型描述为：structr_node{intdata;structr_node*parent;};typedefstructr-nodeR_NODE;R_NODE*root2;2.树的逆形式存储结构逆形式结点的类型描述为：135.2树的存储结构3.树的扩充标准形式存储结构若树为m次树，则结点的数据结构为：其中：指针parent指向父结点；指针childi（０≤i≤m-1）依次指向子结点。dataparentchild0,child1,child2,…,childm-2,childm-15.2树的存储结构3.树的扩充标准形式存储结构datap143.树的扩充标准形式存储结构若树为３次树，则结点的类型描述为：structe_node{intdata;structe_node*child[3];structe_node*parent;};typedefstructe_nodeE_NODE;E_NODE*root3;3.树的扩充标准形式存储结构若树为３次树，则结点的类型155.2树的存储结构树的图示：pp.106-107标准形式逆形式扩充标准形式5.2树的存储结构树的图示：165.4树的遍历树的遍历：按某种指定的次序获得一棵树中的所有的结点。树的遍历是对于树结构进行的最基本和最重要的一种操作。5.4树的遍历树的遍历：按某种指定的次序获得一棵树中的175.4树的遍历遍历方法：（１）前序遍历（２）后序遍历（３）层次遍历（４）遍历叶子结点（５）对于二叉树，中序遍历（以后讲）5.4树的遍历遍历方法：18（1）前序遍历首先访问根结点，然后按前序遍历根结点的各棵子树。对于下面的树，前序遍历的结点序列为ABCDEFGHJKL.ABHDCLKJGEF（1）前序遍历首先访问根结点，然后按前序遍历根结点的各棵19（2）后序遍历首先按后序遍历根结点的各棵子树，然后访问根结点。对于下面的树，后序遍历的结点序列为CFEGDHBKLJA.ABHDCLKJGEF（2）后序遍历首先按后序遍历根结点的各棵子树，然后访问根20（3）层次遍历首先访问第０层的根结点，然后访问第１层的结点，再逐一访问以下各层。对于下面的树，层次遍历的结点序列为ABJCDHKLEGF.ABHDCLKJGEF（3）层次遍历首先访问第０层的根结点，然后访问第１层的结21（4）树中叶子结点遍历如果只有一个结点，则该结点就是叶子结点；否则就是根结点的各棵子树的叶子结点。对于下面的树，叶子结点的结点序列为CFGHKL.ABHDCLKJGEF（4）树中叶子结点遍历如果只有一个结点，则该结点就是叶子225.4树的遍历设m次树的标准存储形式的结点类型为：#defineMAXM10structnode{intdata;structnode*child[MAXM];};typedefstructnodeNODE;NODE*t;intm;//树的次数5.4树的遍历设m次树的标准存储形式的结点类型为：235.4树的遍历

两个前序遍历的算法：p.115r_preorder(t,m)用递归调用来实现对m次树t的前序遍历。pp.115-116s_preorder(t,m)用栈来帮助实现对m次树t的前序遍历，顺序存储的栈用来保存尚未完成遍历的子树的根结点的地址。5.4树的遍历两个前序遍历的算法：24Voids_preorder(t,m)NODE*t;Intm;{NODE*s[100]Inttop,I;if(t==Null)return;//空树,返回.s[0]=t;//根进栈top=1;//栈顶指针=1while(top>0){t=s[--top];//取栈顶(某根)printf(“%c”,t->data);for(I=m-1;I>=0;I--)//该根结点所有子树由后向前进栈if(t->chlid[I]!=NULL)s[top++]=t->chlid[I];}}Voids_preorder(t,m)255.4树的遍历按层次遍历的算法：p.116levorder(t,m)用队列来帮助实现对m次树t的层次遍历，算法中使用一个顺序存储的队列存放还没有处理的子树的根结点的地址（指针）。这里，队首指针head指向队首结点，队尾指针tail指向队尾结点的后面一个位置。5.4树的遍历按层次遍历的算法：265.5树的线性表示前面介绍的树结构，都是用指针来体现结点之间所存在的关系。但是，建立树的结构，需要按一定顺序逐一将结点输入计算机。这时的结点排列是线性的。于是，我们需要考虑怎样用线性的方法来表示一棵树。具体方法有：（１）层号表示（２）括号表示5.5树的线性表示前面介绍的树结构，都是用指针来体现结27１.树的层号表示定义结点层号：如果k是树中的一个结点，那么结点k的层号lev(k)为整数，且满足：（1）如果k’是k的子结点，那么lev(k’)>lev(k);（2）如果k’和k’’同是结点k的子结点，那么lev(k’)=lev(k’’)。p.117中间的树以及其层号表示。注意：结点层号和结点所在的层次是不同的。１.树的层号表示定义结点层号：28１.树的层号表示树的层号表示：（1）用一个二元组来表示结点，前一个元为层号，后一个元为结点键值。（2）所有结点的二元组按前序排列存放在一个二元组的数组中。１.树的层号表示树的层号表示：29１.树的层号表示二元组数组的数据结构描述：#defineMAXN100typedefstructdnode{intlev;intdata;}DNODE;DNODEa[MAXN];//存放层号表示的树intn;//树的结点个数１.树的层号表示二元组数组的数据结构描述：30１.树的层号表示举例：pp.117-118上的程序的功能是实现由树的层号表示建立一棵按扩充标准形式存储的m次树。对于某个结点来说，前面层号小的最近的结点是它的父结点；后面紧靠它、层号大的结点为它的子结点，再后面层号与子结点相同的结点为子结点的兄弟结点，直到出现层号小于或者等于它的结点。１.树的层号表示举例：31*lev_tree(a,m,n){if(n<1)return;root=(NODE*)malloc();root->lev=a[0].lev;root->data=a[0].data;处理根结点For(I=0;I<m;I++)root->child[I]=NULL;Root->parent=NULL;P=root;For(I=1;I<n;I++){q=(NODE*)malloc();q->lev=a[I].lev;q->data[I]=a[I].data;//创建新结点for(j=0;j<m;j++)q->child[j]=NULL;//当前结点儿子,清空;while(q->lev<=p->lev)p=p->parent;//找到P层号比Q的层号小,即找到Q的父亲q->parent=p;//认父亲;j=-1;while(p->chlid[++j]!=NULL;//找没有认领过儿子的域;p->chlid[j]=q;//认领儿子;p=q;//p指向新结点,重复下一步;}return(root);}

(0,a),(1,b),(2,d),(2,e),(3,h),(3,I),(2,f),(3,j),(1,c),(2,g),(3,k)*lev_tree(a,m,n)(0,a),(1,b),(2322.树的括号表示设T是一棵树，则其括号表示σT的规则为：（1）如果树T只有一个结点，则此结点就是它的括号表示（可直接用结点键值表示它）。（2）如果树T是由根结点A和子树T0，T1，…，Tm-1组成，则树T的括号表示σT为A（σT0，σT1，…，σTm-1）p.117中间的树的括号表示σT=A(σB,σC)=A(B(σD,σE,σF),C(σG))=A(B(D,E(σH,σI),F(σJ)),C(G(σK,σL)))=A(B(D,E(H,I),F(J)),C(G(K,L)))2.树的括号表示设T是一棵树，则其括号表示σT的规则为：332.树的括号表示树的括号表示，是一个字符串，将被存储在字符数组中，用“\0”标识括号表示结束。pp.119-120上的程序是实现由树的括号表示建立一棵按标准形式存储的m次树的程序。其中结点键值为英文字母。程序用一个栈存放正在建立的子树的根结点的地址。2.树的括号表示树的括号表示，是一个字符串，将被存储在字345.6二叉树二叉树的定义一个有限的结点集合，或为空；或由一个根结点及表示为根结点的左右子树的两个互不相交的结点集合所组成，而根结点的左右子树也是二叉树。如5.6二叉树二叉树的定义355.6二叉树二叉树与m次树的区别（1）二叉树可为空，但是m次树不能为空，至少有一个结点。（2）二叉树中的结点可有两棵子树（可能其中一棵或两棵为空），而m次树的结点可有若干子树。（3）在二叉树中每个结点的子树都是有序的，可用左、右子树来区别，而m次树的子树间（若不特别指定）是无序的。5.6二叉树二叉树与m次树的区别365.6二叉树3.把任意次树转换成相应的二叉树描述性方法：若任意结点k有子结点k0,k1,…,km-1，则转换后的二叉树的结点k，它的左子结点为k0，而其他结点ki+1作为结点ki的右子结点（i=0,1,…,m-2）。5.6二叉树3.把任意次树转换成相应的二叉树375.6二叉树原树的两个结点转换后的二叉树相应结点kk0k1k2k3kk0k1k2k3k01k02k03k01k02k035.6二叉树原树的两个结点转换后的二385.6二叉树把多棵有序树转换成一棵二叉树（1）方法若T=(T0,T1,…,Tm-1)是m棵树的序列，则得到与树T相对应的二叉树β(T)的法则为：如果m=0，那么β(T)为空的二叉树；如果m>0，那么β(T)的根结点就是树T0的根结点，β(T)的根结点的左子树是β(A0,A1,…,Ar-1),其中A0,A1,…,Ar-1是树T0的根结点的子树；β(T)的根结点的右子树是β（T1,T2,

…,Tm-1)。5.6二叉树把多棵有序树转换成一棵二叉树395.6二叉树把多棵有序树转换成一棵二叉树（2）举例p.123三棵三次树组成的有序树林变换成一棵对应的二叉树（3）性质如果T是有序树组成的树林，那么上面方法得到的与T相对应的二叉树β（T）是唯一的。5.6二叉树把多棵有序树转换成一棵二叉树405.6二叉树算法pp.123-124的beta()函数的功能是将三棵或三棵以下的三次树，用递归方法转化为一棵二叉树，返回这棵二叉树的根结点的地址。做法：（1）第一棵树的根结点变为二叉树的根结点；（2）第一棵树的根结点的子树用beta()转化成一棵二叉树，为新树的左子树；（3）第二棵和第三棵树用beta()转化成一棵二叉树，为新树的右子树。5.6二叉树算法415.7二叉树的遍历1.复习前序和后序遍历二叉树（1）前序遍历二叉树typedefstructnode{intdata;structnode*lchild,*rchild;}NODE;NODE*t;

5.7二叉树的遍历1.复习前序和后序遍历二叉树42前序遍历二叉树算法（递归）voidr_preorder(NODE*t){if(t!=NULL){printf(“%d”,t->data);r_preorder(t->lchild);r_preorder(t->rchild);}}前序遍历二叉树算法（递归）voidr_preor431.复习前序和后序遍历二叉树后序遍历二叉树voidr_posorder(t)NODE*t;{if(t!=NULL){r_posorder(t->lchild);r_posorder(t->rchild);printf(“%d”,t->data);}}1.复习前序和后序遍历二叉树后序遍历二叉树445.7二叉树的遍历中序遍历二叉树(取结点垂直投影)（1）做法首先按中序遍历根结点的左子树；然后访问根结点；最后按中序遍历根结点的右子树。5.7二叉树的遍历中序遍历二叉树(取结点垂直投影)452.中序遍历二叉树（2）中序遍历二叉树的递归算法voidr_midorder(t)NODE*t;{if(t!=NULL){r_midorder(t->lchild);printf(“%d”,t->data);r_midorder(t->rchild);}}2.中序遍历二叉树（2）中序遍历二叉树的递归算法462.中序遍历二叉树中序遍历二叉树的非递归算法pp.125-126函数s_midorder()使用“链接栈”，栈结点用于存放正在遍历的子树的根结点的地址。做法：（1）按前序顺序将结点一一进栈；（2）当栈顶结点的左子树为空或左子树处理完成时，遍历栈顶结点。2.中序遍历二叉树中序遍历二叉树的非递归算法475.7二叉树的遍历采用逆转链接指针的方法遍历二叉树这种方法不使用栈或递归。做法为：若当前结点为k，当需要向其左（或右）子树运动时，则逆转它的左（或右）指针改指k的父结点，以便为将来“回溯”准备路径。若回溯经过结点k，则修改指针恢复指向左（或右）子树。设立标志tag，若逆转的是右指针，则令tag=1。5.7二叉树的遍历采用逆转链接指针的方法遍历二叉树483.采用逆转链接指针的方法遍历二叉树pp.127-128invert_link_order(t,i)为实现对给定的二叉树用逆转指针的方法进行遍历的函数。参数t为指向需要遍历的树的根结点的指针。参数i为遍历方式的选项，若i=1，则按前序遍历；若i=2，则按中序遍历；若i=3，则按后序遍历。注意：树结点的结构多一个字段tag。3.采用逆转链接指针的方法遍历二叉树pp.127-128495.7二叉树的遍历4.二叉树的递归操作（1）复制一个二叉树p.129copy()（2）比较两棵二叉树是否等价p.130equiltree()5.7二叉树的遍历4.二叉树的递归操作505.8二叉树的顺序存储假如一棵二叉树建立以后，不需要再进行插入和删除操作，那么，我们可以将树结点依次顺序存储在一组连续的存储单元（如数组）中，这便是二叉树的顺序存储。具体方法有：按层次顺序存储按前序顺序存储（有附加左标志和右指针方法、附加两个标志方法等）5.8二叉树的顺序存储假如一棵二叉树建立以511.按层次顺序存储二叉树我们研究的这棵二叉树应满足：（1）除了最后一层外，每层都放满结点；（2）最后一层则结点从左到右逐一存放。用数学概念表示：设有n个结点的序列(k0,k1,…,kn-1)，令i=[log2(n+1)]，则将序列中的前面的(2i-1)个结点依次从上到下、从左到右放满前i层（即第0层到第i-1层），剩下的n-(2i-1)个结点则依次从左到右放在第i层上。1.按层次顺序存储二叉树我们研究的这棵二叉521.按层次顺序存储二叉树假若将n个结点的序列(k0,k1,…,kn-1)依次存放在一维数组a[MAXN]中，那么就有：（1）当0≤i≤[(n-2)/2]时，a[i]有左子结点a[2*i+1]；否则没有左子结点。（2）当0≤i≤[(n-3)/2]时，a[i]有右子结点a[2*i+2]；否则没有右子结点。（3）当1≤i≤n-1时，a[i]有父结点a[(i-1)/2]。（4）当0≤i≤[(n-3)/2]时，a[2*i+1]和a[2*i+2]有相同的父结点。1.按层次顺序存储二叉树假若将n个结点的序列(k0,535.8二叉树的顺序存储按前序顺序存储二叉树仅将二叉树的结点按前序存放在一个一维数组中，不能反映树中结点之间的关系。因此，需要附加一些信息。我们介绍下列两种存储方法：(1)附加左标志和右指针(2)附加两个标志5.8二叉树的顺序存储按前序顺序存储二叉树54（1）附加左标志和右指针的方法假设二叉树中的结点已按前序依次存放在数组中。数组元素有三个字段：ltag,data和rchild。如果树中的结点k有左子结点，那么它一定存放在结点k的后面。ltag是标志结点k后面是否有左子结点，若有，ltag=0；若无，ltag=1。如果结点k有右子结点，那么rchild中存放它右子结点的数组元素的下标；若无右子结点，则rchild=-1。举例：p.132ltagdatarchild（1）附加左标志和右指针的方法假设二叉树中的结点已按前序55（1）附加左标志和右指针的方法算法：#defineMAXN100typedefstructnode{intltag;chardata;intrchild;}NODE;NODEa[MAXN];introot=0;（1）附加左标志和右指针的方法算法：56（1）附加左标志和右指针的方法查找结点k（存放在a[p]中）的左子结点if(a[p].ltag==0)printf(“%c”,a[p+1].data);else<无左子结点，出错处理>（1）附加左标志和右指针的方法查找结点k（存放在a[p]中）57（1）附加左标志和右指针的方法查找结点k（存放在a[p]中）的右子结点if(a[p].rchild==-1)<无右子结点，出错处理>elseprintf(“%c”,a[a[p].rchild].data);（1）附加左标志和右指针的方法查找结点k（存放在a[p]中）58（1）附加左标志和右指针的方法查找结点k（存放在a[p]中）的按前序的前面结点if(p-1<0)<结点k没有按前序的前面结点，出错处理>elseprintf(“%c”,a[p-1].data);（1）附加左标志和右指针的方法查找结点k（存放在a[p]中）59（1）附加左标志和右指针的方法查找结点k（存放在a[p]中）的按前序的后面结点if(p+1>=n)<结点k没有按前序的后面结点，出错处理>elseprintf(“%c”,a[p+1].data);（1）附加左标志和右指针的方法查找结点k（存放在a[p]中）60（1）附加左标志和右指针的方法查找结点k（存放在a[p]中）的父结点if(p-1<0)<结点k没有父结点>elseif(a[p-1].ltag==0)printf(“%c”,a[p-1].data);else{for(q=p-1;a[q].rchild!=p;q--);printf(“%c”,a[q].data);}

（1）附加左标志和右指针的方法查找结点k（存放在a[p]中）61请画出下面数组的树0A60B31D-10E51G-11H-11C70F-11I-1请画出下面数组的树0A60B31D-10E51G-11H-162(2)附加两个标志的方法假设二叉树中的结点已按前序依次存放在数组中。数组元素有三个字段：ltag,data和rtag。

字段ltag是标志结点k是否有左子结点，若有，ltag=0；若无，ltag=1。字段rtag是标志结点k是否有右子结点，若有，rtag=0；若无，rtag=1。ltagdatartag(2)附加两个标志的方法假设二叉树中的结点63(2)附加两个标志的方法在存放二叉树的数组中，假如结点k的ltag=0，那么，紧跟在后面的是它的左子结点；当ltag=1，则结点k没有左子结点。问题是结点k的右子结点怎么找？寻找的原则：（1）右子结点的前一个结点的ltag=1，也就是说，ltag=1的结点的后一个结点一定是右子结点。（2）将右子结点与前面最靠近的rtag=0的结点配对，形成父子关系。试用上述原则画出p.134上数组表示的树。(2)附加两个标志的方法在存放二叉树的数组中64(2)附加两个标志的方法pp.134-135transfer(tree,n)功能是将存储在数组tree[]中n个结点表示的二叉树转换成按标准形式存储的二叉树。算法使用了栈stack[]，用于存放要找右子结点的父结点（rtag=0）的地址（指针）。栈顶下标top指向栈顶结点的上面一个位置。(2)附加两个标志的方法pp.134-135tra655.9穿线树和穿线排序用标准形式存储一棵有n个结点的二叉树，每个结点有两个指针，共有2*n个指针，但只有n-1个指针用于指向子结点，而n+1个指针是空的。这是一种浪费。于是可利用这些空指针，作为“穿线”。5.9穿线树和穿线排序665.9穿线树和穿线排序

1.穿线