树与二叉树的关系

root=1 num=7
孩子表示法的结构定义： 孩子表示法的结构定义：
typedef struct ChildNode /* 孩子链表结点的定义 */ { int Child; struct ChildNode * next; }ChildNode; typedef struct /* 顺序表结点的结构定义 */ { DataType data; ChildNode * FirstChild ; }DataNode; typedef struct /* 树的定义 */ { DataNode nodes[MAX]; /* 顺序表 */ int root, num; /* 根结点指示及结点个数 */ } ChildTree;
三、 孩子兄弟表示法
孩子兄弟表示法又称二叉链表表示法， 孩子兄弟表示法又称二叉链表表示法，表 又称二叉链表表示法 中每个结点设有两个链域， 中每个结点设有两个链域，分别指向该结点的 第一个孩子结点和下一个兄弟（右兄弟）结点。 第一个孩子结点和下一个兄弟（右兄弟）结点。
结点结构: 结点结构
第一孩子 下一兄弟
fch data nsib
孩子兄弟表示法的结点结构定义： 孩子兄弟表示法的结点结构定义：
typedef struct CSNode { DataType data; Struct CSNode *FCh, *Nsib; *CSTree; }CSNode, *CSTree;
孩子兄弟表示法示意图： 孩子兄弟表示法示意图：
三、二叉树转换为树或森林
二叉树转换为树或森林的方法为： 二叉树转换为树或森林的方法为： 若某结点是其双亲的左孩子， （1）若某结点是其双亲的左孩子，则把该结 点的右孩子、右孩子的右孩子、 点的右孩子、右孩子的右孩子、……都与该 都与该 结点的双亲结点用线连起来。 结点的双亲结点用线连起来。 （2）删掉原二叉树中所有双亲结点与右孩子 结点的连线。 结点的连线。 整理由（ ）、（2 （3）整理由（1）、（2）两步所得到的树或 森林，使之结构层次分明。 森林，使之结构层次分明。
E A B F H C G D
2、后根遍历
若树非空，则遍历过程为： 若树非空，则遍历过程为： 从左到右， （1）从左到右，依次后根遍历根结点的每一 棵子树。 棵子树。 A 访问根结点。 （2）访问根结点。
B C F H G D
如图树的后根遍历序列为： 如图树的后根遍历序列为： EBHFGCDA。 。
森林转换为二叉树示意图
B
B E HLeabharlann ICD F GH
E I J
C D F G
J
森林转换为二叉树的实例另见p179的图 的图6.31 森林转换为二叉树的实例另见 的图
递归方法描述森林转换为二叉树: 递归方法描述森林转换为二叉树:
将森林F看作树的有序集F={T 将森林F看作树的有序集F={T1，T2，…,TN}， ,T 它对应的二叉树为B 它对应的二叉树为B（F）： 为空。 （1）若N＝0，则B（F）为空。 N>0， （2）若N>0，则： 二叉树B 的根为森林中第一棵树T 的根； 二叉树B（F）的根为森林中第一棵树T1的根； 的左子树为B ），其 B（F）的左子树为B（{T11，…，T1m}），其 ， 的子树森林； 中{T11，…，T1m}是T1的子树森林； ， 的右子树是B {T2， ， B（F）的右子树是B（{T2，…，TN}）。
2、中序遍历
若森林非空，则遍历方法为： 若森林非空，则遍历方法为： （1）中序遍历森林中第一棵树的根结点的 子树森林。 子树森林。 访问第一棵树的根结点。 （2）访问第一棵树的根结点。 （3）中序遍历除去第一棵树之后剩余的树 构成的森林。 构成的森林。 即：依次从左至右对森林中的每一棵树进行 后根遍历。 后根遍历。
双亲表示法的结点结构定义： 双亲表示法的结点结构定义：
#define MAX 100 typedef struct TNode { DataType data; int parent; }TNode;
一棵树可以定义为： 一棵树可以定义为：
typedef struct { TNode tree[MAX]; int nodenum; /*结点数 结点数*/ 结点数 }ParentTree;
树转换为二叉树示意图
A B E F H C G A B E F H C G H D D E B F H B E F G C D A C G A D
二、森林转换为二叉树
森林转换为二叉树的方法为： 森林转换为二叉树的方法为： 将森林中的每棵树转换成相应的二叉树。 （1）将森林中的每棵树转换成相应的二叉树。 第一棵二叉树不动， （2）第一棵二叉树不动，从第二棵二叉树开 始，依次把后一棵二叉树的根结点作为前一 棵二叉树根结点的右孩子，当所有二叉树连 棵二叉树根结点的右孩子， 在一起后， 在一起后，所得到的二叉树就是由森林转换 得到的二叉树。 得到的二叉树。
A B C E D F G
root
A B C E F G D
优点：便于实现树的各种操作； 优点：便于实现树的各种操作； 可实现树(森林)与二叉树的相互转换。 可实现树(森林)与二叉树的相互转换。
对应的关系： 对应的关系： 树 根 第一孩子 下一兄弟
二叉树 根 左孩子 右孩子
A B C E F G
无兄弟
数据 Data 双亲 Parent 序号 0 1 2 3 4 5 6 Data 1 2 3 4 5 6 7 Parent -1 0 0 1 1 1 2
树的双亲表示法如下图： 树的双亲表示法如下图： 1 2 4 5 6 3 7
双亲表示法的优点： 双亲表示法的优点： 利用了树中每个结点（根结点除外） 利用了树中每个结点（根结点除外） 只有一个双亲结点的性质， 只有一个双亲结点的性质，使得查找某 个结点的双亲结点非常容易。 个结点的双亲结点非常容易。 双亲表示法的缺点： 双亲表示法的缺点： 求某个结点的孩子时，需要遍历整 求某个结点的孩子时， 个表。 个表。
树的孩子链表表示法见p175的图 的图6.26 树的孩子链表表示法见 的图
带双亲的孩子表示法: 带双亲的孩子表示法 孩子表示法示意图: 孩子表示法示意图
data par fch
A B C E G F D
1 2 3 4 5 6 7
A B C D E F G
0 1 1 1 3 3 5
2 5 7
3 6
4
E
A
B
A
B E H I J
C F
D G
H
E I J
C D F G
树的先根遍历： 树的先根遍历：A B E H I J C D F G 对应二叉树的先序遍历 树的后根遍历： 树的后根遍历：H I J E B C F G D A 对应二叉树的中序遍历
二、树的遍历算法
[先根遍历方法一 先根遍历方法一] 先根遍历方法一 void RootFirst(CSTree root) { if (root!=NULL) { Visit(root ->data); /* 访问根结点 */ p= root-> FCh; while (p!=NULL) { RootFirst( p ); /* 访问以 为根的子树 */ 访问以p为根的子树 p = p -> Nsib; } }} [先根遍历方法二 先根遍历方法二] 先根遍历方法二 void RootFirst(CSTree root) { if (root!=NULL) { Visit (root ->data); /*访问根结点 访问根结点*/ 访问根结点 RootFirst (root->FCh); /*先根遍历首子树 先根遍历首子树*/ 先根遍历首子树 RootFirst (root->Nsib); /*先根遍历兄弟树 先根遍历兄弟树*/ 先根遍历兄弟树 }}
A B
无右孩子
D
森林中兄弟树 森林中兄弟树 将转为右子树 将转为右子树
C D F
E G
6.4.2 树、森林与二叉树的相互转换
一、 树转换为二叉树 约定树中每一个结点的孩子结点按从左到 右的次序顺序编号，即把树看作为有序树。 右的次序顺序编号，即把树看作为有序树。 将一棵树转换为二叉树的方法： 将一棵树转换为二叉树的方法： 树中所有相邻兄弟之间加一条连线。 ⑴ 树中所有相邻兄弟之间加一条连线。 对树中的每个结点， ⑵ 对树中的每个结点 ， 只保留其与第一个 孩子结点之间的连线， 孩子结点之间的连线，删去其与其它孩子结 点之间的连线。 点之间的连线。 以树的根结点为轴心， ⑶ 以树的根结点为轴心，将整棵树顺时针 旋转一定的角度，使之结构层次分明。 旋转一定的角度，使之结构层次分明。
三、森林的遍历
森林的遍历方法主要有以下三种： 森林的遍历方法主要有以下三种： 先序遍历 中序遍历 *后序遍历 1、先序遍历 若森林非空，则遍历方法为： 若森林非空，则遍历方法为： 访问森林中第一棵树的根结点。 （1）访问森林中第一棵树的根结点。 先序遍历第一棵树的根结点的子树森林。 （2）先序遍历第一棵树的根结点的子树森林。 （3）先序遍历除去第一棵树之后剩余的树构成 的森林。 的森林。 即：依次从左至右对森林中的每一棵树进 先根遍历。 行先根遍历。
二叉树转换为森林的示意图
A B C D F H I J J E G B C D F H I A E G B E F H C G I J D A
用递归的方法描述其转换
是一棵二叉树， 的根结点， 若B是一棵二叉树，T是B的根结点，L是B的 左子树， 的右子树， 对应的森林F 左子树，R为B的右子树，设B对应的森林F（B） 中含有的n棵树为T 中含有的n棵树为T1,T2, …,Tn，则有： ,T 则有： 为空， 为空的森林（ （1）B为空，则：F（B）为空的森林（n＝0）。 非空， （2）B非空，则： 中第一棵树T 的根为二叉树B的根T F（B）中第一棵树T1的根为二叉树B的根T； 中根结点的子树森林由B的左子树L T1中根结点的子树森林由B的左子树L转换而 成，即F（L）={T11,…,T1m}； ,T 的右子树R转换为F B的右子树R转换为F（B）中其余树组成的森 林，即F(R)＝{ T2, T3, …,Tn}。 F(R)＝ ,T