清华数据结构

2024/2/1数据结构1第六章树

树形结构是一种重要的非线性结构，在我们的客观世界和现实生活中大量存在。

我们学院的组织结构：

在计算机领域也常用到树形结构。例如编译程序中用树表示源程序语法结构，数据库系统中用树组织信息等等。2024/2/1数据结构2我们的家谱：张林张源张明张亮张磊张京张群张华张平张维张力2024/2/1数据结构36.1树的概念1、树的定义：树(Tree)是n(n>0)个结点的有限集合T，

它满足如下条件：

(1)有且仅有一个称为根(Root)的结点。

(2)其余结点可分为m(m>=0)个互不相交的有限集合,

T1,T2,…,Tm,其中每个集合又是一棵树，并称其

为根的子树（Subtree）。这是一个递归定义。 有时n=0也称为空树。ABCDEFG集合1集合2集合3一、树的基本概念2024/2/1数据结构42、树的表示方法1）树形图法

2）嵌套集合法

3）广义表形式

4）凹入表示法(A(B,C(E,F),D(G))ABCDEFGABCEFDGABDGEFC2024/2/1数据结构51）结点的度(Degree)：为该结点的子树的个数。

2）树的度：为该树中结点的最大度数。3）终端结点(叶子)：度为零的结点。

4）非终端结点(分支结点)：度不为零的结点。

5）内部结点：除根结点之外的分支结点。ACDEFGB3、树结构的基本术语2024/2/1数据结构66）孩子(child)：结点的子树之根

双亲（parent):该结点称为孩子的双亲

兄弟(sibling):同一双亲的孩子

堂兄弟（cousin):双亲不同但其双亲处于同一层的结点7）路径(Path)：若树中存在一个结点序列k1,k2,…,kj,使得ki是ki+1的双亲(1<=i<j)，则称该结点序列是从ki到kj一条路径(Path)

路径长度：路径的长度为j-1,其为该路径所经过的边的数目。ACDEFGB2024/2/1数据结构79）结点的层次(Level)：从根算起，根结点的层次为1，其余结点的层次为其双亲的层次数加1。11）树的高度：树中结点的最大层次数称为树的高度或深度(Depth)。12）有序树：树中每个结点的各子树从左至右有次序之分，不能互换，这样的树称为有序树。8）祖先(Ancestor)

：若树中结点k到ks存在一条路径，则称k为ks的祖先

子孙（descendant):ks是k的子孙。ACDEFGB2024/2/1数据结构8

二、树型结构的逻辑特征：树中任一个结点都可以有零个或多个后继结点，但最多只能有一个前趋结点。有序树中兄弟结点之间从左至右有次序之分。13）森林：m(m>=0)棵互不相交的树的集合称为森林。关系：树森林删去一个树根加上一个树根ACDEFGB2024/2/1数据结构9

三、树的逻辑运算1.setnull(T):

置T为空树。2.root(T)或root(x):求树T或结点x所在树的根结点。3.parent(T,x):

求T中x结点的双亲，若x为根或x不在树中，

结果为空。4.child(T,x,i):

求T中x结点从左至右第i个孩子，若x为叶

子或x不在树中，结果为空。2024/2/1数据结构106.2二叉树6.2.1二叉树的概念一、二叉树的定义：

二叉树(BinaryTree)是n(n>=0)个结点的有限集，它或者是空集(n=0)或者由一个根结点和两棵互不相交的，分别称为根的左子树和右子树的二叉树组成。可以看出，二叉树的定义和树的定义一样，均为递归定义。2024/2/1数据结构11二、二叉树的五种基本形态：空二叉树只有一个根结点的二叉树右子树为空的二叉树左子树为空的二叉树左、右子树均非空的二叉树注意：二叉树中子树是有左右之分的，即使只有一棵子树，或为左子树，或为右子树，这一点与度为2的有序树不同。这不是二叉树这是二叉树2024/2/1数据结构126.2.2二叉树的性质性质1：二叉树第i层上的结点数目最多为2i-1(i>=1)

该性质可用数学归纳法证明。证明:

归纳基础:i=1时,有2i-1=20.因为第1层上只有一个根结点, 所以命题成立.

归纳假设:假设对所有的j(1<=j<i)命题成立,即第j层上至多 有2j-1个结点，证明j=i时命题也成立.

归纳步骤:根据归纳假设,第i-1层上至多有2i-2个结点。由于 二叉树的每一个结点至多有两个孩子,故第i层上的结点数, 至多是第i-1层上的最大结点数的2倍,即j=i时,该层上至多 有2*2i-2=2i-1个结点，故命题成立.2024/2/1数据结构13性质2：深度为k的二叉树至多有2k-1个结点(k>=1)

证明:

在具有相同深度的二叉树中，仅当每一层都含有最 大结点数时,其树中结点数最多。因此，利用性质1 可得,深度为k的二叉树的结点数至多为：

20+21+...+2k-1=2k-1

故命题成立.2024/2/1数据结构14性质3：任意二叉树中，若叶结点的个数为n0,度为2的结点数为n2，则n0=n2+1。

证明：设n1为二叉树T中度为1的结点数。因为二叉树中所 有结点的度均为小于或等于2，所以其结点总数为：

n=n0+n1+n2(6-1)

