数据结构-树课件

引言在前面几章里讨论的数据结构都属于线性结构，线性结构的特点是逻辑结构简单，易于进行查找、插入和删除等操作，主要用于对客观世界中具有单一的前驱和后继的数据关系进行描述。而现实中的许多事物的关系并非如此简单，如人类社会的族谱、各种社会组织机构以及城市交通、通讯等，这些事物中的联系都是非线性的，采用非线性结构进行描绘会更明确和便利。所谓非线性结构，是指在该结构中至少存在一个数据元素，有两个或两个以上的直接前驱（或直接后继）元素。树结构和图结构是非常重要的非线性结构。.第六章树和二叉树本章内容6.1树的定义和基本术语6.2二叉树6.2.1二叉树的定义及基本运算6.2.2二叉树的性质6.2.3二叉树的存储结构6.3遍历二叉树和线索二叉树6.3.1遍历二叉树6.3.2线索二叉树6.4树和森林6.4.1树的存储结构6.4.2森林与二叉树的转换及遍历6.6赫夫曼树及应用6.6.1赫夫曼树（最优二叉树）6.6.2赫夫曼编码.6.1树树是n个结点的有限集合(可以是空集)，在任一棵非空树中：

（1）有且仅有一个称为根的结点。

（2）其余结点可分为互不相交的子集，而且这些子集本身又是一棵树，称为根的子树。JIACBDHGFEKLM.从逻辑结构看：

1）树中只有树根没有父结点；

2）除根外，其余结点都有且仅一个父结点；

3）树中的结点，可以有零个或多个孩子结点；

4)没有孩子的结点称为叶子结点，或终端结点；

5）除根外的其他结点，都存在唯一一条从根到该结点的路径；JIACBDHGFEKLM.树的基本术语树的结点：包含一个数据元素及若干指向子树的分支；孩子结点：结点的子树的根称为该结点的孩子；父结点：B是A的孩子，则A是B的父亲；兄弟结点：同一双亲的孩子结点；堂兄弟结点：其父结点在同一层上的结点；祖先结点:

从根到该结点所经分支上的所有结点；子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙；结点的度:

结点的孩子数目JIACBDHGFEKLM.树的基本运算找树的根结点求树的高度找指定结点的父结点找指定结点的孩子结点在树中插入、删除一个结点遍历树......JIACBDHGFEKLM.树的表示JIACBDHGFEKLMGCKLEFBMHJIDA(a)(A(B(E(k,L),F),C(G),D(H(M),I(),J())))(b).6.2二叉树二叉树的定义：二叉树要么为空，要么由根结点、左子树和右子树组成。左、右子树本身也是二叉树。注意：二叉树的子树有严格的左右之分，而树没有。ACBFEDG.二叉树的子树要区分左子树和右子树，即使只有一棵子树也要进行区分。这是二叉树与树的最主要的差别。下面列出了二叉树的5种基本形态，(c)和（d）是不同的两棵二叉树。(a)空二叉树AABABACB(b)只有根的二叉树(c)根和左子树(d)根和右子树(e)根和左右子树二叉树的5种基本形式.6.2.2二叉树的性质性质1

在二叉树的第i层上至多有2i-1个结点性质2

深度为k的二叉树至多有2k-1个结点性质3任何一个二叉树中度为2的结点数目(n2)比度为0的结点数目(n0)少1，即n2＝n0-1。GKJCFABEIHD.6.2.2二叉树的性质

性质3任何一个二叉树中度为2的结点数目(n2)比度为0的结点数目(n0)少1，即n2＝n0-1。证明：设二叉树上叶结点数为n0，单分支结点数为n1，双分支结点数为n2，则总结点数=n0+n1+n2。在一棵二叉树中，所有结点的分支数(即度数)应等于单分支结点数加上双分支结点数的2倍，即总的分支数=n1+2n2。由于二叉树中除根结点以外，每个结点都有惟一的一个分支指向它，因此二叉树中：总的分支数=总结点数-1。由上述三个等式可得：n1+2n2=n0+n1+n2-1

