二叉查询树的数据结构于相关操作实现

数据结构

今天我们讲讲树这个结构。与之前的链表，栈，队列不同，之前的这些数据结构都是线性的，而今天的树，则是一种非线性结构。树这种结构，最常见的就是菜单以及win/mac/linux下的目录系统。

DeepinScreenshot_20171017213517.png

通过这张图我们可以很形象的了解目录结构的树型结构，我们以out文件夹为例：out文件夹是一个父文件夹，我们也可以看做是一个根节点，而production是out的一个子文件夹，我们可以称之为子节点，同时，我们又看到，production下还有classes文件夹，我们称classes文件夹为production的子文件夹（子节点），production为classes的父文件夹（父节点），因此，父节点与子节点是相对的，但是，根节点只有一个，就是out文件夹。现在，我们来看AdaperFactory.class这个文件，注意，这是一个文件了，相当于叶子了，他没有再包含文件夹，处于末端，因此这种情况就是树结构中的树叶，没有任何子节点的一个结点。

二叉树是树的一种特殊情形，与普通树结构不同的地方在于，一个节点只能有两个父节点，就像这张图所示（盗用了百度百科的图片）

b999a9014c086e06f719387b01087bf40ad1cb49

这就是二叉树的结构图形展示。

那什么是二叉查询树呢？二叉查询树的定义为：任何一个结点的左子结点的结点的值都小于父节点的值，右子节点的值都大于父节点的值，同时，左子树的任何一个结点的值都小于父节点的值，右子树则相反。二叉树查询树结点存放的数据依照特定要求进行放置的，因此我们很容易知道，根节点的左子树的最左下的结点是整个二叉查询树的最小值，根节点的右子树的最右下的结点存放的整个树的最大值。既然我们知道二叉查询树的结构特点，那么数据结构相关的初始化，插入，删除，遍历操作也应该可以很清楚，但是，树的结构要尤其注意，你要判断待删除的结点是树叶还是有子节点的结点，如果是树叶结点，那么很简单，直接delete这个结点就可以，但如果不是树叶结点呢？我们能简单的直接delete吗？答案显然是不可以的，删除只有一个子节点的结点时，我们只需要将待删除结点的子节点与待删除结点的父节点进行连接，然后删除结点就可以，在删除有两个子节点的结点时，我们需要在右子树递归的去寻找一个符合二叉查询树的要求的结点数据，然后去替换待删除结点，接着递归的删除那个代替的结点。

现在，我们来用代码看看二叉查询树如何实现

首先是头文件的定义

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
#ifndef TREE_SEARCHTREE_H
#define TREE_SEARCHTREE_H

typedef struct TreeNode *Tree;
typedef struct TreeNode *Position;

struct TreeNode {
    int data;
    Tree LeftTree;
    Tree RightTRee;
};
//树的置空
Tree MakeEmpty(Tree T);
//找到某个值在树中的结点位置
Position Find(int x, Tree tree);
//找到二叉查询树中最小的值
Position FindMin(Tree tree);
//找到二叉查询树中最大的值
Position FindMax(Tree tree);
//向二叉查询树中插入一个值
Tree Insert(int x, Tree tree);
//二叉查询树删除制定的结点
Tree Delete(int x, Tree tree);
//计算二叉树的深度
int TreeDepth(Tree tree);
//先序遍历
void PrintTreeFirst(Tree tree);
//后续遍历
void PrintTreeLast(Tree tree);
//中序遍历
void PrintTreeMid(Tree tree);
//销毁二叉树
void DestoryTree(Tree tree);
//统计树叶结点的个数
int CountLeaf(Tree tree);

#endif //TREE_SEARCHTREE_H

然后我们看具体操作函数的执行方式

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
141
142
143
144
145
146
147
#include <iostream>
#include "SearchTree.h"
using namespace std;

//查询二叉树的置孔操作
Tree MakeEmpty(Tree tree) {
    if (tree != NULL) {
        MakeEmpty(tree -> LeftTree);
        MakeEmpty(tree -> RightTRee);
        free(tree);
    }
}

