树和二叉树的应用

发表于 | 分类于 | 评论数：

摘要：树的基本概念、二叉树、树和森林、树与二叉树的应用。

树的基本概念

树的定义

树是一种非线性的数据结构。树是若干结点的集合，是由唯一的根和若干棵互不相交的子树组成的。其中每一棵子树又是一棵树，也是唯一的根节点和若干互不相交的子树组成的。由此可见树的定义是递归的。其中需要注意的是结点数为0的树称为空树。

树的基本术语

image-20200910090801458

结点：A、B、C等都是结点，结点不仅包含数据，而且包含指向子树的分支。

结点的度：结点拥有的子树个数或者分支的个数。例如A结点有3棵子树，所以A的结点的度为3。

树的度：树中个结点度的最大值。

叶子结点：指度为0的结点。

非终端结点：指度不为0的结点，除了根结点之外的非终端结点，也叫作内部节点。

孩子：结点的子树的根，如A结点的孩子就是B、C、D

双亲：与孩子定义对应，如B、C、D的双亲就是A

兄弟：同一个双亲的孩子之间互为兄弟，如B、C、D互为兄弟。

祖先：从根到某个结点的路径上的所有结点，都是这个结点的祖先。如K的祖先是A、B、E

子孙：以某个结点为根的子树中的所有结点，都是该结点的子孙，如D的子树为H、I、J、M

层次：从根开始，根为第一次，根的孩子为第二次，以此类推

树的高度（深度）：树中结点的最大层次。

结点的高度（深度）：从根节点到该节点路径上的结点个数

堂兄弟：双亲在同一层的结点互为堂兄弟，如G和H互为堂兄弟。

有序树：树中的结点的子树从左到右是有次序的，不能交换，这样的树叫做有序树

无序树：树中结点的子树没有顺序，可以任意次交换。

丰满树：丰满树即为了理想平衡树，要求除去最底层外，其他层都是满的

森林：若干互不相交的树的集合，例如把A去掉，则剩下的三个子树互不相交，构成一个森林。

树的存储结构

1.顺序存储结构

树的顺序存储结构中最直观的是双亲存储的结构，用以为数组即可实现。int tree[maxSize]。数组下标表示树中的结点，数组元素的内容表示该结点的双亲结点，这样就可以表示一棵树了。

2.链式存储结构

（1）孩子存储结构

孩子存储结构实质上就是图的邻接表存储结构，树是一种特殊的图，把图中多对多的关系改为一对多即可得到树。

（2）孩子兄弟存储结构

孩子兄弟存储结构与树和森林和二叉树的相互转换关系密切。

二叉树的定义

将一般的树加上下面两个限制即可得到二叉树：

1.每个结点最多只有两个子树

2.子树有左右顺序之分

所有的分支结点都有左右孩子结点及并且叶子结点都集中在二叉树的最下一层，这样的二叉树称为满二叉树。对满二叉树进行编号，如果个结点编号与次深度相同的满二叉树相同位置的结点编号钧相同，则为完全二叉树

image-20200910103118995

二叉树的主要性质

1.非空二叉树上叶子结点数等于双分支结点数+1

2.二叉搜索的第i层上最多有2^(i-1)个结点。（i>=1)

3.高度为k的二叉树最多有2^k - 1个结点。

其他待补充……

二叉树的存储结构

1.顺序存储结构

image-20200910105118422

2.链式存储结构

image-20200912232642646

1
2
3
4
5
6
typedef struct BTNode
{
	char data;
	struct BTNode *lchild;
	struct BTNode *rchild;
}BTNode;

二叉树的遍历算法

先序遍历

访问根节点–>先序遍历左子树–>先序遍历右子树

1
2
3
4
5
6
7
8
9
void preorder(BTNode *p)
{
	if(p != NULL)
	{
		Visit(p);	//假设访问函数为Visit
		preorder(p->lchild);	//先序遍历左子树
		preorder(p->rchild);	//先序遍历右子树
	}
}

中序遍历

中序遍历左子树–>访问根节点–>中序遍历右子树

1
2
3
4
5
6
7
8
9
void inorder(BTNode *p)
{
	if(p != NULL)
	{
		inorder(p->lchild);
		Visit(p);
		inorder(p->rchild);
	}
}