即：n0=n2+1.满二叉树和完全二叉树高度为3的满二叉树高度为3的一个完全二叉树高度为3的一个完全二叉树.完全二叉树高度为3的完全二叉树(a)(b)(c)(d).满二叉树和完全二叉树高度为3的满二叉树高度为3的一个完全二叉树123456712345.二叉树的性质(续)性质4一个有n个结点的完全二叉树的高度H＝[log(n)]+1。证明：设具有n个结点的完全二叉树的深度为h，则根据性质3：深度为h的二叉树至多有2h-1个结点，因此，n<=2h-1另外，深度为h的完全二叉树的结点数一定大于2h-1-1，即n>=2h-1综上，2h-1<=n<2h，或

h-1<=log2n<h即h=

log2n

+1或

log2n+1

证毕。.二叉树的性质(续)性质5完全二叉树中的某结点编号为i，则1)若有左孩子，则左孩编号为2i2）若有右孩子，则右孩子结点编号为2i+13）若有双亲，则双亲结点编号为[i/2].6.2.3二叉树的顺序存储二叉树的顺序存储指的是用元素在数组中的下标表示一个结点与其孩子和父结点的关系.完全二叉树的顺序存储EDCFABABCDEF123456789101112#defineMAX_TREE_SIZE100typedefTelemTypeSqBiTree[MAX_TREE_SIZE];SqBiTreebt;.二叉树的顺序存储非完全二叉树的顺序存储EGFCDABABCDEFG12345678910111213141516非完全二叉树不适合进行顺序存储.二叉树的链式存储一般用二叉链表存储二叉树(每个结点有两个指针域)EGFCDABA∧B∧CE∧D∧∧F∧∧G∧rootLchilddataRchildtypedefstructBiTNode{TElemTypedata;structBiTNode*Lchild,*Rchild;}BiTNode,*BiTree;.二叉树的链式存储三叉链表存储(每个节点有三个指针域)EGFCDABA∧∧BCE∧D∧FG∧root∧∧∧∧LchilddataRchildParent.6.3遍历二叉树和线索二叉树任何一个非空的二叉树都由三部分构成DLR根结点根的左子树根的右子树树的遍历是访问树中每个结点仅一次的过程。遍历可以被认为是把所有的结点放在一条线上，或者将一棵树进行线性化的处理。.6.3.1二叉树的遍历先左后右：DLR，LDR，LRDDLR根结点根的左子树根的右子树先右后左：DRL，RDL，RLD.先序遍历DLR：访问根结点、先序遍历左子树、先序遍历右子树DLR123.先序遍历DLR：访问根结点、先序遍历左子树、先序遍历右子树若二叉树非空（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树；若二叉树为空，结束——基本项（也叫终止项）若二叉树非空——递归项（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树；DLR.