//查询二叉树的销毁
void DestoryTree(Tree tree) {
    if (tree) {
        DestoryTree(tree -> LeftTree);
        DestoryTree(tree -> RightTRee);
        delete(tree);
    }
}

//查找查询二叉树的某个值的位置
Position Find(int x, Tree tree) {
    if (tree -> data == x)
        return tree;
    if (x < tree -> data)
        return Find(x, tree -> LeftTree);
    if (x > tree -> data)
        return Find(x, tree -> RightTRee);
}

//查找查询二叉树的最小值
Position FindMin(Tree tree) {
    if (tree == NULL)
        return NULL;
    if (tree -> LeftTree == NULL)
        return tree;
    return FindMin(tree -> LeftTree);
}

//查找查询二叉树的最大值
Position FindMax(Tree tree) {
    if (tree == NULL)
        return NULL;
    if (tree -> RightTRee == NULL)
        return tree;
    return FindMax(tree -> RightTRee);
}

//插入新的树叶
Tree Insert(int x, Tree tree) {
    if (tree == NULL) {
        Tree new_tree = new TreeNode;
        if (new_tree == NULL)
            return NULL;
        new_tree -> data = x;
        new_tree -> LeftTree = new_tree -> RightTRee = NULL;
        return new_tree;
    } else if (x < tree -> data)
        tree -> LeftTree = Insert(x, tree -> LeftTree);
    else if (x > tree -> data)
        tree -> RightTRee = Insert(x, tree -> RightTRee);
    return tree;
}

//结点的删除
Tree Delete(int x, Tree tree) {
    Position tempCell;
    if (tree == NULL)
        return NULL;
    else if (x < tree -> data)
        tree -> LeftTree = Delete(x, tree -> LeftTree);
    else if (x > tree -> data)
        tree -> RightTRee = Delete(x, tree -> RightTRee);
    else if (tree -> LeftTree &amp;&amp; tree -> RightTRee) {
        tempCell = FindMin(tree -> RightTRee);
        tree -> data = tempCell -> data;
        tree -> RightTRee = Delete(tree -> data, tree -> RightTRee);
    } else {
        tempCell = tree;
        if (tree -> LeftTree == NULL)
            tree = tree -> RightTRee;
        else if (tree -> RightTRee == NULL)
            tree = tree -> LeftTree;
        delete(tempCell);
    }
    return tree;
}

//计算树的深度
int TreeDepth(Tree tree) {
    if (tree == NULL)
        return 0;
    int a, b;
    a = TreeDepth(tree -> LeftTree);
    b = TreeDepth(tree -> RightTRee);
    return a > b ? a + 1 : b + 1;
}

//先序遍历
void PrintTreeFirst(Tree tree) {
    if (tree) {
        cout << tree -> data << " ";
        PrintTreeFirst(tree -> LeftTree);
        PrintTreeFirst(tree -> RightTRee);
    }
}

//中序遍历
void PrintTreeMid(Tree tree) {
    if (tree) {
        PrintTreeMid(tree -> LeftTree);
        cout << tree -> data << " ";
        PrintTreeMid(tree -> RightTRee);
    }
}

//后序遍历
void PrintTreeLast(Tree tree) {
    if (tree) {
        PrintTreeLast(tree -> LeftTree);
        PrintTreeLast(tree -> RightTRee);
        cout << tree -> data << " ";
    }
}

//计算树叶结点的个数
int CountLeaf(Tree tree, int &amp;n) {
    if (tree) {
        CountLeaf(tree -> LeftTree, n);
        CountLeaf(tree -> RightTRee, n);
        if (tree -> LeftTree == NULL &amp;&amp; tree -> RightTRee == NULL)
            n += 1;
    }
}

int main() {
    Tree tree = Insert(6, tree);
    tree = Insert(2, tree);
    tree = Insert(1, tree);
    tree = Insert(5, tree);
    tree = Insert(3, tree);
    tree = Insert(4, tree);
    tree = Insert(8, tree);
    PrintTreeFirst(tree);
}