另一方面,1度结点有一个孩子,2度结点有两个孩子, 故二叉树中孩子结点的总数是n1+2*n2,但树中只有 根结点不是任何结点的孩子，故二叉树中的结点总 数又可表示为：

n=n1+2*n2+1(6-2)

由式(6-1)和(6-2)得

n0=n2+1

2024/2/1数据结构15两种特殊形态的二叉树：满二叉树和完全二叉树

深度为k且有2k-1个结点的二叉树称为满二叉树。－－若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。满二叉树1234567非完全二叉树123456完全二叉树234512024/2/1数据结构16两种特殊形态的二叉树：满二叉树和完全二叉树

深度为k且有2k-1个结点的二叉树称为满二叉树。－－对满二叉树的结点进行编号，约定编号从根结点起，自上而下，自左至右。－－深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应，则称之为完全二叉树。满二叉树1234567非完全二叉树123456完全二叉树234512024/2/1数据结构17根据定义:(1)满二叉树是完全二叉树,反之不成立;

(2)对于完全二叉树,若某结点无左孩子,则必无 右孩子,该结点为叶结点;证明：设深度为k，则根据性质2和完全二叉树的定义有

2k-1-1<n<=2k-1即2k-1<=n<2k

于是k-1<=log2n<k,又因为k是整数，所以k-1=

log2n

，

即k=log2n+1性质4：具有n个结点的完全二叉树的深度为

log2n

+1(

log2(n+1)

)2024/2/1数据结构18性质5：如果对一棵有n个结点的完全二叉树的结点按层次编号(即自上而下，自左至右)，则对任一结点i(1<=i<=n)，有

(1)如果i=1，则结点i是二叉树的根，无双亲；如果i>1,则其 双亲是编号为

i/2的结点。

(2)如果2*i>n,则结点i无左孩子；否则其左孩子是编号为2*i 的结点。

(3)如果2*i+1>n,则结点i无右孩子；否则其右孩子是编号为 2*i+1的结点。

(4)若i为奇数且不为1,则结点i的左兄弟的编号是i-1;否则,结点 i无左兄弟。

(5)若i为偶数且小于n,则结点i的右兄弟的编号是i+1;否则,结 点i无右兄弟。234512024/2/1数据结构196.2.3二叉树的存储1.顺序存储结构1）对于完全二叉树可以采用顺序存储结构(即一维数组)进行存储，编号为i的结点存放在第i个数组元素所分配的存储单元中，完全二叉树结点之间的逻辑关系通过数组元素的下标体现。完全二叉树abcde非完全二叉树abcdef012345abcde下标元素01234567abc*def下标元素“虚结点”占据的空间补设的“虚结点”2024/2/1数据结构202）对于非完全二叉树，通过补设一些“虚结点”，使得二叉树的结点的编号与完全二叉树相同，再进行顺序存储。每个“虚结点”都将占据一个数组元素存储单元。结论：非完全二叉树采用顺序存储结构会造成存储空间的浪费。2024/2/1数据结构21二叉树除了可以采用顺序存储结构实现存储外,还可以采用链式存储结构进行存储,与采用顺序存储结构相比,采用链式存储结构实现二叉树的存储显得更自然.1）链式存储结构中结点的结构:lchilddatarchild指向左孩子的指针域指向右孩子的指针域存放数据2、链式存储结构2024/2/1数据结构222）结点的存储描述:typedefstructnode

{datatypedata;

structnode*lchild,*rchild;

}bitree;bitree*root;所有类型为node的结点，再加上一个指向根结点的头指针root，就构成了二叉树的存储结构，称为二叉链表。lchilddatarchild指向左孩子的指针域指向右孩子的指针域存放数据2024/2/1数据结构23abcde

二叉树abcde^^^^^^root

二叉链表链式存储例：说明：1）一个二叉链表由头指针唯一确定。若二叉树为空，则root=NULL。2）在n个结点的二叉树中一共有2n个指针域，n+1个为空，n-1个非空。2024/2/1数据结构243）二叉链表是二叉树最常用的存储结构。还有其它链接方法，采用何种方法，主要取决于所要实施的各种运算频度。例:若经常要在二叉树中寻找某结点的双亲时，可在每个结点上再加一个指向其双亲的指针域parent，称为三叉链表。lchilddataparentrchildroot

三叉链表abcde^^^^^^^abcde

二叉树链式存储2024/2/1数据结构25特殊的，为了方便找到结点的双亲,还可以在结点结构中增加一个指向该结点双亲的指针域:dadalchildparentrchild左指针数据域双亲指针右指针2024/2/1数据结构26若二叉树中每一个结点均采用上述第一或第二种结构,由此便实现了二叉树的链式存储,这种存储结构又称为二叉链表或三叉链表。此外,还需引入一个指针变量,使其指向根结点.该指针变量说明如下:

bitree*root;abcde

二叉树abcde^^^^^^root

二叉链表链式存储root

三叉链表abcde^^^^^^^2024/2/1数据结构272）结点的存储描述:typedefstructnode