voidpreorder(BiTNode*root){//先序遍历root指向根的二叉树

if(root!=NULL)

{cout<<root->data；//访问根结点

preorder(root->Lchild);//先序遍历根的左子树

preorder(root->Rchild);//先序遍历根的右子树

}//if}//preorder先序遍历LchilddataRchildECDABA∧B∧C∧E∧∧D∧root.

voidpreorder(BiTNode*root){

if(root!=NULL)

{cout<<root->data；//访问根结点

preorder(root->Lchild);//先序遍历根的左子树

preorder(root->Rchild);//先序遍历根的右子树

}//if}//preorderBACEDGFroot先序遍历序列：root:A.

voidpreorder(BiTNode*root){

if(root!=NULL)

{

cout<<root->data；//访问根结点

preorder(root->Lchild);//先序遍历根的左子树

preorder(root->Rchild);//先序遍历根的右子树

}//if}//preorderBACEDGFroot先序遍历序列：Aroot:A.

voidpreorder(BiTNode*root){

if(root!=NULL)

{

cout<<root->data；//访问根结点

preorder(root->Lchild);//先序遍历根的左子树

preorder(root->Rchild);//先序遍历根的右子树

}//if}//preorderBACEDGFrootroot:Broot:A先序遍历序列：AB.

voidpreorder(BiTNode*root){

if(root!=NULL)

{

cout<<root->data；//访问根结点

preorder(root->Lchild);//先序遍历根的左子树

preorder(root->Rchild);//先序遍历根的右子树

}//if}//preorderBACEDGFrootroot:Broot:A先序遍历序列：ABroot:DD∧∧.

voidpreorder(BiTNode*root){

if(root!=NULL)

{cout<<root->data；//访问根结点

preorder(root->Lchild);//先序遍历根的左子树

preorder(root->Rchild);//先序遍历根的右子树

}//if}//preorderBACEDGFrootroot:Broot:A先序遍历序列：ABroot:DD∧∧root:NULL.D

voidpreorder(BiTNode*root){

if(root!=NULL)

{cout<<root->data；//访问根结点

preorder(root->Lchild);//先序遍历根的左子树

preorder(root->Rchild);

//先序遍历根的右子树

}//if}//preorderBACEDGFrootroot:Broot:A先序遍历序列：ABroot:DD∧∧.

voidpreorder(BiTNode*root){

if(root!=NULL)

{cout<<root->data；//访问根结点

preorder(root->Lchild);//先序遍历根的左子树

preorder(root->Rchild);//先序遍历根的右子树

}//if}//preorderBACEDGFrootroot:Broot:A先序遍历序列：ABroot:DD∧∧root:NULL.D

voidpreorder(BiTNode*root){

if(root!=NULL)

{

cout<<root->data；//访问根结点

preorder(root->Lchild);

//先序遍历根的左子树

preorder(root->Rchild);

//先序遍历根的右子树

}//if}//preorderBACEDGFrootroot:Broot:A先序遍历序列：ABroot:DD∧∧.EE

voidpreorder(BiTNode*root){

if(root!=NULL)

{cout<<root->data；//访问根结点

preorder(root->Lchild);//先序遍历根的左子树

preorder(root->Rchild);

//先序遍历根的右子树

}//if}//preorderBACDGFrootroot:Broot:A先序遍历序列：ABDroot:EE.G

voidpreorder(BiTNode*root){

if(root!=NULL)

{cout<<root->data；//访问根结点

preorder(root->Lchild);//先序遍历根的左子树

preorder(root->Rchild);//先序遍历根的右子树

}//if}//preorderBACEDGFrootroot:Broot:A先序遍历序列：ABDroot:EEGroot:G.E

voidpreorder(BiTNode*root){

if(root!=NULL)

{cout<<root->data；//访问根结点

preorder(root->Lchild);//先序遍历根的左子树

preorder(root->Rchild);//先序遍历根的右子树

}//if}//preorderBACEDGFrootroot:Broot:A先序遍历序列：ABDroot:EEG.B

voidpreorder(BiTNode*root){

if(root!=NULL)

{cout<<root->data；//访问根结点

preorder(root->Lchild);//先序遍历根的左子树

preorder(root->Rchild);//先序遍历根的右子树

}//if}//preorderBACEDGFrootroot:Broot:A先序遍历序列：ABDEG.A

voidpreorder(BiTNode*root){

if(root!=NULL)

{cout<<root->data；//访问根结点

preorder(root->Lchild);//先序遍历根的左子树

preorder(root->Rchild);//先序遍历根的右子树

}//if}//preorderBACEDGFrootroot:A先序遍历序列：ABDEG.C

voidpreorder(BiTNode*root){

if(root!=NULL)

{cout<<root->data；//访问根结点

preorder(root->Lchild);//先序遍历根的左子树

preorder(root->Rchild);//先序遍历根的右子树

}//if}//preorderBACEDGFrootroot:A先序遍历序列：ABDEGroot:CC.

voidpreorder(BiTNode*root){

if(root!=NULL)

{cout<<root->data；//访问根结点

preorder(root->Lchild);//先序遍历根的左子树

preorder(root->Rchild);//先序遍历根的右子树

}//if}//preorderBACEDGFrootroot:A先序遍历序列：ABDEGroot:CC∧root:NULL.C

voidpreorder(BiTNode*root){

if(root!=NULL)

{cout<<root->data；//访问根结点

preorder(root->Lchild);//先序遍历根的左子树

preorder(root->Rchild);//先序遍历根的右子树

}//if}//preorderBACEDGFrootroot:A先序遍历序列：ABDEGroot:CC∧.F

voidpreorder(BiTNode*root){

if(root!=NULL)

{cout<<root->data；//访问根结点

preorder(root->Lchild);//先序遍历根的左子树

preorder(root->Rchild);//先序遍历根的右子树

}//if}//preorderBACEDGFrootroot:A先序遍历序列：ABDEGroot:CCroot:FF.C

voidpreorder(BiTNode*root){

if(root!=NULL)

{cout<<root->data；//访问根结点

preorder(root->Lchild);//先序遍历根的左子树

preorder(root->Rchild);//先序遍历根的右子树

}//if}//preorderBACEDGFrootroot:A先序遍历序列：ABDEGroot:CCF.A

voidpreorder(BiTNode*root){

if(root!=NULL)

{cout<<root->data；//访问根结点

preorder(root->Lchild);//先序遍历根的左子树

preorder(root->Rchild);//先序遍历根的右子树

}//if}//preorderBACEDGFrootroot:A先序遍历序列：ABDEGCF.

voidpreorder(BiTNode*root){

if(root!=NULL)

{cout<<root->data；//访问根结点

preorder(root->Lchild);//先序遍历根的左子树

preorder(root->Rchild);//先序遍历根的右子树

}//if}//preorderBACEDGFroot先序遍历序列：ABDEGCF.先序遍历过程BACEDGF先序遍历序列：ABDEGCFABDEGCF递归调用返回

voidpreorder(BiTNode*root){

if(root!=NULL)

{cout<<root->data；//访问根结点

preorder(root->Lchild);//先序遍历根的左子树

preorder(root->Rchild);//先序遍历根的右子树

}//if}//preorder.root:Aroot:Broot:Eroot:G栈在先序遍历中的作用BACEDGFroot先序遍历序列：ABDEG栈用于保存当前结点的祖先结点.中序遍历LDR：中序遍历左子树、访问根结点、中序遍历右子树DLR213.中序遍历LDR：中序遍历左子树、访问根结点、中序遍历右子树若二叉树非空（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树；若二叉树为空，结束——基本项（也叫终止项）若二叉树非空——递归项（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树；DLR.

voidinorder(BiTNode*root){//中序遍历root指向根的二叉树

if(root!=NULL)

{inorder(root->Lchild);//中序遍历根的左子树

cout<<root->data；//访问根结点

inorder(root->Rchild);//中序遍历根的右子树

}//if}//inorder中序遍历LchilddataRchild.

voidinorder(BiTNode*root){

if(root!=NULL)

{inorder(root->Lchild);//中序遍历根的左子树

cout<<root->data；//访问根结点

inorder(root->Rchild);//中序遍历根的右子树

}//if}//inorderBACEDGFroot中序遍历序列：root:A.

voidinorder(BiTNode*root){

if(root!=NULL)

{inorder(root->Lchild);//中序遍历根的左子树

cout<<root->data；//访问根结点

inorder(root->Rchild);//中序遍历根的右子树

}//if}//inorderBACEDGFroot中序遍历序列：root:Aroot:B.

voidinorder(BiTNode*root){

if(root!=NULL)

{inorder(root->Lchild);//中序遍历根的左子树

cout<<root->data；//访问根结点

inorder(root->Rchild);//中序遍历根的右子树

}//if}//inorderBACEDGFroot中序遍历序列：root:Aroot:Broot:D∧∧.

voidinorder(BiTNode*root){

if(root!=NULL)

{inorder(root->Lchild);//中序遍历根的左子树

cout<<root->data；//访问根结点

inorder(root->Rchild);//中序遍历根的右子树

}//if}//inorderBACEDGFroot中序遍历序列：root:Aroot:Broot:D∧∧root:NULL.

voidinorder(BiTNode*root){

if(root!=NULL)

{inorder(root->Lchild);//中序遍历根的左子树

cout<<root->data；//访问根结点

inorder(root->Rchild);//中序遍历根的右子树

}//if}//inorderBACEDGFroot中序遍历序列：root:Aroot:Broot:D∧∧D.

voidinorder(BiTNode*root){

if(root!=NULL)

{inorder(root->Lchild);//中序遍历根的左子树

cout<<root->data；//访问根结点

inorder(root->Rchild);//中序遍历根的右子树

}//if}//inorderBACEDGFroot中序遍历序列：root:Aroot:Broot:D∧∧Droot:NULL.

voidinorder(BiTNode*root){

if(root!=NULL)

{inorder(root->Lchild);//中序遍历根的左子树

cout<<root->data；//访问根结点

inorder(root->Rchild);//中序遍历根的右子树

}//if}//inorderBACEDGFroot中序遍历序列：root:Aroot:Broot:D∧∧D.

voidinorder(BiTNode*root){

if(root!=NULL)

{inorder(root->Lchild);//中序遍历根的左子树

cout<<root->data；//访问根结点

inorder(root->Rchild);//中序遍历根的右子树

}//if}//inorderBACEDGFroot中序遍历序列：root:Aroot:BDB.

voidinorder(BiTNode*root){

if(root!=NULL)

{inorder(root->Lchild);//中序遍历根的左子树

cout<<root->data；//访问根结点

inorder(root->Rchild);//中序遍历根的右子树

}//if}//inorderBACEDGFroot中序遍历序列：root:Aroot:BDBroot:E.

voidinorder(BiTNode*root){

if(root!=NULL)

{inorder(root->Lchild);//中序遍历根的左子树

cout<<root->data；//访问根结点

inorder(root->Rchild);//中序遍历根的右子树

}//if}//inorderBACEDGFroot中序遍历序列：root:Aroot:BDBroot:Eroot:G.

voidinorder(BiTNode*root){

if(root!=NULL)

{inorder(root->Lchild);//中序遍历根的左子树

cout<<root->data；//访问根结点

inorder(root->Rchild);//中序遍历根的右子树

}//if}//inorderBACEDGFroot中序遍历序列：root:Aroot:BDBroot:Eroot:Groot:NULL∧.

voidinorder(BiTNode*root){

if(root!=NULL)

{inorder(root->Lchild);//中序遍历根的左子树

cout<<root->data；//访问根结点

inorder(root->Rchild);//中序遍历根的右子树

}//if}//inorderBACEDGFroot中序遍历序列：root:Aroot:BDBroot:Eroot:G∧G.

voidinorder(BiTNode*root){

if(root!=NULL)

{inorder(root->Lchild);//中序遍历根的左子树

cout<<root->data；//访问根结点

inorder(root->Rchild);//中序遍历根的右子树

}//if}//inorderBACEDGFroot中序遍历序列：root:Aroot:BDBroot:EGE.

voidinorder(BiTNode*root){

if(root!=NULL)

{inorder(root->Lchild);//中序遍历根的左子树

cout<<root->data；//访问根结点

inorder(root->Rchild);//中序遍历根的右子树

}//if}//inorderBACEDGFroot中序遍历序列：root:Aroot:BDBGE.

voidinorder(BiTNode*root){

if(root!=NULL)

{inorder(root->Lchild);//中序遍历根的左子树

cout<<root->data；//访问根结点

inorder(root->Rchild);//中序遍历根的右子树

}//if}//inorderBACEDGFroot中序遍历序列：root:ADBGEA.

voidinorder(BiTNode*root){

if(root!=NULL)

{inorder(root->Lchild);//中序遍历根的左子树

cout<<root->data；//访问根结点

inorder(root->Rchild);//中序遍历根的右子树

}//if}//inorderBACEDGFroot中序遍历序列：root:ADBGEAroot:C.

voidinorder(BiTNode*root){

if(root!=NULL)

{inorder(root->Lchild);//中序遍历根的左子树

cout<<root->data；//访问根结点

inorder(root->Rchild);//中序遍历根的右子树

}//if}//inorderBACEDGFroot中序遍历序列：root:ADBGEAroot:C∧root:NULL.

voidinorder(BiTNode*root){

if(root!=NULL)

{inorder(root->Lchild);//中序遍历根的左子树

cout<<root->data；//访问根结点

inorder(root->Rchild);//中序遍历根的右子树

}//if}//inorderBACEDGFroot中序遍历序列：root:ADBGEAroot:C∧C.

voidinorder(BiTNode*root){

if(root!=NULL)

{inorder(root->Lchild);//中序遍历根的左子树

cout<<root->data；//访问根结点

inorder(root->Rchild);//中序遍历根的右子树

}//if}//inorderBACEDGFroot中序遍历序列：root:ADBGEAroot:CCroot:F.

voidinorder(BiTNode*root){

if(root!=NULL)

{inorder(root->Lchild);//中序遍历根的左子树

cout<<root->data；//访问根结点

inorder(root->Rchild);//中序遍历根的右子树

}//if}//inorderBACEDGFroot中序遍历序列：root:ADBGEAroot:C∧Croot:Froot:NULL.

voidinorder(BiTNode*root){

if(root!=NULL)

{inorder(root->Lchild);//中序遍历根的左子树

cout<<root->data；//访问根结点

inorder(root->Rchild);//中序遍历根的右子树

}//if}//inorderBACEDGFroot中序遍历序列：root:ADBGEAroot:CCroot:F∧F.

voidinorder(BiTNode*root){

if(root!=NULL)

{inorder(root->Lchild);//中序遍历根的左子树

cout<<root->data；//访问根结点

inorder(root->Rchild);//中序遍历根的右子树

}//if}//inorderBACEDGFroot中序遍历序列：root:ADBGEAroot:CCF.

voidinorder(BiTNode*root){

if(root!=NULL)

{inorder(root->Lchild);//中序遍历根的左子树

cout<<root->data；//访问根结点

inorder(root->Rchild);//中序遍历根的右子树

}//if}//inorderBACEDGFroot中序遍历序列：root:ADBGEACF.

voidinorder(BiTNode*root){

if(root!=NULL)

{inorder(root->Lchild);//中序遍历根的左子树

cout<<root->data；//访问根结点

inorder(root->Rchild);//中序遍历根的右子树

}//if}//inorderBACEDGFroot中序遍历序列：DBGEACF.BACEDGFrootroot:Aroot:Broot:Eroot:G∧栈在中序遍历中的作用中序遍历序列：DBG栈用于保存当前结点的祖先结点.后序遍历LRD：后序遍历左子树、后序遍历右子树、访问根结点DLR312EGFCDAB后序遍历序列:BDFGECA.

voidinorder(BiTNode*root){

if(root!=NULL)

{inorder(root->Lchild);//中序遍历根的左子树

cout<<root->data；//访问根结点

inorder(root->Rchild);//中序遍历根的右子树

}//if}//inordervoidpreorder(BiTNode*root){

if(root!=NULL)

{cout<<root->data；//访问根结点

preorder(root->Lchild);//先序遍历根的左子树

preorder(root->Rchild);//先序遍历根的右子树

}//if}//preordervoidpostorder(BiTNode*root){if(root!=NULL){postorder(root->Lchild);//后序遍历根的左子树

postorder(root->Rchild);//后序遍历根的右子树

cout<<root->data；//访问根结点

}//if}//postorder.

voidinorder(BiTNode*root){

if(root!=NULL)

{inorder(root->Lchild);//中序遍历根的左子树

cout<<root->data；//访问根结点

inorder(root->Rchild);//中序遍历根的右子树

}//if}//inorderBACEDGFrootroot:Aroot:Broot:EE中序遍历序列：DBGvoidInOrder(BiTNode*root){

InitStack(S);Push(S,root);

//根指针进栈

while(!StackEmpty(S))

{

while(GetTop(S,p)&&p)Push(S,p->Lchild);//向左走到头

Pop(S,p);//空指针退栈

if(!StackEmpty(S)){Pop(S,p);cout<<p->data;//访问结点

Push(S,p->Rchild);//向右

}//if}//while}//InOrder.

voidinorder(BiTNode*root){

if(root!=NULL)

{inorder(root->Lchild);//中序遍历根的左子树

cout<<root->data；//访问根结点

inorder(root->Rchild);//中序遍历根的右子树

}//if}//inorderBACEDGFrootroot:Aroot:Broot:EE中序遍历序列：DBGvoidInOrder(BiTNode*root){

InitStack(S);p=root;

//根指针进栈

while(p||!StackEmpty(S))

{

if(p){Push(S,p);p=p->Lchild;}

else{

//根指针退栈，访问根结点，遍历右子树

Pop(S,p);cout<<p->data;p=p->Rchild;}//if-else}//while}//InOrder.用二叉树表示表达式a+b*(c–d)–e/ff/e-+*a-bdc先序遍历序列:–+a*b–cd/ef中序遍历序列:a+b*c–d–e/f后序遍历序列:abcd–*+ef/–

表达式的前缀、中缀和后缀表示.用栈对后缀表达式求值表达式的后缀表示:abcd–*+ef/–bacdbat1t2at1=c–dt2=b*t1t3=a+t2t3et3ft4=e/ft4t3t5t5=t3–t4.层序遍历先根，后子树；先左子树，后右子树EGFCDAB队列队头树根结点A入队层序遍历序列:.层序遍历EGFCDAB队列队头A层序遍历序列:A出队先根，后子树；先左子树，后右子树.层序遍历先根，后子树；先左子树，后右子树EGFCDAB队列队头根结点B、C入队A的子树层序遍历序列:A.层序遍历先根，后子树；先左子树，后右子树EGFCDAB队列队头BB出队C层序遍历序列:A.层序遍历先根，后子树；先左子树，后右子树EGFCDAB队列队头C根结点入队B的子树层序遍历序列:AB.层序遍历先根，后子树；先左子树，后右子树EGFCDAB队列队头CC出队层序遍历序列:AB.层序遍历先根，后子树；先左子树，后右子树EGFCDAB队列队头根结点入队C的子树层序遍历序列:ABC.层序遍历先根，后子树；先左子树，后右子树EGFCDAB队列队头DED出队层序遍历序列:ABC.层序遍历先根，后子树；先左子树，后右子树EGFCDAB队列队头E根结点入队D的子树层序遍历序列:ABCD.层序遍历先根，后子树；先左子树，后右子树EGFCDAB队列队头EE出队层序遍历序列:ABCD.层序遍历先根，后子树；先左子树，后右子树EGFCDAB队列队头根结点F、G入队E的子树层序遍历序列:ABCDE.层序遍历先根，后子树；先左子树，后右子树EGFCDAB队列队头FGF出队层序遍历序列:ABCDE.层序遍历先根，后子树；先左子树，后右子树EGFCDAB队列队头G根结点入队F的子树层序遍历序列:ABCDEF.层序遍历先根，后子树；先左子树，后右子树EGFCDAB队列队头GG出队层序遍历序列:ABCDEF.层序遍历先根，后子树；先左子树，后右子树EGFCDAB层序遍历序列:ABCDEFG利用队列实现二叉树的层序遍历：构造一个空队列；树根结点入队列；while（队列不空）{

队头元素出队列；访问结点；刚出队的结点的左孩子、右孩子结点先后入队列；

}.6.3.2线索二叉树Ltag=LchilddataRchildLchilddataRchildRtagLtag0Lchild指向左子树根结点1Lchild指向前驱结点Rtag=0Rchild指向右子树根结点1Rchild指向后继结点typedefenumPointerTag{Link=0,Thread=1};typedefstructBiThrNode{ElemTypedata;structBiThrNode*Lchild,*Rchild;PointerTagLtag,Rtag;}*BiThrTree;BACEDGFroot.BACEDGFroot中序线索二叉树NULL中序序列：DBGEACFNULL.BACEDGFroot中序线索二叉树NULL中序序列：DBGEACFNULL在中序线索化二叉树上查找给定结点的前驱和后继结点.中序线索二叉树在中序线索二叉树上，查找p所指结点的后继分为两种情况：(1)若p->Rtag=1，则p->Rchild指向其后继结点；(2)若p->Rtag=0，则p所指结点的中序后继必为其右子树中序遍历得到的第一个结点，即从p所指结点的右子树根出发，沿左指针链向下找，直到找到一个没有左孩子的结点为止，这个结点称为p的右子树中“最左下”的结点。.BACEDGFroot中序线索二叉树NULLNULLIH.中序线索二叉树中序线索二叉树上找指定结点的后继：

BiThrTreeinordernext(BiThrTreep){

if

（p->rtag==1）return(p->Rchild);

else{q=p->Rchild;

while(q->ltag==0)q=q->Lchild;

return(q);

}}typedefstructBiThrNode{ElemTypedata;structBiThrNode*Lchild,*Rchild;PointerTagLtag,Rtag;}*BiThrTree;.建立中序线索二叉树线索化的实质是将二叉链表中的空指针改为指向前驱或后继的线索，而前驱或后继的信息只有在遍历时才能得到，因此线索化的过程就是在遍历过程中修改空指针的过程。

voidInOrderThreading(BiThrTree&Thrt,BiThrTreeroot){//Thrt指向中序线索化链表的头结点

if(!Thrt=(BiThrTriTree)malloc(sizeof(BiThrNode)))exit(OVERFLOW);

Thrt->Ltag=Link;Thrt->Rtag=Thread;Thrt->Rchild=Thrt;if(root==NULL)Thrt->Lchild=Thrt;else{Thrt->Lchild=root;pre=Thrt;InThreading(root);//中序遍历进行中序线索化

pre->Rchild=Thrt;pre->Rtag=Thread;Thrt->Rchild=pre;}}//InOrderThreadingLchilddataRchildRtagLtagvoidInThreading(BiThrTreep){if(p){InThreading(p->Lchild);//左子树线索化

if(!p->Lchild){//前驱线索

p->Ltag=Thread;p->Lchild=pre;}if(!pre->Rchild){//后继线索

pre->Rtag=Thread;pre->Rchild=p;}pre=p;InThreading(p->Rchild);//右子树线索化

}}//InThreading.BACEDGFroot后序线索二叉树后序序列：IDGHEBFCANULL在后序线索化二叉树上查找给定结点的前驱和后继结点HI.后序线索二叉树在后序线索二叉树上，查找p所指结点的后继分为两种情况：(1)若p所指结点是整棵二叉树的根结点，则无后继结点；(3)若p->Rtag=0：//P所指结点有右子树①若p所指结点是其父结点f的右孩子，则其父结点f是其后继；②若p所指结点是其父结点f的左孩子：

ⅰ若p所指结点没有右兄弟，则其父结点f是其后继；

ⅱ若P有右兄弟，则其后继结点是其父的右子树上后序遍历得到的第一个结点。(2)若p->Rtag=1，则p->Rchild指向其后继结点；.后序线索二叉树后序线索二叉树上找指定结点的后继

BiThrTree

postorder_next(BiThrTreep){if(p->Rtag==1)return(p->Rchild);

else{

查找p所指节点的父结点f;

if(p==f->Rchild)returnf;if(p==f->Lchild&&f->Rtag==1)returnf;q=f->Rchild;while(q->Ltag==0||q->Rtag==0){if(q->Ltag==0)q=q->Lchild;elseq=q->Rchild;}/*endofwhile*/

return(q);}}/*postorder_next*/typedefstructBiThrNode{ElemTypedata;structBiThrNode*Lchild,*Rchild;PointerTagLtag,Rtag;}*BiThrTree;BACEDGFroot后序序列：IDGHEBFCANULLHIp.BACEDGFroot后序后继线索二叉树HILK.BACEDGFroot先序线索二叉树NULL先序序列：ABDEGCF在先序线索化二叉树上查找给定结点的前驱和后继结点.

树的存储结构树、森林和二叉树的相互转换树、森林的遍历6.4树和森林.

双亲表示法采用一组地址连续的存储单元存储树的结点,通过保存每个结点的双亲结点的位置，表示树中结点之间的结构关系。

IACBHGFED6.4.1树的存储结构//双亲表示类型定义#defineMAX100structnode{chardata;intparent;//双亲位置域};typedefstructnodeNODE;NODEtree[MAX];9A0B1C1D2E2F3G5H5I50123456789dataparent

树中结点数目.IACBHGFED

孩子表示法通过保存每个结点的孩子结点的位置，表示树中结点之间的结构关系。20123456789ABCDEFGHI∧∧∧∧∧3∧45∧6∧789∧6.4.1树的存储结构.

孩子兄弟表示法用二叉链表作为树的存贮结构。链表的两个指针域分别指向该结点的第一个孩子结点和其右边的下一个兄弟结点。

structnode{chardata;structnode*son,*brother;};6.4.1树的存储结构IACBHGFEDA∧BF∧∧D∧C∧E∧G∧H∧I∧∧root.6.4.1树的存储结构IACBHGFEDA∧BF∧∧D∧C∧E∧G∧H∧I∧∧rootABDCEFGHI.树与