数据结构(七)——树与二叉树

​ 树是数据结构中的一种非线性结构,树形结构节点间的关系是除了头节点(根 root)外,每个节点都存在唯一的前驱,但不唯一的后继,也就是说树形结构中节点的关系是一对多的关系,这篇文章主要说一下代码方面实现的过程,理论上设计的比较少

普通树的定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//双亲存储结构
typedef struct {
int data;
int parent;//指向双亲位置
}PTree[MAXSIZE];

//孩子链存储指针
typedef struct node {
int data;
node* sons[MAXSIZE];//指向孩子节点
}TSonNode;

//孩子兄弟链存储结构
typedef struct tnode {
int data;
tnode *hp;//指向兄弟
tnode *vp;//指向孩子节点
}TSBNode;

​ 另外树的操作,我将通过二叉树实现并说明实现原理

树——二叉树

​ 二叉树是一种十分常用的特殊的树状存储结构,由一个根节点(root)和根节点左右两侧的左子树和右子树组成,一棵二叉树的每个节点最多只能含有两个子节点,且要区分开左孩子和右孩子

​ 满二叉树和完全二叉树是二叉树中的两种状态,满二叉树即除最底层的节点外,每个节点都拥有自己的左孩子和右孩子,完全二叉树的特点则是最多只有下面两层的节点度数小于二,并且最下面一层的叶节点都依次排在该层最左边的位置上

​ 同样也是因为二叉树树状存储结构的特性,在各种操作的实现算法中会经常使用递归操作

二叉树的存储结构

​ 二叉树的存储结构分为顺序存储和链式存储

​ 在二叉树的顺序存储结构中,想要查找一个结点的双亲和孩子节点都很容易,但是对于一般的二叉树来说,空间的浪费十分惊人,所以这里我们主要讨论二叉树的链式存储结构

二叉树的链式存储结构

​ 除了定义必要的指针外,二叉链比较节省存储空间;在二叉链中,查找一个节点的孩子很容易,但是查找双亲不方便

定义

1
2
3
4
5
6
7
8
//二叉链,二叉树的链式存储结构
typedef struct DTnode {
int data;
DTnode *lchild, *rchild;
}DTnode;

stack<DTnode*> s;
//栈在初始化二叉树时使用

创建二叉链

​ 创建二叉链,是比较复杂的操作,这个操作的思想是,通过一个 “1(2(3(,4)),5(6,7))” 这种可以表示二叉树中每个节点的值的字符串,在遍历这个字符串的过程中,通过不同位置字符的不同来运行不同的代码实现创建二叉树

​ ch 是用来记录当前遍历位置字符的变量,从 str 的第一个字符开始遍历,当前根节点;一定是为空的,所以把第一个元素的值设置成头节点的值,使用栈的原理,如果遇到 ‘(’ 就先将当前的节点 p 进栈,之后根据 k 的值,来决定将数据赋给栈顶元素的左孩子还是右孩子,最后在遇到 ‘)’ 时就代表当前栈的双亲结点已经定义完,就弹出他

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
28
29
30
DTnode *CreateDTnode(string str) {
DTnode *b ;
DTnode *p;
int k, j = 0;
char ch;
b = NULL;
ch = str[j];
while (ch != '\0') {
switch (ch) {
case '(': s.push(p); k = 1; break;
case ')': s.pop(); break;
case ',': k = 2; break;
default:
p = (DTnode *)malloc(sizeof(DTnode));
p->data = ch - '0';
p->lchild = p->rchild = NULL;
if (b == NULL)
b = p;
else {
switch (k) {
case 1: s.top()->lchild = p; break;
case 2: s.top()->rchild = p; break;
}
}
}
j++;
ch = str[j];
}
return b;
}

二叉树深度

​ 通过递归操作来计算二叉树的深度

1
2
3
4
5
6
7
8
9
10
int DTnodeDepth(DTnode *b) {
int lchilddep, rchilddep;
if (b == NULL)
return 0;
else {
lchilddep = DTnodeDepth(b->lchild);
rchilddep = DTnodeDepth(b->rchild);
return (lchilddep > rchilddep) ? (lchilddep + 1) : (rchilddep + 1);
}
}

打印二叉树

1
2
3
4
5
6
7
void PTree(DTnode *dt) {
if (dt == NULL)
return;
cout << dt->data << endl;
PTree(dt->lchild);
PTree(dt->rchild);
}

查找节点

​ 同样是通过递归算法,查找符合给定值的节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
DTnode *FindNode(DTnode *b, int x) {
DTnode *p;
if (b == NULL)
return NULL;
else if (b->data == x)
return b;
else {
p = FindNode(b->lchild, x);
if (p != NULL)
return p;
else
return FindNode(b->rchild, x);
}
}

二叉树的遍历

​ 图片加不上去实在是太难受了!口述吧!

​ 先给一个二叉树

​ A(B(D,F(E,)),C(G(,H),I))

先序遍历

​ 先序遍历的顺序是先遍历根节点,再遍历左子树,最后遍历右子树

​ 例子中给的二叉树,按照先序遍历排列得到的就是

​ ABDFECGHI

1
2
3
4
5
6
7
8
void FOrder(DTnode *dt) {
//先序遍历
if (dt == NULL)
return;
cout << dt->data << " ";
FOrder(dt->lchild);
FOrder(dt->rchild);
}

中序遍历

​ 中序遍历的顺序是先遍历左子树,访问根节点,再遍历右子树

​ 结果为:DBEFAGHCI

1
2
3
4
5
6
7
8
void COrder(DTnode *dt) {
//中序遍历
if(dt == NULL)
return;
COrder(dt->lchild);
cout << dt->data << endl;
COrder(dt->rchild);
}

后序遍历

​ 后序遍历的顺序是先遍历左子树,再遍历右子树,最后访问根节点

​ 结果为:DEFBHGICA

1
2
3
4
5
6
7
8
void LPerOrder(DTnode *dt) {
//后序遍历
if (dt == NULL)
return;
LPerOrder(dt->lchild);
LPerOrder(dt->rchild);
cout << dt->data << endl;
}
-------------本文结束感谢您的阅读-------------