{datatypedata;

structnode*lchild,*rchild;

}bitree;bitree*root;所有类型为node的结点，再加上一个指向根结点的头指针root，就构成了二叉树的存储结构，称为二叉链表。lchilddatarchild指向左孩子的指针域指向右孩子的指针域存放数据2024/2/1数据结构283、二叉树的生成1）顺序存储结构非常简单：从终端上读入数据填入数组2）二叉链表的生成基本思想：按完全二叉树的层次顺序(非完全二叉树添加虚结点)，依次输入结点信息，若输入的结点不是虚结点，则建立一个新结点。若新结点是第一个结点，则令其为根结点；否则将新结点作为孩子链接到它的双亲结点上。如此重复下去，直至所有结点送完并以特殊字符结束。实现技巧：实现过程中引入一个指针队列，该队列中的每个元素指向相应结点。2024/2/1数据结构29事实上：先入队的结点其孩子必将先入队。因此front指针指向的队列元素所指向的结点为当前必须与其孩子建立链接的双亲结点，而rear指针指向的队列元素所指向的结点为当前必须与其双亲建立链接的孩子结点。当rear为偶数时，为左孩子，否则为右孩子。算法描述：

bitree*q[maxsize];/*队列q为bitree指针类型的数组*/

bitree*creattree()

{ charch;intfront,rear;bitree*root,*s;

root=NULL;/*置空二叉树*/

front=1;rear=0;/*置空队列*/

ch=getchar();

2024/2/1数据结构30前者简单，不在此讨论，这里仅说明后者的处理方法。基本思想：按完全二叉树的层次顺序(非完全二叉树添加虚结点)，依次输入结点信息，若输入的结点不是虚结点，则建立一个新结点。若新结点是第一个结点，则令其为根结点；否则将新结点作为孩子链接到它的双亲结点上。如此重复下去，直至所有结点送完并以特殊字符结束。算法在实现过程中引入一个指针队列，该队列中的每个元素指向相应结点。注意一个事实：先入队的结点其孩子必将先入队。因此front指针指向的队列元素所指向的结点为当前必须与其孩子建立链接的双亲结点，而rear指针指向的队列元素所指向的结点为当前必须与其双亲建立链接的孩子结点。当rear为偶数时，为左孩子，否则为右孩子。算法描述：

bitree*q[maxsize];/*队列q为bitree指针类型的数组*/

bitree*creattree()

{charch;intfront,rear;bitree*root,*s;while(ch!=‘#’)/*’#’为结束符号*/

{s=NULL;

if(ch!=‘@’)/*’@’为虚结点符号，不是虚结点时建立新结点*/

{s=malloc(sizeof(bitree));

sdata=ch;slchild=NULL;srchild=NULL;}

rear++;q[rear]=s;/*将虚结点指针或新结点地址入队*/

if(rear==1)root=s;

else{if(s&&q[front])/*孩子和双亲结点均不是 虚结点*/

if(rear%2==0)q[front]lchild=s;/*rear为 偶数，新结点是左孩子*/

elseq[front]rchild=s;

if(rear%2==1)front++;}/*结点Q[front]的孩子 处理完毕，出队列*/

ch=getchar();

}returnroot;

} 2024/2/1数据结构32while(ch!=‘#’)

{s=NULL;if(ch!=‘@’)/*’@’为虚结点符号，不是虚结点时建立新结点*/

{s=malloc(sizeof(bitree));sdata=ch;

slchild=NULL;srchild=NULL;}

rear++;q[rear]=s;/*将虚结点指针或新结点地址入队*/if(rear==1)root=s;

else{if(s&&q[front])/*孩子和双亲结点均不是虚结点*/

if(rear%2==0)q[front]lchild=s; elseq[front]rchild=s; if(rear%2==1)front++;}/*结点Q[front]出队列*/ch=getchar();

}returnroot;

} 2024/2/1数据结构33作业:6.26.36.46.52024/2/1数据结构346.3二叉树的遍历二叉树的遍历指的是沿某条搜索路径访问二叉树，对二叉树中的每个结点访问一次且仅一次。这里的“访问”实际上指的是对结点进行某种操作。(以下“访问”特指打印该结点信息)2、遍历方法的推导1、定义非空二叉树根结点D左子树L右子树RP3=63DLR

LDR

LRDDRL

RDL

RLD先左后右先右后左前序遍历中序遍历后序遍历2024/2/1数据结构351)前序遍历二叉树前序遍历算法：

先访问根结点，

再遍历左子树

最后遍历右子树3、遍历算法abcde前序遍历结果abdece的前序遍历前趋为de的逻辑前趋为b前序前序若二叉树非空2024/2/1数据结构36非空的二叉树可以分成三部份：根结点，左子树和右子树。因此，对二叉树的遍历可以分成三个子问题：访问根结点，遍历左子树，遍历右子树。若分别以D，L，R表示上述三个子问题，则对二叉树存在六种遍历次序：DLR，LDR，LRD，DRL，RDL，RLD。后三种与前三种对称，因此仅需讨论前三种。按照根结点在遍历过程中被访问的先后次序，DLR、LDR和LRD分别被称为前序、中序和后序遍历。1.前序遍历二叉树遍历过程：若二叉树非空，则先访问根结点，再前序遍历左子树，最后前序遍历右子树。对如下的二叉树，进行前序遍历，得到怎样的结果？2024/2/1数据结构37算法描述：

preorder(t)

bitree*t;

{if(t)

{printf(“\t%c”,tdata);

preorder(tlchild);

preorder(trchild);

}

}2)中序遍历二叉树中序遍历算法：若二叉树非空，

