C++之---树/数据结构_c++的树

一、树
什么是树？
1.1 树（Tree）是n（n>=0）个结点的有限集。n=0时称为空树。在任意一棵非空树中：
（1） 有且仅有一个特定的称为根（Root）的结点；
（2） 当n>1时，其余结点可分为m（m>0）个互不相交的有限集T1、T2、…Tm，其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）。
1.2 度：结点拥有的子树数称为结点的度（Degree）。
树的度是树内各结点的度的最大值。
二者关系：结点的子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲（Parent）。同一个双亲的孩子之间互称兄弟（Sibling）。结点的祖先是从根到该结点所经分支上的所有结点。以某结点为根的子树中的任一结点都称为该结点的子孙。
1.3 其他相关概念：结点的层次（Level）从根开始定义起，根为第一层，根的孩子为第二层。双亲在同一层的结点互为堂兄弟。树中结点的最大层次称为树的深度或高度。
1.4 森林是m（m>=0）棵互不相交的树的集合。

二、树的存储
2.1 双亲表示法
在每个结点中，附设一个指示器指示其双亲结点到链表中的位置。


如图所示：A是没有双亲的所以它的parent的值是-1.
双亲表示法的结点结构定义代码：

//双亲表示法的结点结构定义代码
/*树的双亲表示法结点结构定义*/
#define MAX_TREE_SIZE 100
typedef int TElemType;   /*树结点的数据类型，目前暂定为整型*/
typedef struct PTNode   /*结点结构*/
{
 TElemType data;   /*结点数据*/
 int parent;   /*双亲位置*/
}PTNode;
typedef struct
{
 PTNode nodes[MAX_TREE_SIZE];   /*结点数组*/
 int r, n;   /*根的位置和结点*/
}PTree;
1
2
3
4
5
6
7
8
9
10
11
12
13
14

2.2 孩子表示法
把每个结点的孩子结点排列起来，以单链表作存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空。然后n个头指针又组成一个线性表，采用顺序存储结构，存放进一个一维数组中。

孩子表示法的结构定义代码：

/*树的孩子表示法的定义*/
#define MAX_TREE_SIZE 100
typedef int TElemType;   /*树结点的数据类型，目前暂定为整型*/
typedef struct CTNode   /*孩子结点*/
{
 int child;
 struct CTNode* next;
}*ChildPtr;
typedef struct   /*表头结构*/
{
 TElemType data;
 ChildPtr firstchild;
}CTBox;
typedef struct   /*树结构*/
{
 CTBox nodes[MAX_TREE_SIZE];   /*结点数组*/
 int r, n;   /*根的位置和结点数*/
}CTree;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2.3 双亲孩子表示法：

如上图所示，双亲孩子表示法就是在孩子表示法的基础之上加上一个存储空间用来存储该结点的双亲结点。
2.4 孩子兄弟表示法（实际上是把一棵复杂的树变成了一棵二叉树）
任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。就是把第一个孩子为左指针（firstchild），它的兄弟右指针（rightsib）。

孩子兄弟表示法结构定义：

typedef struct CSNode
{
 TElem data;
 struct CSNode* firstchild, * rightsib;
}CSNode,*CSTree;
1
2
3
4
5

三、二叉树
3.1 二叉树的存储结构
（1） 二叉树顺序存储结构
按照补充为完全二叉树的形式，以数组的方式进行存储，没有的位置为空。
（2） 二叉链表
一个数据域和两个指针域：

/*二叉树的二叉树链表结点结构定义*/
typedef struct BitNode /* 结点结构*/
{
TElemType data;
struct BiTNode *lchild, *rchild;
} BiTNode,*BiTree;
1
2
3
4
5
6

3.2 二叉树的遍历
二叉树的遍历是指从根结点出发，按照某种次序访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。此处说明树的遍历就像递归一样，每一个结点本身也是一棵树。

前序遍历：根左右
void PreOrderTraverse(BiTree T)
{
if(T==NULL)
return;
printf(“%c”,T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
中序遍历：左根右
void InOrderTraverse(BiTree T)
{
if(T==NULL)
return;
InOrderTraverse(T->lchild);
printf(“%c”,T->data);
InOrderTraverse(T->rchild);
}
后序遍历：左右根
void PostOrderTraverse(BiTree T)
{
if(T==NULL)
return;
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
printf(“%c”,T->data);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

3.3 二叉树的建立


对于一个普通二叉树来说，仅仅只有一个前序，是无法确定一个二叉树，有一个办法就是将二叉树中的每个结点的空指针引出一个虚结点，其值为一个特值，比如“#”。称这种树为原二叉树的扩展二叉树。扩展二叉树就可以做到一个遍历序列确定一棵二叉树了。把前序遍历序列AB#D##c##用键盘挨个输入就可以了。

/*按前序输入二叉树中结点的值（一个字符）*/
/* #表示空树，构造二叉链表表示二叉树T。*/
void CreateBiTree(BiTree *T)
{
 TElemType ch;
 scanf("%c",&ch);
 if (ch == "#")
  *T = NULL;
 else
 {
  *T = (BiTree)malloc(sizeof(BiTNode));
  if (!*T)
   exit(OVERFLOW);
  (*T)->data=ch; /*生成根结点*/
  CreateBiTree(&(*T)->lchild);/*构造左子树*/
  CreateBiTree(&(*T)->rchild);/*构造右子树*/
 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

其实建立二叉树，也是利用了递归的原理。只不过在原来应该是打印结点的地方，改成了生成结点、给结点赋值的操作而已。

四、树、森林与二叉树的转换
4.1 树转换为二叉树
前面所提到的孩子兄弟表示法，实际上就是把树转换为二叉树的方法，在此不再多说。

4.2 森林转换为二叉树
在孩子兄弟表示法转换为二叉树的过程中，就知道根结点是没有右子树的，因为它没有兄弟，所以对于多个树的森林来说，它们就是兄弟，也就是右子树。

4.3 二叉树转换为树
二叉树转换为树，就是树转换为二叉树的逆过程。
一个结点的左子树，是它的左子树，该左子树的右子树都是该结点的一棵棵右孩子。

4.4 二叉树转换为森林
就是先把根结点的右子树依次拆开为一棵棵树，再按照二叉树转换为树的方法将一棵棵树转换。