第 7章 树树的定义及基本操作二叉树线索二叉树树、森林和二叉树哈夫曼树及其应用树的定义树,包含 n（ n>0）个节点的有穷集合 K，且在 K中定义了一个关系 N,N满足以下条件：
有且仅有一个结点 K0，它对于关系 N来说没有前驱，
称 K0为树的根结点。
除 K0外,K中的每个结点对于关系 N来说有且仅有一个前驱。
K中各结点对关系 N来说可以有 m个后继 (m≥0) 。
子树,若 n>1，除根结点之外的其余数据元素被分为 m
（ m>0）个互不相交的集合 T1,T2,….,Tm,其中每一个集合 Ti (1≤i≤m) 本身又是一棵树；树 T1,T2,…..,Tm 称作根结点的子树。
实例：
树的特点：
树的根结点没有前驱结点，且除了根结点之外的所有结点有且只有一个前驱结点。
树结点可以有零个或多个后继结点。
树的表示形式树的表示方法：
直观表示法：
形式化表示法：
（ A(B(E(K,L),F(L)),C(G),D(H,I(M(N))))）
凹入表示法：
树的常用术语树的结点,包含一个数据元素及若干指向其子树的分支。
结点的度,结点所拥有的子树的个数称为该结点的度。
叶子,度为 0的结点。
非终端结点,度不为 0的结点。
孩子,结点的子树的根称为该结点的孩子。
兄弟,同一个双亲的孩子之间互称兄弟。
结点的祖先,是从根到该结点所经分支上的所有结点。
子孙,以某结点为根的子树中的任意结点都称为该结点的子孙。
层次性,从根开始定义起，根为第一层，根的孩子为第二层；某结点在第 L层，则其子树的根就在第 L+1层。
树的深度,树中各结点层次的最大值称作该树的深度。
有序树：将树中结点的各子树看成从左向右是有次序的则称该树为有序树。
森林,是 m（ m≥0 ）棵互不相交的树构成的有限集合；
即 F={T1,T2,? Tm}，其中,Ti（ i=1,2,? m）是树，
当 m=0时,F是空森林。对树中每个结点而言，其子树的集合即为森林。反之，若给森林 F={T1,T2,? Tm}
中的每棵树的根结点都赋予同一个双亲结点，则就构成一棵树。
树的基本操作树的基本操作：
Initiate(t),初始化一棵树 t。
Root(x),求结点 x所在树的根结点。
Parent(t,x),求树 t中结点 x的双亲结点。
Child(t,x,i),求树 t中结点 x的第 i个孩子结点。
Insert(t,x,i,s),把以 s为结点的树插入到树 t中作为结点 x的第 i棵子树。
Delete(t,x,i),在树 t中删除结点 x的第 i棵子树。
Tranverse(t),按某种方式访问树 t中的每个结点，且使每个结点只被访问一次。
二叉树二叉树,T是 n（ n≥0 ） 个有限元素的集合，这个集合或者是空集，或者是由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树组成。即当 T
时,T满足以下条件：
存在唯一的数据元素 r?T，且 r在 T中没有直接前驱，称为 根结点 。
若 T-{r}，则 T-{r}存在划分 T1,T2：
T1?T2=T-{r},T1?T2=?,且 T1,T2均为二叉树，并命名 T1是 T的 左子树,T2是 T的 右子树 。
实例：
二叉树的基本形态：
特殊二叉树满二叉树,一棵深度为 k且有 2k-1个结点的二叉树。
完全二叉树,深度为 k，有 n个结点的二叉树，当且仅当其每一个结点都与深度为 k的满二叉树中编号从 1到 n的结点一一对应。
二叉树的性质性质 1,在二叉树的第 i层上至多有 2 i– 1个结点（ i≥1 。）
性质 2,深度为 k的二叉树至多有 2k -1个结点（ k≥1 ）。
性质 3,对任何一棵二叉树 T，如其叶子结点数为 n0，度为
2的结点数为 n2，则 n0= n2+1。
性质 4,具有 n个结点的完全二叉树的深度为「 log2n」 +1。
性质 5,如果对一棵有 n个结点的完全二叉树的结点按层编号，则对任一结点 i（ 1≤i≤n ）有：
如果 i＝ 1，结点 i是根结点，无双亲；如果 i＞ 1，则其双亲结点的编号 i/2。
如果 2i>n，则结点 i无左孩子，为叶子结点；否则其左孩子是结点 2i。
如果 2i+1>n，则结点 i无右孩子；否则其右孩子结点
2i+1。
二叉树的存储结构顺序存储结构：
概念,把二叉树的所有结点，按照一定的次序顺序，
存储到一片连续的存储单元中。
完全二叉树的结点编号与线性序列的关系,编号为 i
的结点是 Ti(1≤i≤n),则有：
i>1，则 Ti的双亲编号为 i/2；若 i=1，则 Ti为根结点。
若 2i≤n,则 Ti的左孩子的编号是 2i；否则,Ti无左孩子。
若 2i+1≤n,则 Ti的右孩子的编号是 2i+1；否则,Ti无右孩子。
若 i为奇数且不为 1，则 Ti的左兄弟的编号为 i-1；否则,Ti没有左兄弟。
若 i为偶数且小于 n，则 Ti的右兄弟的编号为 i+1；否则,Ti
没有右兄弟。
二叉树顺序存储结构实例 1 — 完全二叉树：
二叉树顺序存储结构实例 2 — 一般二叉树,
链式存储结构：
概念,二叉树的链表中的结点至少包含三个域：数据域和左、右指针域，如图 7-12（ a）所示；为便于找到结点的双亲，则在结点结构中增加一个指向其双亲结点的指针域，如图 7-12（ b）所示：
实例：
二叉树的遍历遍历,按某指定规则访问树中每个结点，且使得每个结点均被访问一次，且仅被访问一次。
二叉树的遍历方案：
先序遍历（ DLR ）：
访问过程：
访问根结点。
先序遍历根结点的左子树。
先序遍历根结点的右子树。
算法：
void PreOrder (BTree T)
{ if (T == NULL) return ; /*递归出口 */
visite (T -> data ); /*访问结点的数据域 */
if ( T -> lchild != NULL ) PreOrder (T -> lchild );
if ( T -> rchild != NULL ) PreOrder (T -> rchild );}
中序遍历（ LDR）：
访问过程：
中序遍历根结点的左子树。
访问根结点。
中序遍历根结点的右子树。
算法：
void Inorder(BTree T)
{
if(T==NULL) return; /* 递归出口 */
if(T->lchild!=NULL)
Inorder(T->lchild);
visite(T->data); /*访问结点的数据域 */
if(T->rchild!=NULL)
Inorder(T->rchild);
}
后序遍历（ LRD）：
过程：
后序遍历根结点的左子树。
后序遍历根结点的右子树。
访问根结点。
算法：
void Postorder(BTree T)
{
if(T==NULL) return;/* 递归出口 */
if(T->lchild!=NULL)
Postorder(T->lchild);
if(T->rchild!=NULL)
Postorder(T->rchild);
visite(T->data); /*访问结点的数据域 */
}
层次遍历：
算法：
void LevelOrder（ BiTree bt） /*层次遍历二叉树 bt*/
{ BiTree Queue[MAXNODE];
int front,rear;
if (bt==NULL) return;
front=-1;
rear=0;
queue[rear]=bt;
while(front!=rear)
{front++;
Visite(queue[front]->data); /*访问队首结点的数据域 */
if (queue[front]->lchild!=NULL) /*将队首结点的左孩子结点入队列 */
{ rear++;
queue[rear]=queue[front]->lchild;}
if (queue[front]->rchild!=NULL) /*将队首结点的右孩子结点入队列 */
{ rear++;
queue[rear]=queue[front]->rchild;}
}
}
二叉树遍历的应用结点序列,如图所示的二叉树表示表达式
a+b*(c-d)-e/f
前缀表达,先序遍历二叉树来遍历此二叉树，按访问结点的先后次序将结点排列起来,可得到：
- + a * b – c d /ef 。
中缀表示,中序遍历二叉树来遍历此二叉树，得到此二叉树的中序序列,可得到,a + b * c – d – e / f 。
后缀表示,后序遍历二叉树来遍历此二叉树，得到此二叉树的后序序列，可得到 a b c d - * + e f / - 。
查找数据元素：
概念,在 bt为二叉树的根结点指针的二叉树中查找数据元素 x;查找成功时返回该结点的指针；查找失败时返回空指针。
算法：
BTree Search(BTree bt,elemtype x)
{
BTree p;
if(bt==NULL)
return NULL;
if(bt->data==x)
return bt; /*查找成功出口 */
/*在 bt ->lchild为根结点的二叉树中查找数据元素 x*/
if（ bt->lchild！ =NULL）
{
p=Search（ bt->lchild,x）；
if（ p！ = NULL）
return p；
}
if（ bt->rchild！ = NULL） /*在 bt-〉 rchild为根结点的二叉树中查找数据元素 x*/
{
p=Search（ bt->rchild,x）；
if（ p！ =NULL）
return p；
}
return NULL;/*查找失败出口 */
}
线索二叉树线索,利用空指针域，存放指向结点的某种遍历次序下的前驱和后继结点的指针，这种附加的指针称为线索。
线索链表,加上线索的二叉链表。
线索二叉树,相应的二叉树称为线索二叉树。
线索化,对二叉树以某种次序遍历使其变为线索二叉树的过程。
线索二叉树的结点结构各域规定：
中序线索二叉树实例：
线索二叉树的遍历查找结点的后继结点问题 (以后序为例 )，分三种情况：
若点 x是二叉树的根，则其后继为空。
若结点 x是其双亲的右孩子或是其双亲的左孩子且其双亲没有右子树，则其后继即为双亲结点。
若结点 x是其双亲的左孩子，且其双亲有右子树，
则其后继为双亲的右子树上按后序遍历列出的第一个结点。
实例：
线索化过程中，对当前根结点的处理：
若结点 *p有空指针域，则将相应的标志置为 1。
若结点 *p有中序前驱结点 *pre(即 *pre != NULL)
则：
若结点 *pre的右线索标志已建立 (即 pre ->
Rtag==1)，则令 pre -> Rchild指向其中序前驱结点 *p的右线索。
若结点 *pre的左线索标志已建立 (即 pre ->
Ltag==1)，则令 pre -> Lchild指向其中序前驱结点 *p的左线索。
将 pre指向刚刚访问过的结点 *p(即 pre=p)；则在下一次访问一个新结点 *p时,*pre为其前驱结点。
线索二叉树的运算中序线索二叉树,查找结点 *p的中序后继结点,
若 *p的右子树空 (即 p->rtag为 Thread)，则 p-
>rchild为右线索，直接指向 *p的中序后继。
若 *p的右子树非空 (即 p->rtag为 Link)，则 *p的中序后继必是其右子树中第一个中序遍历到的结点。
其算法的时间复杂度不超过树的高度 h，即 O(h)。
中序线索二叉树查找结点 *p的中序前趋结点,
若 *p的左子树为空，则 p->1child为左线索，
直接指向 *p的中序前趋结点。
若 *p的左子树非空，则从 *p的左孩子出发，沿右指针链往下查找，直到找到一个没有右孩子的结点为止。
树的存储结构双亲表示法：
概念,用一组连续的空间存储树中的各个结点，同时在每个结点中附设一个指示器指向其双亲结点在链表中的位置。
实例：
孩子表示法：
概念,使用多重链表，每个结点有多个指针域，其中每个指针指向一棵子树的根结点。
多重链表的结点是同构的,d为树的度多重链表的结点是不同构的,d为结点的度实例：
带双亲的孩子链表孩子兄弟表示法：
概念,每个结点除信息域外，再增加两个分别指向该结点的第一个孩子结点和下一个兄弟结点的指针域 。
实例,
森林与二叉树的转换树转换成二叉树：
方法：
在所有兄弟结点之间加一连线。
对每个结点，除了保留与其长子的连线外，
去掉该结点与其它孩子的连线。
实例：
森林转化成二叉树：
方法,F={T1,T2,…,Tm}是森林，可以把上述森林转换为二叉树的方法做如下定义，即可按如下规则将森林转换成一棵二叉树 B＝（ root,LB,RB）。
若 F为空，即 m＝ 0，则 B为空树。
若 F非空，即 m≠0,则 B的根 root即为森林中第一棵树的根 ROOT（ T1）； B的左子树 LB是从
T1中根结点的子树森林 F1＝ {T11,T12,…,T 1n}转换而成的二叉树 B{T11,T12,…,T 1n}；其右子树 RB是从森林 F’={T 2,…,Tm}转换而成的二叉树
B{T2,…,Tm}。
实例,
二叉树转换成树、森林：
方法,如果 B=（ root,LB,RB）是一棵二叉树，则可按如下规则转换成森林 F＝ {T1,T2,…,Tm}：
若 B为空，则 F为空。
若 B非空，则 F中第一棵树 T1的根 ROOT（ T1）
即为二叉树 B的根 root； T1中根结点的子树森林 F1是由 B的左子树 LB转换而成的森林； F中除 T1之外其余树组成的森林 F’={T 1,T2,…,
Tm}是由 B的右子树 RB转换而成的森林。
实例：
树和森林的遍历前序遍历森林,若森林非空，则按下面规则遍历森林。
访问森林中第一棵树的根结点。
先序遍历第一棵树中根结点的子树森林。
先序遍历除去第一棵树之后剩余的树构成的森林 。
后序遍历森林,若森林非空，则按下面规则遍历森林。
后序遍历森林中第一棵树的根结点的子树森林。
访问第一棵树的根结点。
后序遍历除去第一棵树之后剩余的树构成的森林。
实例：
先序序列,A B E F C D
后序序列,E F B C D A
哈夫曼树及其应用概念：
路径,树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。
路径长度,路径上的分支数目。
树的路径长度,根结点到树中每一结点的路径长度之和。
树的带权路径长度,树中所有叶子结点的带权路径长度之和，即：
哈夫曼树,对于一组带有确定权值的叶结点，带权路径长度 WPL最小的二叉树。
实例：
带权路径长度分别为：
（ a） WPL＝ 7× 2+5× 2+2× 2+4× 2＝ 36
（ b） WPL＝ 7× 3+5× 3+2× 1+4× 2＝ 46
（ c） WPL＝ 7× 1+5× 2+2× 3+4× 3＝ 35
哈夫曼树的构造基本思想：
（ 1）给定的 n个权值 {W1,W2,…,Wn}构成 n棵二叉树的集合 F={T1,T2,…,Tn}，其中每棵二叉树 Ti中只有一个带权为 Wi的根结点，其左右子树均空。
（ 2）在 F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、
右子树上根结点的权值之和。
(3)在 F中删除这两棵树，同时将新得到的二叉树加入 F中。
(4)重复（ 2）和（ 3），直到 F中只剩下一棵二叉树为止 。
实例,{5,11,26,18,34,15,6}构成一棵哈夫曼树。
哈夫曼树在编码问题中的应用前缀编码,设计长短不等的编码，使任何一个字符的编码都不是另一个字符的前缀，以才能保证译码的唯一性，
这种编码称做前缀编码。
哈夫曼编码,利用哈夫曼树构造使电文的编码总长度最短，即以 n种字符出现的次数或频率作为权值，由此得到的二进制前缀编码便称为哈夫曼编码。
有且仅有一个结点 K0，它对于关系 N来说没有前驱，
称 K0为树的根结点。
除 K0外,K中的每个结点对于关系 N来说有且仅有一个前驱。
K中各结点对关系 N来说可以有 m个后继 (m≥0) 。
子树,若 n>1，除根结点之外的其余数据元素被分为 m
（ m>0）个互不相交的集合 T1,T2,….,Tm,其中每一个集合 Ti (1≤i≤m) 本身又是一棵树；树 T1,T2,…..,Tm 称作根结点的子树。
实例：
树的特点：
树的根结点没有前驱结点，且除了根结点之外的所有结点有且只有一个前驱结点。
树结点可以有零个或多个后继结点。
树的表示形式树的表示方法：
直观表示法：
形式化表示法：
（ A(B(E(K,L),F(L)),C(G),D(H,I(M(N))))）
凹入表示法：
树的常用术语树的结点,包含一个数据元素及若干指向其子树的分支。
结点的度,结点所拥有的子树的个数称为该结点的度。
叶子,度为 0的结点。
非终端结点,度不为 0的结点。
孩子,结点的子树的根称为该结点的孩子。
兄弟,同一个双亲的孩子之间互称兄弟。
结点的祖先,是从根到该结点所经分支上的所有结点。
子孙,以某结点为根的子树中的任意结点都称为该结点的子孙。
层次性,从根开始定义起，根为第一层，根的孩子为第二层；某结点在第 L层，则其子树的根就在第 L+1层。
树的深度,树中各结点层次的最大值称作该树的深度。
有序树：将树中结点的各子树看成从左向右是有次序的则称该树为有序树。
森林,是 m（ m≥0 ）棵互不相交的树构成的有限集合；
即 F={T1,T2,? Tm}，其中,Ti（ i=1,2,? m）是树，
当 m=0时,F是空森林。对树中每个结点而言，其子树的集合即为森林。反之，若给森林 F={T1,T2,? Tm}
中的每棵树的根结点都赋予同一个双亲结点，则就构成一棵树。
树的基本操作树的基本操作：
Initiate(t),初始化一棵树 t。
Root(x),求结点 x所在树的根结点。
Parent(t,x),求树 t中结点 x的双亲结点。
Child(t,x,i),求树 t中结点 x的第 i个孩子结点。
Insert(t,x,i,s),把以 s为结点的树插入到树 t中作为结点 x的第 i棵子树。
Delete(t,x,i),在树 t中删除结点 x的第 i棵子树。
Tranverse(t),按某种方式访问树 t中的每个结点，且使每个结点只被访问一次。
二叉树二叉树,T是 n（ n≥0 ） 个有限元素的集合，这个集合或者是空集，或者是由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树组成。即当 T
时,T满足以下条件：
存在唯一的数据元素 r?T，且 r在 T中没有直接前驱，称为 根结点 。
若 T-{r}，则 T-{r}存在划分 T1,T2：
T1?T2=T-{r},T1?T2=?,且 T1,T2均为二叉树，并命名 T1是 T的 左子树,T2是 T的 右子树 。
实例：
二叉树的基本形态：
特殊二叉树满二叉树,一棵深度为 k且有 2k-1个结点的二叉树。
完全二叉树,深度为 k，有 n个结点的二叉树，当且仅当其每一个结点都与深度为 k的满二叉树中编号从 1到 n的结点一一对应。
二叉树的性质性质 1,在二叉树的第 i层上至多有 2 i– 1个结点（ i≥1 。）
性质 2,深度为 k的二叉树至多有 2k -1个结点（ k≥1 ）。
性质 3,对任何一棵二叉树 T，如其叶子结点数为 n0，度为
2的结点数为 n2，则 n0= n2+1。
性质 4,具有 n个结点的完全二叉树的深度为「 log2n」 +1。
性质 5,如果对一棵有 n个结点的完全二叉树的结点按层编号，则对任一结点 i（ 1≤i≤n ）有：
如果 i＝ 1，结点 i是根结点，无双亲；如果 i＞ 1，则其双亲结点的编号 i/2。
如果 2i>n，则结点 i无左孩子，为叶子结点；否则其左孩子是结点 2i。
如果 2i+1>n，则结点 i无右孩子；否则其右孩子结点
2i+1。
二叉树的存储结构顺序存储结构：
概念,把二叉树的所有结点，按照一定的次序顺序，
存储到一片连续的存储单元中。
完全二叉树的结点编号与线性序列的关系,编号为 i
的结点是 Ti(1≤i≤n),则有：
i>1，则 Ti的双亲编号为 i/2；若 i=1，则 Ti为根结点。
若 2i≤n,则 Ti的左孩子的编号是 2i；否则,Ti无左孩子。
若 2i+1≤n,则 Ti的右孩子的编号是 2i+1；否则,Ti无右孩子。
若 i为奇数且不为 1，则 Ti的左兄弟的编号为 i-1；否则,Ti没有左兄弟。
若 i为偶数且小于 n，则 Ti的右兄弟的编号为 i+1；否则,Ti
没有右兄弟。
二叉树顺序存储结构实例 1 — 完全二叉树：
二叉树顺序存储结构实例 2 — 一般二叉树,
链式存储结构：
概念,二叉树的链表中的结点至少包含三个域：数据域和左、右指针域，如图 7-12（ a）所示；为便于找到结点的双亲，则在结点结构中增加一个指向其双亲结点的指针域，如图 7-12（ b）所示：
实例：
二叉树的遍历遍历,按某指定规则访问树中每个结点，且使得每个结点均被访问一次，且仅被访问一次。
二叉树的遍历方案：
先序遍历（ DLR ）：
访问过程：
访问根结点。
先序遍历根结点的左子树。
先序遍历根结点的右子树。
算法：
void PreOrder (BTree T)
{ if (T == NULL) return ; /*递归出口 */
visite (T -> data ); /*访问结点的数据域 */
if ( T -> lchild != NULL ) PreOrder (T -> lchild );
if ( T -> rchild != NULL ) PreOrder (T -> rchild );}
中序遍历（ LDR）：
访问过程：
中序遍历根结点的左子树。
访问根结点。
中序遍历根结点的右子树。
算法：
void Inorder(BTree T)
{
if(T==NULL) return; /* 递归出口 */
if(T->lchild!=NULL)
Inorder(T->lchild);
visite(T->data); /*访问结点的数据域 */
if(T->rchild!=NULL)
Inorder(T->rchild);
}
后序遍历（ LRD）：
过程：
后序遍历根结点的左子树。
后序遍历根结点的右子树。
访问根结点。
算法：
void Postorder(BTree T)
{
if(T==NULL) return;/* 递归出口 */
if(T->lchild!=NULL)
Postorder(T->lchild);
if(T->rchild!=NULL)
Postorder(T->rchild);
visite(T->data); /*访问结点的数据域 */
}
层次遍历：
算法：
void LevelOrder（ BiTree bt） /*层次遍历二叉树 bt*/
{ BiTree Queue[MAXNODE];
int front,rear;
if (bt==NULL) return;
front=-1;
rear=0;
queue[rear]=bt;
while(front!=rear)
{front++;
Visite(queue[front]->data); /*访问队首结点的数据域 */
if (queue[front]->lchild!=NULL) /*将队首结点的左孩子结点入队列 */
{ rear++;
queue[rear]=queue[front]->lchild;}
if (queue[front]->rchild!=NULL) /*将队首结点的右孩子结点入队列 */
{ rear++;
queue[rear]=queue[front]->rchild;}
}
}
二叉树遍历的应用结点序列,如图所示的二叉树表示表达式
a+b*(c-d)-e/f
前缀表达,先序遍历二叉树来遍历此二叉树，按访问结点的先后次序将结点排列起来,可得到：
- + a * b – c d /ef 。
中缀表示,中序遍历二叉树来遍历此二叉树，得到此二叉树的中序序列,可得到,a + b * c – d – e / f 。
后缀表示,后序遍历二叉树来遍历此二叉树，得到此二叉树的后序序列，可得到 a b c d - * + e f / - 。
查找数据元素：
概念,在 bt为二叉树的根结点指针的二叉树中查找数据元素 x;查找成功时返回该结点的指针；查找失败时返回空指针。
算法：
BTree Search(BTree bt,elemtype x)
{
BTree p;
if(bt==NULL)
return NULL;
if(bt->data==x)
return bt; /*查找成功出口 */
/*在 bt ->lchild为根结点的二叉树中查找数据元素 x*/
if（ bt->lchild！ =NULL）
{
p=Search（ bt->lchild,x）；
if（ p！ = NULL）
return p；
}
if（ bt->rchild！ = NULL） /*在 bt-〉 rchild为根结点的二叉树中查找数据元素 x*/
{
p=Search（ bt->rchild,x）；
if（ p！ =NULL）
return p；
}
return NULL;/*查找失败出口 */
}
线索二叉树线索,利用空指针域，存放指向结点的某种遍历次序下的前驱和后继结点的指针，这种附加的指针称为线索。
线索链表,加上线索的二叉链表。
线索二叉树,相应的二叉树称为线索二叉树。
线索化,对二叉树以某种次序遍历使其变为线索二叉树的过程。
线索二叉树的结点结构各域规定：
中序线索二叉树实例：
线索二叉树的遍历查找结点的后继结点问题 (以后序为例 )，分三种情况：
若点 x是二叉树的根，则其后继为空。
若结点 x是其双亲的右孩子或是其双亲的左孩子且其双亲没有右子树，则其后继即为双亲结点。
若结点 x是其双亲的左孩子，且其双亲有右子树，
则其后继为双亲的右子树上按后序遍历列出的第一个结点。
实例：
线索化过程中，对当前根结点的处理：
若结点 *p有空指针域，则将相应的标志置为 1。
若结点 *p有中序前驱结点 *pre(即 *pre != NULL)
则：
若结点 *pre的右线索标志已建立 (即 pre ->
Rtag==1)，则令 pre -> Rchild指向其中序前驱结点 *p的右线索。
若结点 *pre的左线索标志已建立 (即 pre ->
Ltag==1)，则令 pre -> Lchild指向其中序前驱结点 *p的左线索。
将 pre指向刚刚访问过的结点 *p(即 pre=p)；则在下一次访问一个新结点 *p时,*pre为其前驱结点。
线索二叉树的运算中序线索二叉树,查找结点 *p的中序后继结点,
若 *p的右子树空 (即 p->rtag为 Thread)，则 p-
>rchild为右线索，直接指向 *p的中序后继。
若 *p的右子树非空 (即 p->rtag为 Link)，则 *p的中序后继必是其右子树中第一个中序遍历到的结点。
其算法的时间复杂度不超过树的高度 h，即 O(h)。
中序线索二叉树查找结点 *p的中序前趋结点,
若 *p的左子树为空，则 p->1child为左线索，
直接指向 *p的中序前趋结点。
若 *p的左子树非空，则从 *p的左孩子出发，沿右指针链往下查找，直到找到一个没有右孩子的结点为止。
树的存储结构双亲表示法：
概念,用一组连续的空间存储树中的各个结点，同时在每个结点中附设一个指示器指向其双亲结点在链表中的位置。
实例：
孩子表示法：
概念,使用多重链表，每个结点有多个指针域，其中每个指针指向一棵子树的根结点。
多重链表的结点是同构的,d为树的度多重链表的结点是不同构的,d为结点的度实例：
带双亲的孩子链表孩子兄弟表示法：
概念,每个结点除信息域外，再增加两个分别指向该结点的第一个孩子结点和下一个兄弟结点的指针域 。
实例,
森林与二叉树的转换树转换成二叉树：
方法：
在所有兄弟结点之间加一连线。
对每个结点，除了保留与其长子的连线外，
去掉该结点与其它孩子的连线。
实例：
森林转化成二叉树：
方法,F={T1,T2,…,Tm}是森林，可以把上述森林转换为二叉树的方法做如下定义，即可按如下规则将森林转换成一棵二叉树 B＝（ root,LB,RB）。
若 F为空，即 m＝ 0，则 B为空树。
若 F非空，即 m≠0,则 B的根 root即为森林中第一棵树的根 ROOT（ T1）； B的左子树 LB是从
T1中根结点的子树森林 F1＝ {T11,T12,…,T 1n}转换而成的二叉树 B{T11,T12,…,T 1n}；其右子树 RB是从森林 F’={T 2,…,Tm}转换而成的二叉树
B{T2,…,Tm}。
实例,
二叉树转换成树、森林：
方法,如果 B=（ root,LB,RB）是一棵二叉树，则可按如下规则转换成森林 F＝ {T1,T2,…,Tm}：
若 B为空，则 F为空。
若 B非空，则 F中第一棵树 T1的根 ROOT（ T1）
即为二叉树 B的根 root； T1中根结点的子树森林 F1是由 B的左子树 LB转换而成的森林； F中除 T1之外其余树组成的森林 F’={T 1,T2,…,
Tm}是由 B的右子树 RB转换而成的森林。
实例：
树和森林的遍历前序遍历森林,若森林非空，则按下面规则遍历森林。
访问森林中第一棵树的根结点。
先序遍历第一棵树中根结点的子树森林。
先序遍历除去第一棵树之后剩余的树构成的森林 。
后序遍历森林,若森林非空，则按下面规则遍历森林。
后序遍历森林中第一棵树的根结点的子树森林。
访问第一棵树的根结点。
后序遍历除去第一棵树之后剩余的树构成的森林。
实例：
先序序列,A B E F C D
后序序列,E F B C D A
哈夫曼树及其应用概念：
路径,树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。
路径长度,路径上的分支数目。
树的路径长度,根结点到树中每一结点的路径长度之和。
树的带权路径长度,树中所有叶子结点的带权路径长度之和，即：
哈夫曼树,对于一组带有确定权值的叶结点，带权路径长度 WPL最小的二叉树。
实例：
带权路径长度分别为：
（ a） WPL＝ 7× 2+5× 2+2× 2+4× 2＝ 36
（ b） WPL＝ 7× 3+5× 3+2× 1+4× 2＝ 46
（ c） WPL＝ 7× 1+5× 2+2× 3+4× 3＝ 35
哈夫曼树的构造基本思想：
（ 1）给定的 n个权值 {W1,W2,…,Wn}构成 n棵二叉树的集合 F={T1,T2,…,Tn}，其中每棵二叉树 Ti中只有一个带权为 Wi的根结点，其左右子树均空。
（ 2）在 F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、
右子树上根结点的权值之和。
(3)在 F中删除这两棵树，同时将新得到的二叉树加入 F中。
(4)重复（ 2）和（ 3），直到 F中只剩下一棵二叉树为止 。
实例,{5,11,26,18,34,15,6}构成一棵哈夫曼树。
哈夫曼树在编码问题中的应用前缀编码,设计长短不等的编码，使任何一个字符的编码都不是另一个字符的前缀，以才能保证译码的唯一性，
这种编码称做前缀编码。
哈夫曼编码,利用哈夫曼树构造使电文的编码总长度最短，即以 n种字符出现的次数或频率作为权值，由此得到的二进制前缀编码便称为哈夫曼编码。