先中序遍历左子树，

再访问根结点，

最后中序遍历右子树2024/2/1数据结构38abcde中序遍历结果dbeac算法描述：

inorder(t)

bitree*t;

{if(t)

{inorder(tlchild); printf(“\t%c”,t->data);

inorder(trchild);

}

}2024/2/1数据结构393）后序遍历二叉树后序遍历算法：若二叉树非空，

先后序遍历左子树，

再后序遍历右子树，

最后访问根结点。abcde后序遍历结果debca2024/2/1数据结构40算法描述：

postorder(t)

bitree*t;

{if(t)

{

postorder(tlchild);

postorder(trchild);

printf(“\t%c”,t->data);}

}2024/2/1数据结构41说明:1)递归算法的终止条件是二叉树为空.2)三个算法具有相同的搜索路径:

该路线从根结点出发,逆时针沿二叉树外缘移动,对每个结点均途径三次.若访问结点均是在第一次经过结点时进行的,则是前序遍历,若访问结点均是在第二次(或第三次)经过结点时进行的,则是中序遍历(或后序遍历).abcdefØØØØØØØ第一次：abdcef第二次：dbaecf第三次：dbefcaabdddbbaceeecfffca2024/2/1数据结构423）遍历序列的前趋、后继的称谓问题：对于上述三种遍历序列，均在某结点的前趋和后继之前加上遍历次序的名称。abcdefØØØØØØØ例：对于C结点，其前序前趋结点是D,其前序后继结点是E。 中序前趋结点是E,中序后继结点是F,

后序前趋结点是F,后序后继结点是A,但是就该树的逻辑结构而言，C的前趋结点是A，后继结点是E和F。第一次：abdcef第二次：dbaecf第三次：dbefca程序跟踪见动态演示1)Inorder(t=&a)2)Inorder(t=&b)1)2)Inorder(t=&d)1)2)Inorder(t=NULL)

1 2 3ae

f

cd

b

ttttinorder(t)

bitree*t;

1)、{if(t)

{

2)、

inorder(tlchild);

3)、

printf(“\t%c”,t->data);

4)、

inorder(trchild);

}

5)、

}4)Inorder(t=NULL)1)Inorder(t=&a)2)Inorder(t=&b)1)2)Inorder(t=&d)1)2)Inorder(t=NULL)1)3)5)打印d

1 2 3ae

f

cd

b

tttinorder(t)

bitree*t;

1)、{if(t)

{

2)、

inorder(tlchild);

3)、

printf(“\t%c”,t->data);

4)、

inorder(trchild);

}

5)、

}1)Inorder(t=&a)2)Inorder(t=&b)1)2)Inorder(t=&d)1)2)Inorder(t=NULL)1)3)2)4)Inorder(t=NULL)5)1)5)打印d

1 2 3ae

f

cd

b

tinorder(t)

bitree*t;

1)、{if(t)

{

2)、

inorder(tlchild);

3)、

printf(“\t%c”,t->data);

4)、

inorder(trchild);

}

5)、

}打印b3)1)Inorder(t=&a)2)Inorder(t=&b)1)2)Inorder(t=&d)1)2)Inorder(t=NULL)1)3)5)4)Inorder(t=NULL)5)1)5)打印d4)Inorder(t=NULL)

1 2 3ae

f

cd

b

tttinorder(t)

bitree*t;

1)、{if(t)

{

2)、

inorder(tlchild);

3)、

printf(“\t%c”,t->data);

4)、

inorder(trchild);

}

5)、

}inorder(t)

bitree*t;

1)、{if(t)

{

2)、

inorder(tlchild);

3)、

printf(“\t%c”,t->data);

4)、

inorder(trchild);

}

5)、

}5)1)5)

1 2 3ae

f

cd

b

t打印b3)1)Inorder(t=&a)2)Inorder(t=&b)1)2)Inorder(t=&d)1)2)Inorder(t=NULL)1)3)5)4)Inorder(t=NULL)5)1)5)打印d4)Inorder(t=NULL)3)

1 2 3打印aae

f

cd

b

ttinorder(t)

bitree*t;

1)、{if(t)

{

2)、

inorder(tlchild);

3)、

printf(“\t%c”,t->data);

4)、

inorder(trchild);

}

5)、

}打印b3)1)Inorder(t=&a)2)Inorder(t=&b)1)2)Inorder(t=&d)1)2)Inorder(t=NULL)1)3)5)4)Inorder(t=NULL)5)1)5)打印d4)Inorder(t=NULL)5)1)5)

1 2 3打印aae

f

cd

b

tinorder(t)

bitree*t;

1)、{if(t)

{

2)、

inorder(tlchild);

3)、

printf(“\t%c”,t->data);

4)、

inorder(trchild);

}

5)、

}4)Inorder(t=&c)打印b3)1)Inorder(t=&a)2)Inorder(t=&b)1)2)Inorder(t=&d)1)2)Inorder(t=NULL)1)3)5)4)Inorder(t=NULL)5)1)5)打印d4)Inorder(t=NULL)5)1)5)3)1)4)Inorder(t=NULL)5)1)5)3)打印b4)Inorder(t=NULL)5)1)5)3)打印a4)Inorder(t=&c)Inorder(t=&a)2)Inorder(t=&b)1)2)Inorder(t=&d)1)2)Inorder(t=NULL)5)1)2)4)5)3)Inorder(t=&e)1)2)4)5)3)Inorder(t=NULL)1)5)打印eInorder(t=NULL)1)5)Inorder(t=&f)1)2)4)5)3)Inorder(t=NULL)1)5)打印fInorder(t=NULL)1)5)打印c1)3)5)打印ddbaecf中序序列