后序遍历

后序遍历左子树–>后序遍历右子树–>访问根节点

1
2
3
4
5
6
7
8
9
void postorder(BTNode *p)
{
	if(p != NULL)
	{
		postorder(p->lchild);
		postorder(p->rchild);
		Visit(p);
	}
}

二叉树的深度

1
2
3
4
5
6
7
8
9
10
11
12
int get_tree_depth(BTNode *root)
{
    int ld,rd;
    if(root == NULL)
        return 0;
    else
    {
        ld = get_tree_depth(root->lchild);  //求左子树深度
        rd = get_tree_depth(root->rchild);  //求右子树深度
        return (ld>rd?ld:rd) +1;            //返回左右子树深度最大值+1
    }
}

层次遍历

按照层次进行遍历输出，需要建立一个循环队列。先将二叉树的头结点入队，然后出队列，访问该节点。如果左子树存在则左子树根节点入队，如果右子树存在则右子树根节点入队，然后出队列，对结点进行访问。如此反复直到队列为空。

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
//层次遍历
void leavel(BTNode *node)
{
    int front = 0,rear = 0;
    BTNode *que[MAX_SIZE];
    BTNode *temp_node;
    if(node != NULL)
    {
        rear =(rear + 1)% MAX_SIZE; //循环队列
        que[rear] = node;

        while(front != rear)    //队列不为空的时候出队
        {
            front = (front + 1) % MAX_SIZE;
            temp_node = que[front];
            printf("%3c",temp_node->data);  //访问结点
            if(temp_node->lchild != NULL)   //左子树不为空则入队
            {
                rear = (rear + 1)% MAX_SIZE;
                que[rear] = temp_node->lchild;
            }
            if(temp_node->rchild != NULL)
            {
                rear = (rear + 1) % MAX_SIZE;
                que[rear] = temp_node->rchild;
            }

        }
    }
}

创建二叉树

二叉树以链表的形式存储

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_SIZE 128
// 二叉树的结构定义
typedef struct BTNode
{
    char data;
    struct BTNode *lchild;
    struct BTNode *rchild;
}BTNode;


/*
            二叉树的创建
采取输入格式为：ABD##E##CF###
构建：
                    A
            B               C
        D       E       F       #
      #   #   #   #   #   #

*/
int cnt = 0;
BTNode *create_tree(char *str)
{
    BTNode *root;
    char ch;
    ch = str[cnt];
    ++cnt;
    if(ch == '#')
        return NULL;
    root = (BTNode*)malloc(sizeof(BTNode));
    root->data = ch;
    root->lchild = create_tree(str);
    root->rchild = create_tree(str);
    return root;
}
//先序遍历
void preorder(BTNode *node)
{
    if(node!=NULL)
    {
        printf("%3c",node->data);
        preorder(node->lchild);
        preorder(node->rchild);
    }
}
//中序遍历
void inorder(BTNode *node)
{
    if(node!=NULL)
    {
        preorder(node->lchild);
        printf("%3c",node->data);
        preorder(node->rchild);
    }
}
//后序遍历
void postorder(BTNode *node)
{
    if(node!=NULL)
    {
        preorder(node->lchild);
        preorder(node->rchild);
        printf("%3c",node->data);
    }
}

//层次遍历
void leavel(BTNode *node)
{
    int front = 0,rear = 0;
    BTNode *que[MAX_SIZE];
    BTNode *temp_node;
    if(node != NULL)
    {
        rear =(rear + 1)% MAX_SIZE; //循环队列
        que[rear] = node;

        while(front != rear)    //队列不为空的时候出队
        {
            front = (front + 1) % MAX_SIZE;
            temp_node = que[front];
            printf("%3c",temp_node->data);  //访问结点
            if(temp_node->lchild != NULL)   //左子树不为空则入队
            {
                rear = (rear + 1)% MAX_SIZE;
                que[rear] = temp_node->lchild;
            }
            if(temp_node->rchild != NULL)
            {
                rear = (rear + 1) % MAX_SIZE;
                que[rear] = temp_node->rchild;
            }
        }
    }
}

