树与二叉树(五)

本篇文章简单介绍树和森林的表示方法、森林与二叉树的关系以及树和森林的简单遍历

树和森林的表示方法

树的三种存储结构

1
2
3
双亲表示法
孩子链表表示法
树的二叉链表(孩子-兄弟)存储表示法
  • 双亲表示法:数组的两部分,一部分存储data,另一部分存储双亲的下标

结点结构: data | parent

类型描述:

1
2
3
4
5
#define MAX_TREE_ZISE 100
typedef struct PTNode {
elem data;
int parent; //双亲位置域
}PTNode;

树结构:

1
2
3
4
5
typedef struct {
PTNode nodes[MAX_TREE_SIZE];
int r; //根结点的位置
int n; //结点个数
}PTree;
  • 孩子链表表示法:用链表表示孩子,并将孩子(链表)串成串

孩子结点结构: child | nextChild

类型描述:

1
2
3
4
typedef struct CTNode {
int child;
struct CTNode nextChild;
}*childPtr;

双亲结点结构:data | firstChild

类型描述:

1
2
3
4
typedef struct {
elem data;
childPtr firstChild; //孩子链的头指针
}CTBox;

树结构:

1
2
3
4
5
typedef struct {
CTBox nodes[MAX_TREE_SIZE];
int r; //根节点的位置
int n; //结点数
}CTree;
  • 树的二叉链表(孩子-兄弟)存储表示法:左指针域存放孩子,右指针域存放兄弟

结点结构:firstChild | data | nextSibling

类型描述:

1
2
3
4
typedef struct CSNode {
elem data;
struct CSNode *firstChild, *nextSibling;
}CSNode, *CSTree;

森林和二叉树的关系

设森林

1
2
F = (T1,T2,…,Tn);
T1 = (root, t11,t12,…,t1m);

设二叉树

1
B = (LBT, node(root), RBT);

由森林转化为二叉树的转换规则为

若F为空,则B为空
否则:
由root(T1)对应得到node(root)
由(t11,t12,…,t1m)对应得到LBT
由(T2,T3,…,Tn)对应得到RBT

由二叉树转换为森林的规则为

若B为空,则F为空
否则:
由node(root)对应得到root(T1)
由LBT对应得到(t11,t12,…,t1m)
由RBT对应得到(T2,T3,…,Tn)

由此,树和森林的各种操作均与二叉树的各种操作相对应

应当注意的是,和树对应的二叉树,其左、右子树的概念已改变为:左是孩子,右是兄弟

一棵树转换为二叉树的思路,主要根据树的孩子-兄弟而来的,方法是:

1
2
3
树中所有兄弟结点间加一条连线
对树中的每个结点,对树中的每个结点,只保留其与第一个孩子结点之间的连线,删去其与其他孩子结点间的连线
以树的根节点为轴心,将整棵树顺时针旋转一定的角度,使之结构层次分明
可以证明,树做这样的转换所构成的二叉树是唯一的。

将森林转换为二叉树

森林是若干树的集合,树可以转换为二叉树,森林同样可以。因此,森林也可以方便的用兄弟孩子链表表示。

1
2
3
将森林中的每棵树转换成相应的二叉树
第一棵二叉树不动,从第二棵二叉树开始,依次把后一棵二叉树的根节点作为前一棵二叉树的右孩子
当所有二叉树连在一起后,所得到的二叉树就是森林转换的二叉树。

二叉树还原为树或者森林

树和森林都可以转换为二叉树,二者的不同是:树转换成的二叉树,其根节点必然无右孩子;二森林转换后二叉树,其根节点必然有右孩子。

1
2
3
若某结点是其双亲的左孩子,则把该结点的右孩子,右孩子的右孩子。。。都与该结点的双亲结点链接起来
删除原二叉树中所有双亲结点与右孩子结点的连线
整理由1、2两步得到的树或森林,使其层次分明

树和森林的遍历

  • 树的遍历

树的遍历可有以下搜索路径:

先根次序遍历:若树不空,则先访问根结点,然后依次先根遍历各棵子树(其结果与二叉树的先序遍历结果一样)
后根次序遍历:若树不空,则先依次后根遍历各棵子树,然后访问根结点(其结果与二叉树的中序遍历一样)
按层次遍历:若树不空,则自上而下自左而右访问树中的每个结点
  • 森林的遍历

可以分解成三部分

1
2
3
森林中第一棵树的根节点
森林中第一棵树的子树森林
森林中其他树构成的森林
先序遍历:若森林不空,则访问森林中的第一棵树的根节点;先序遍历森林中第一棵树的子树森林;先序遍历森林中(除第一棵树之外)其余树构成的森林
中序遍历:若森林不空,则中序遍历森林中第一棵树的子树森林;访问森林中第一棵树的根节点;中序遍历森林中(除第一棵树之外的)其余树构成的森林。即:依次从左至右对森林中的每一棵树进行中序遍历

树的遍历与二叉树遍历的对应关系

1
2
3
树		森林		二叉树
先根遍历 先序遍历 先序遍历
后根遍历 中序遍历 中序遍历

例题1:求森林的深度

设树的存储结构为孩子兄弟链表

1
2
3
4
5
6
7
8
9
10
11
12
typedef struct CSNode {
elemType data;
struct CSNode *firstChild, *nextSibling;
}CSNode, *CSTree;
int depth(CSTree T) {
if (T == NULL) return 0;
else {
d1 = depth(T ->firstChild);
d2 = depth(T -> nextSibling);
return max(d1 + 1; d2);
}
}

例题2:编写递归算法,求二叉树中以元素值为x的结点为根的子树的深度

分析:本题主要是利用遍历算法实现查找值为x的结点的操作,以及求二叉树的深度的操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int getSubDepth(BiTree T, int x) {
if (T -> data == x) {
//找到值为x的结点,并求其深度
printf(“%d\n”, getDepth(T));
exit 1;
}else {
if (T -> lChild)
//在左子树中继续查找
getSubDepth(T -> lChild, x);
if (T -> rChild)
//在右子树中继续查找
getSubDepth(T -> rChild, x);
}
}
int getDepth(BiTree T) {
//求子树深度的递归算法
if (!T) return 0;
else {
m = getDepth(T -> lChild);
n = getDepth(T -> rChild);
return (m > n ? m : n) + 1;
}
}