1 2 32024/2/1数据结构51中序遍历(LDR)前提:二叉树非空(1)中序遍历左子树(2)访问根结点(3)中序遍历右子树后序遍历(LRD)前提:二叉树非空(1)后序遍历左子树(2)后序遍历右子树(3)访问根结点前序遍历(DLR)前提:二叉树非空(1)前序遍历左子树(2)访问根结点(3)前序遍历右子树2024/2/1数据结构52bØØØØØØØfcaed

从根结点出发，逆时针沿着二叉树外缘移动，对每个结点均途经三次。

1 2 3bØØØØØØØfcaed

Inorder(t=NULL)

打印b

Inorder(t=NULL)

打印a

Inorder(t=&c)Inorder(t=&a)

Inorder(t=&b)

Inorder(t=&d)

Inorder(t=NULL)

打印d

2024/2/1数据结构54bØØØØØØØfcaedaceeecfffcaabdddbb第一次经过的结点:第二次经过的结点:第三次经过的结点:前序序列中序序列后序序列abdecfdbacefdbecfa2024/2/1数据结构55bØØØØØØØfcaedtt&a&b&dtt&a&b2024/2/1数据结构56算法描述如下：

typedefbitree*datatype;

typedefstructnode

{datatypedata;

structnode*next;

}linkstack;

inorder(t)

bitree*t;

{linkstack*top;

top=NIL;

do{while(t!=NIL){top=pushlstack(top,t);t=tlchild;}

if(top!=NIL){top=poplstack(top,&t);printf("%d\t",tdata);

t=trchild;}

}while((top!=NIL)||(t!=NIL));

}算法思想：采用非递归算法实现中序遍历必须引入堆栈。具体实现步骤为…….。例：中序遍历的非递归算法3、遍历的非递归算法2024/2/1数据结构574、遍历的非递归算法例：中序遍历的非递归算法算法思想：采用非递归算法实现中序遍历必须引入堆栈。具体实现步骤为…….。置栈s为空t为空？t入栈

t=t->lchild栈为空？t=s->top,出栈

打印t->data

t=t->rchild结束NNYYtypedefbitree*datatype;

typedefstructnode

{datatypedata;

structnode*next;

}linkstack;

inorder(t)

bitree*t;

{linkstack*top;

top=NULL;

do{while(t!=NULL){top=pushlstack(top,t); t=tlchild;}

if(top!=NULL){top=poplstack(top,&t); printf("%d\t",tdata);

t=trchild;}

}while((top!=NULL)||(t!=NULL));

}算法描述如下：2024/2/1数据结构59考虑：1、遍历的第一个结点和最后一个结点的特征?2、前序序列、中序序列、后序序列，已知任意两者可以确定第三者吗?3、遍历算法中对每个结点进行一次访问操作，访问操作可以是多种形式及多个操作。－》得到求解许多问题的算法。2024/2/1数据结构60根结点最右下叶结点最左下结点最右下结点最左下叶结点根结点第一个结点最后一个结点前序遍历中序遍历后序遍历考虑：1、遍历的第一个结点和最后一个结点的特征?2024/2/1数据结构61考虑：2、前序序列、中序序列、后序序列，已知任意两者可以确定第三者吗?前序、中序二叉树后序、中序前序、后序二叉树二叉树后序前序2024/2/1数据结构62考虑：3、遍历算法中对每个结点进行一次访问操作，访问操作可以是多种形式及多个操作。－》得到求解许多问题的算法。例： －－打印所有叶子结点 －－求二叉树中的结点数

2024/2/1数据结构63考虑：4、二叉树的遍历只有这六种方法吗?NO!2024/2/1数据结构64例：给定一棵采用二叉链表存储的二叉树，编写按层次遍历二叉树的算法，同层的结点按从左至右的次序访问。算法思想：根据题义可知，先被访问的结点，其孩子结点也将被先访问，因此，可以使用一个指针队列。初始时将根结点指针入队，只要队列不空，则出队一个元素，对其指向结点进行访问，并将其孩子结点指针入队，如此反复，直到队列空为止。算法描述：

typedefbitree*datatype;

typedefstruct

{datatypedata[maxsize];

intfront,rear;

}sequeue;

lorder(t)

bitree*t;

{sequeue*sq;/*sq为循环队列指针*/

bitree*x

setnull(sq);

if(t!=NULL)

{enqueue(sq,t);

while(!empty(sq))

{x=dequeue(sq);

printf("%d\t",xdata);

if(xlchild!=NULL)enqueue(sq,xlchild);

if(xrchild!=NULL)enqueue(sq,xrchild);

}

}

}2024/2/1数据结构66作业:6.7