//深度
int get_tree_depth(BTNode *root)
{
    int ld,rd;
    if(root == NULL)
        return 0;
    else
    {
        ld = get_tree_depth(root->lchild);  //求左子树深度
        rd = get_tree_depth(root->rchild);  //求右子树深度
        return (ld>rd?ld:rd) +1;            //返回左右子树深度最大值+1
    }
}

int main(int argc,char** argv)
{
    BTNode *bt = create_tree("ABD##E##CF###");

	printf("preorderr:\n");
	preorder(bt);
	printf("\n");

	printf("inorder:\n");
	inorder(bt);
	printf("\n");

	printf("postorder:\n");
	postorder(bt);
	printf("\n");

	printf("tree_leave:\n");
    leavel(bt);
	printf("\n");

    printf("tree_depth:\n");
    printf("%3d",get_tree_depth(bt));
	printf("\n");

	return 0;

}

二叉树遍历算法的改进

二叉树的深度优先遍历算法都是用递归函数实现的，效率低下。原因是因为相当于调用一个栈并做了诸如保护线程和恢复现场等复杂操作，才使得代码简短。可以采用二叉树深度优先遍历算法的非递归实现和线索二叉树。

  1. 二叉树深度优先遍历算法是用用户自定义的栈来代替系统栈，也就是用非递归的方式来实现遍历算法。
  2. 线索二叉树是将二叉树线索化，不需要栈来辅助完成遍历操作，更进一步提高效率。

二叉树深度优先遍历算法的非递归实现

先序遍历的非递归算法

将出栈的结点的孩子依照右孩子先入栈，左孩子后入栈的顺序入栈。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//非递归先序遍历
void preorder_nonrecurision(Btree *node)
{
    if(node)   //结点不为空
    {
        Btree *stack[MAX_SIZE];     //定义一个栈
        int top = -1;
        Btree *temp;    //定义一个缓存结点
        stack[++top] = node;    //根节点入栈
        while(top != -1)
        {
            temp = stack[top--];
            printf("%3c",temp->data);
            if(temp->rchild)
                stack[++top] = temp->rchild;
            if(temp->lchild)
                stack[++top] = temp->lchild;
        }
    }
}

中序遍历的非递归算法

入栈时左孩子存在则继续入栈

左孩子不存在则栈顶出栈，出栈元素右孩子存在则入栈

tip：会存在栈空但是遍历未结束的情况，所以判断条件不能像先序遍历那样使用top!=-1来判断，需要使用top!=-1 ||p!=NULL进行判断。

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
//非递归中序遍历
void inorder_nonrecurision(Btree *node)
{
    if(node)
    {
        Btree *stack[MAX_SIZE];
        int top = -1;
        Btree *temp=node;

        while(top != -1 || temp != NULL)
        {
            while(temp) //左孩子存在则左孩子入栈
            {
                stack[++top] = temp;
                temp = temp->lchild;
            }
            if(top != -1)   //队列不为空的情况下出栈
            {
                temp = stack[top--];
                printf("%3c",temp->data);
                temp = temp->rchild;
            }
        }
    }
}

后序遍历的非递归算法

先序遍历序列：A B D E C F

后序遍历序列：D E B F C A

后序遍历逆序：A C F B E D

观察发现,逆后序遍历和先序遍历存在一点联系，逆后序遍历序列只不过是先序遍历过程中对左右子树遍历顺序交换所得到的结果