6.86.126.152024/2/1数据结构676.4线索二叉树遍历二叉树是以一定规则将二叉树中的结点排成一个线性序列,将一个非线性结构线性化问题单单依靠二叉树并不能直接得到结点在任一序列中的前趋和后继,这种信息只有在动态遍历中才能得到.所以某次遍历得到的信息,下次再用时,仍要重新遍历.考虑如何保存这种在遍历过程中得到的信息?1.简单的方法:在每个结点上增加指针域fwd和bkwd,分别指示结点在任一次序遍历时,得到的前趋和后继。缺点：将大大降低存储空间的利用率。2024/2/1数据结构686.4线索二叉树问题单单依靠二叉树并不能直接得到结点在任一序列中的前趋和后继,这种信息只有在动态遍历中才能得到.所以某次遍历得到的信息,下次再用时,仍要重新遍历.一、如何保存在遍历过程中得到的信息?1.方法A:

在每个结点上增加指针域fwd和bkwd,分别指示结点在任一次序遍历时,得到的前趋和后继。缺点：将大大降低存储空间的利用率。2024/2/1数据结构692.方法B:利用已有的指针域存放:

利用二叉链表上的n＋1个空指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针，由此得到的二叉链表称为线索链表，相应地采用这种存储结构的二叉树称为线索二叉树。线索链表中结点的结构：

lchildltagdatartagrchildltag=0表示lchild为指向结点左孩子的指针

ltag=1表示lchild为指向结点前趋的左线索rtag=0表示rchild为指向结点右孩子的指针rtag=1表示rchild为指向结点后继的右线索typedefstructnode

{intltag,rtag;

datatypedata;

structnode*lchild,*rchild;

}bithptr;

bithptr*p;2024/2/1数据结构70n个结点的二叉链表中含有n+1个空指针域，可以充分利用这些空指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针，以提高遍历或查找结点在指定次序下的前趋和后继运算的效率。由此得到的二叉链表称为线索链表，相应地采用这种存储结构的二叉树称为线

索二叉树。线索链表中结点的结构：

lchildltagdatartagrchildltag=0表示lchild为指向结点左孩子的指针

ltag=1表示lchild为指向结点前趋的左线索rtag=0表示rchild为指向结点右孩子的指针rtag=1表示rchild为指向结点后继的右线索2.利用已有的指针域存放:2024/2/1数据结构71abcde中序线索二叉树dbeacNULLNULLabcde0010011111中序线索链表线索化(建立某次序线索二叉树的步骤2，步骤1类似于二叉链表的建立过程）:将二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化。具体地体现在将二叉链表变为线索链表。2024/2/1数据结构72二、如何对二叉树进行线索化？1、线索化的实质：是将二叉树的空指针改为指向前趋或后继的线索，而前趋或后继的信息只有在遍历时才能得到，因此线索化的过程即为在遍历的过程中修改指针的过程。2、技巧：1）该算法与遍历算法类似，区别仅在于访问根结点 时所作的处理不同

2）附设一个指针pre始终指向刚刚访问过的结点

3）指针p指向当前访问的结点，pre指向它的前趋，

相应地p指向的结点为pre指向结点的后继。2024/2/1数据结构734、后序遍历建立线索化链表的算法如下：A:若结点*P有空指针域，则将相应标志置为1；B:若*P有前趋结点*pre(pre!=Null)则：（1）若结点*pre的右线索标志已建立（即pre－>rtag=＝1）,

则令pre－>rchild为指向其后继结点*p的右线索。（2）若结点*p的左线索标志已建立（即p－>ltag==1),则

令p－>lchild为指向其前趋*pre的左线索。C:

将pre指向刚刚访问过的结点*p(即pre=p),下次访问新结点*p时，*pre为其前趋结点。3、线索化算法中，访问当前根结点*P所做的处理是：2024/2/1数据结构74将二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化，具体地体现在将二叉链表变为线索链表。接下来的问题是如何对二叉树进行线索化？线索化的实质是将二叉树的空指针改为指向前趋或后继的线索，而前趋或后继的信息只有在遍历时才能得到，因此线索化的过程即为在遍历的过程中修改指针的过程。为了记下遍历过程中访问结点的先后关系，附设一个指针pre始终指向刚刚访问过的结点，若指针p指向当前访问的结点，则pre指向它的前趋，相应地p指向的结点为pre指向结点的后继。abcde中序线索二叉树dbeacNULLNULLabcde0010011111中序线索链表该算法与遍历算法类似,区别仅在于访问根结点时所做的处理不同.线索化算法中，访问当前根结点*P所做的处理是： 1

若结点*P有空指针域，则将相应标志置为1；2

若*P有前趋结点*pre(*pre!=Null)则：（1）若结点*pre的右线索标志已建立（即pre－>rtag=＝1）,

则令pre－>rchild为指向其后继结点*p的右线索。

（2）若结点*p的左线索标志已建立（即p－>ltag==1),则令

p－>lchild为指向其前趋*pre的左线索。3将pre指向刚刚访问过的结点*p(即pre=p),下次访问新结点*p时，*pre为其前趋结点。后序遍历建立线索化链表的算法如下：typedefstructnode

{intltag,rtag;

datatypedata;

structnode*lchild,*rchild;

}bithptr;

bithptr*pre;/*全局变量，初值应为NULL*/

afterthread(p)

bithptr*p;

{if(p!=NULL){afterthread(plchild);

afterthread(prchild);

if(plchild==NULL)pltag=1;

if(prchild==NULL)prtag=1;

if(pre!=NULL){if(prertag==1)prerchild=p;

if(pltag==1)plchild=pre;}

pre=p;

}

}2024/2/1数据结构772024/2/1数据结构78三、线索二叉树的运算：１、查找某结点*P在指定次序下的前趋和后继结点：中序后继：分两种情况（１）若*p的右子树为空，rtag==1,则p－>rchild为右线索，直接指向*p的中序后继结点。（２）若*p的右子树非空，rtag==0,则*p的中序后继必是右子树中第一个中序遍历到的结点，即其右子树中最左下的结点。N0R1０R２０Rk1pＲ１Ｒ２ＲkN1）中序线索二叉树2024/2/1数据结构79中序线索二叉树中求中序后继结点的算法：bithptr*INORDERNEXT(P)

bithptr*p{bithptr*qif(p－>rtag==1)return(p－>rchild);else

{ q=p－>rchild;

while(q－>ltag==0)q=q－>child;

}

return(q);}2024/2/1数据结构802024/2/1数据结构81结点*P的左子树非空时，其中序前趋结点是RkpＲ１Ｒ２ＲkN中序前趋：（１）如果ltag==1，没有左孩子，lchild指向前趋结点。（２）如果ltag==0,有左孩子，中序前趋应是左子树中最后一个遍历的结点，所以应是左子树中最右下的结点。R1R２RkN０qp0012024/2/1数据结构822024/2/1数据结构83结论1：若结点*P的左（右）子树非空，则*P的中序前趋（后继），是顺着链域向下找的，和在非线索二叉链表中是一样的.

但是当左（右）子树为空时，在我们的算法中一条语句就可以用线索找到前趋（后继），而在普通的二叉树中则很难。这是因为中序线索都是指向其祖先的，而二叉链表中没有向上的链接。因此必须从根结点开始中序遍历，才能找到*P的中序前趋（后继）。

但是，线索对于查找指定结点的前序前趋和后序后继却没有帮助。2024/2/1数据结构84在后序线索二叉树中，查找指定结点*P的后序前趋的规律：1

若*P的左子树为空，则P—>lchild是前趋线索，指示其后序前趋结点:H—>BF—>G。2

若左子树非空，则（1）当*P的右子树非空时，*P的右孩子是其后序前趋。（2）当*P的右子树为空时，其左孩子是其后序前趋。ABCDEFGHI2）后序线索二叉树2024/2/1数据结构85在后序线索二叉树中，查找指定结点*P的后序后继的规律：2若*P的右子树非空

（1）若*P是根，则后继为空。

（2）若*P是双亲的右孩子，则*P的后序后继结点就是 双亲结点。

（3）若*P是双亲的左孩子，但*P无右兄弟时，*P的 后序后继是其双亲。若有右兄弟，则右兄弟子树 中第一个被访问到的结点是后继。1若*P的右子树为空，则P—>rchild是后继线索，指示其后序后继结点2024/2/1数据结构86结论2：后序线索二叉树中，找*P的前趋容易，从*P出发就能找到，找后继难，仅当rtag==1时，线索可得到；否则，必须知道双亲才能找到后继。如果没有指向双亲结点的指针，就必须从根开始后序遍历，才能找到*P的后序后继。

类似的,在前序线索二叉树中，找某一点*P的前序后继很简单,仅从*P出发就可以找到;但找其前序前趋也必须知道*P的双亲结点,当树中结点ltag==0且未设双亲指针时,同样要进行从根开始的前序遍历才能找到结点*P的前序前趋.2024/2/1数据结构87回顾一下讨论过的两个问题：如何将二叉树变为线索二叉树：实现思想按某种次序遍历二叉树，在遍历过程中用线索代替空指针域。为此分别介绍了按前序，中序，后序遍历二叉树来生成线索二叉树的过程。线索二叉树上的运算1。若线索二叉树已建立，如何查找某结点的前趋和后序结点为此分别介绍了在前序，中序，后序三种线索二叉树中查找某结点的前趋和后继结点。例：有下列一棵二叉树；ABCDEFG前序序列ABDGCEF中序序列BGDAECF后序序列GDBEFCA2024/2/1数据结构88ABCDEFGNULLABCDEFGNULLNULLABCDEFGNULL前序中序后序2024/2/1数据结构892、遍历线索二叉树

遍历二叉树：指按某种路径对树中结点访问且仅访问一次。遍历线索二叉树：从某次序下的开始结点出发，反复找到该结点在该次序下的后继，直至终端结点。算法要点：（1）如果线索二叉树非空，则做（2），否则结束。

（2）找到某次序下的开始结点。（3）访问该结点。（4）找到该结点在该次序下的后继。（5）不是空则转（3），否则结束2024/2/1数据结构90遍历前序线索二叉树Travelpre(bithptr*p){if(p!=null){do{printf(“%d\n”,p-->data);p=preordernext(p);/*找*p的前序后继结点*/}while(p!=null);}}2024/2/1数据结构91遍历中序线索二叉树Traverseinthread(bithptr*p){if(p!=null){while(p-->ltag==0)/*找中序序列的

p=p-->lchild;

开始结点*/do {printf(“%d\n”,p-->data);

p=inordernext(p);}while(p!=null);}}2024/2/1数据结构92遍历后序二叉树Traverpost(bithptr*p)