只需要将先序遍历的左右子树遍历的顺序交换遍历方式并将遍历结果压入栈即可得到后序遍历序列。

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
//非递归后序遍历
void postorder_nonrecurision(Btree *node)
{
    if(node)
    {
        Btree *stack_1[MAX_SIZE];
        Btree *stack_2[MAX_SIZE];
        int top1,top2;
        top1 = top2 = -1;
        Btree *temp;
        stack_1[++top1] = node;
        while(top1 != -1)
        {
            temp = stack_1[top1--];
            stack_2[++top2] = temp; //将出栈结点存入stack_2
            if(temp->lchild)
                stack_1[++top1] = temp->lchild;
            if(temp->rchild)
                stack_1[++top1] = temp->rchild;
        }
        while(top2 != -1)
        {
            temp = stack_2[top2--];
            printf("%3c",temp->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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_SIZE 128

typedef struct Btree
{
    char data;
    struct Btree *lchild;
    struct Btree *rchild;
}Btree;

/*
            二叉树的创建
采取输入格式为：ABD##E##CF###
构建：
                    A
            B               C
        D       E       F       #
      #   #   #   #   #   #

*/
int cnt = 0;
Btree *create_Btree(char *str)
{
    Btree *root;
    char ch;
    ch = str[cnt++];
    if(ch == '#')
        return NULL;
    root = (Btree*)malloc(sizeof(Btree));
    root->data = ch;
    root->lchild = create_Btree(str);
    root->rchild = create_Btree(str);
    return root;

}

//非递归先序遍历
void preorder_nonrecurision(Btree *node)
{
    if(node)   //结点不为空
    {
        Btree *stack[MAX_SIZE];     //定义一个栈
        int top = -1;
        Btree *temp;    //定义一个缓存结点
        stack[++top] = node;    //根节点入栈
        while(top != -1)
        {
            temp = stack[top--];
            printf("%3c",temp->data);
            if(temp->rchild)
                stack[++top] = temp->rchild;
            if(temp->lchild)
                stack[++top] = temp->lchild;
        }
    }
}
//非递归中序遍历
void inorder_nonrecurision(Btree *node)
{
    if(node)
    {
        Btree *stack[MAX_SIZE];
        int top = -1;
        Btree *temp=node;

        while(top != -1 || temp != NULL)
        {
            while(temp) //左孩子存在则左孩子入栈
            {
                stack[++top] = temp;
                temp = temp->lchild;
            }
            if(top != -1)   //栈不为空的情况下出栈
            {
                temp = stack[top--];
                printf("%3c",temp->data);
                temp = temp->rchild;
            }
        }
    }
}

//非递归后序遍历
void postorder_nonrecurision(Btree *node)
{
    if(node)
    {
        Btree *stack_1[MAX_SIZE];
        Btree *stack_2[MAX_SIZE];
        int top1,top2;
        top1 = top2 = -1;
        Btree *temp;
        stack_1[++top1] = node;
        while(top1 != -1)
        {
            temp = stack_1[top1--];
            stack_2[++top2] = temp; //将出栈结点存入stack_2
            if(temp->lchild)
                stack_1[++top1] = temp->lchild;
            if(temp->rchild)
                stack_1[++top1] = temp->rchild;
        }
        while(top2 != -1)
        {
            temp = stack_2[top2--];
            printf("%3c",temp->data);
        }
    }
}

int main()
{
    Btree *bt = create_Btree("ABD##E##CF###");

    printf("preorder_nonrecurision:\n");
    preorder_nonrecurision(bt);
    printf("\n");

    printf("inorder_nonrecurision:\n");
    inorder_nonrecurision(bt);
    printf("\n");

    printf("postorder_nonrecurision:\n");
    postorder_nonrecurision(bt);
    printf("\n");

    return 0;
}

线索二叉树

二叉树非递归算法避免了系统栈的调用，提高了一定的执行效率。而线索二叉树可以将用户栈也省掉，把二叉树的遍历过程线性化，进一步提高效率。

二叉树线索化后进士于一个线性结构，分支结构的遍历操作就转化为近似于线性结构的遍历操作，通过线索的辅助使得寻找当前结点前驱或者后继的平均效率大大提高。

线索二叉树的构造

image-20200916160034330

在二叉树线索化的时候会把树中的空指针利用起来作为寻找当前结点的前驱或者后继的线索，这样就出现一个问题，即线索和树中原有的孩子结点的指针无法区别。上面的设计是为了区分两类指针，其中ltag和rtag为标识域，具体意义为：

1）如果 ltag=0,表示lchild为指针，指向左孩子。如果ltag=1,表示lchild为线索，指向结点的直接前驱。

2）如果 rtag=0,表示rchild为指针，指向右孩子。如果rtag=1,表示rchild为线索，指向结点的直接后继。

二叉树中序线索化

有待更新

哈夫曼树

哈夫曼树也叫最优二叉树，是一类带权路径最短的树，广泛应用于查找（将更经常使用的结点放在树顶，更少使用的放在叶子结点，这也是哈夫曼编码的优点）

相关文章
-------　本文结束　　感谢您的阅读　-------