{if(p!=null){while((p-->ltag==0)||(p-->rtag==0)){if(p-->ltag==0)p=p-->lchild;

elsep=p-->rchild;

}do{printf(“%d\n”,p-->data); p=postordernext(p);

}while(p!=null);}}2024/2/1数据结构933、线索二叉树的插入线索二叉树的优点：查找和遍历优于非线索树。线索二叉树的缺点：插入和删除不仅要修改指针，

还要修改线索。线索二叉树的插入和删除也分为前序，中序和后序，我们仅讨论中序线索二叉树的插入。中序的插入分两种情况：

1.将新结点*q插入到中序线索二叉树中*p和*p的右子树之间（插到右边）。２.将新结点*q插入到中序线索二叉树中*p和*p的左子树之间（插到左边）。现在开始讨论第一种情况——插入后*q是*p右子树的根（a)*p的右指针域存放的是后继线索，即p-->rtag=１，中序后继结点的指针为p-->rchild。（b)*q插入后.(1)*q为叶结点，有两个空指针域用来存放前趋和后继线索*q插入到*p和*p后继之间

*q的中序前趋为*p结点q-->ltag=1,q-->lchild=p*q的中序后继为*p的原后继结点p-->rchildq-->rtag=1,q-->rchild=p-->rchild,q--rtag=p-->rtag

(2)*q成为*p原来后继的前趋s=p-->rchild;if(s-->ltag==1)s-->lchild=q;(3)*q成为*p的新右孩子p-->rtag=0,p-->rchild=q;（一）若*p无右子树时2024/2/1数据结构95现在开始讨论第一种情况——插入后*q是*p右子树的根（一）若*p无右子树时（a)*p的右指针域存放的是后继线索，即p-->rtag=１，中序后继结点的指针为p-->rchild。……..（b)*q插入后……..(1)*q为叶结点，有两个空指针域用来存放前趋和后继线索*q插入到*p和*p后继之间

*q的中序前趋为*p结点q-->ltag=1,q-->lchild=p*q的中序后继为*p的原后继结点p-->rchildq-->rtag=1,q-->rchild=p-->rchild,q--rtag=p-->rtag

(2)*q成为*p原来后继的前趋s=p-->rchild;if(s-->ltag==1)s-->lchild=q;(3)*q成为*p的新右孩子p-->rtag=0,p-->rchild=q;2024/2/1数据结构96(二)若*p中有右子树(a)*p的右指针存放的是右孩子的指针,即p-->rtag=0,右孩子指针为p-->rchild(b)*q插入后(1)*q为非叶结点,左子树为空,成为*p右子树中最左下的结点，*p的后继成为*q的后继。q-->ltag=1;q-->lchild=p;q-->rtag=0;q-->rchild=p-->rchild;q-->rtag=p-->rtag;(2)*q成为原*p后继的前趋

s=INORDERNEXT(P)if((s!=null)&&(s-->ltag==1))s-->lchild=q;(3)*q成为*p的新右孩子p-->rtag=0,p-->rchild=q;2024/2/1数据结构97(二)若*p中有右子树(a)*p的右指针存放的是右孩子的指针,即p-->rtag=0,右孩子指针为p-->rchild(b)*q插入后(1)*q为非叶结点,左子树为空,成为*p右子树中最左下的结点，*p的后继成为*q的后继。q-->ltag=1;q-->lchild=p;q-->rtag=0;q-->rchild=p-->rchild;q-->rtag=p-->rtag;(2)*q成为原*p后继的前趋

s=INORDERNEXT(P)if((s!=null)&&(s-->ltag==1))s-->lchild=q;两种情况统一*q插入后，*q的左子树均为空，也就是说*q是*p右子树最左下的结点。插入后，*p和其后继之间要修改指针（包括*q的指针，*p的指针，*p原后继的指针)(3)*q成为*p的新右孩子p-->rtag=0,p-->rchild=q;2024/2/1数据结构98INSERTRIGHT(p,q)/*在结点*p和*p的右子树之间插入*q*/bithptr*p,*q{bithptr*s;s=INORDERNEXT(P);q-->ltag=1;q-->lchild=p;q-->rtag=p-->rtag;q-->rchild=p-->rchild;p-->rtag=0;p-->rchild=q;if((s!=null)&&(s->ltag==1))s-->lchild=q;}程序如下：2024/2/1数据结构99两种情况统一*q插入后，*q的左子树均为空，也就是说*q是*p右子树最左下的结点，是*p的新的直接后继。插入后，要修改指针（包括*q的指针，*p的指针，*p原后继的指针)2024/2/1数据结构100INSERTRIGHT(p,q)/*在结点*p和*p的右子树之间插入*q*/bithptr*p,*q{bithptr*s;s=INORDERNEXT(P);

q-->ltag=1;q-->lchild=p;

q-->rtag=p-->rtag;q-->rchild=p-->rchild;

p-->rtag=0;p-->rchild=q;if((s!=null)&&(s->ltag==1))s-->lchild=q;}程序如下：第二种情况：插入*p与其左子树之间：（一）若*p无左子树*p的左指针域存放的是前趋线索，即p-->ltag=1,p-->lchild=s,

中序前趋结点指针为s;(b)*