数据结构 树2

文章目录

前言

一，二叉搜索树的高度

 二，广度优先VS深度优先

三，广度优先的代码实现

四，深度优先代码实现

五，判断是否为二叉搜索树

六，删除一个节点

七，二叉收索树的中序后续节点

总结

---

前言

我们上一篇学习了树的基本知识和树的分类，二叉搜索树是作为我们学习的重点内容，所以我将继续深入学习二叉搜索树

---

一，二叉搜索树的高度

我们来复习一下树的高度和深度

树的高度	节点到子叶节点的距离
树的深度	节点到根节点的距离

接下来我们就要用代码来实现树的高度的计算

#include<iostream>using namespace std;struct BstNode {BstNode* left;int data;BstNode* right;
};BstNode* Insert(BstNode* root, int x);
BstNode* GetNode(int x);
int Hight(BstNode* rtoot);int main() {BstNode* root = NULL;root = Insert(root, 6);root = Insert(root, 9);root = Insert(root, 10);root = Insert(root, 8);root = Insert(root, 4);root = Insert(root, 5);root = Insert(root, 3);int hight = Hight(root);cout << hight << endl;
}/*6/     \4       9/   \   /   \3     5 8    10
*/BstNode* Insert(BstNode* root, int x) {if (root == NULL) {root = GetNode(x);return root;}else if (root->data >= x) {root->left = Insert(root->left, x);}else if (root->data < x) {root->right = Insert(root->right, x);}return root;
}BstNode* GetNode(int x) {BstNode* newNode = new BstNode();newNode->data = x;newNode->left = NULL;newNode->right = NULL;return newNode;
}int Hight(BstNode* root) {if (root == NULL) {return -1;}int lefthight = Hight(root->left);int righthight = Hight(root->right);return max(lefthight, righthight) + 1;
}

代码所表示的树的结构图 

       6/     \4       9/   \   /   \
3     5 8    10

代码里的计算高度

int Hight(BstNode* root) {if (root == NULL) {return -1;}int lefthight = Hight(root->left);int righthight = Hight(root->right);return max(lefthight, righthight) + 1;
}

分析

我们这里如果根节点是空，高度就是-1，这个是规定的
max函数

如果没有接触过C++的，这个max是系统自己给的函数，你也可以自己写，就是我们以往写两个数字比较出最大的数字是一样的
递归

我们这里用的是递归的方法进行了计算，这里就是不断地寻找NULL的节点，我们拿4的计算为例子

左子树：

• 左子树的根是 3
• 3 是叶子节点，它没有左子树和右子树，所以它的左右子树的高度都为 0
• 那么，3 的高度是 max(0, 0) + 1 = 1

右子树：

• 右子树的根是 5
• 5 是叶子节点，它同样没有左右子树
• 所以，5 的高度是 max(0, 0) + 1 = 1

我们不难想出，再寻找NULL的时候，这个是每一个子树的左右子树都是要进行比较的，这个就是递归nb的地方，然后计算完了4，又会跑到右子树进行计算，然后最后把左右两个子树进行比较，这个后面的+1是给子树赋值的

 二，广度优先VS深度优先

树不再像我们之前所学的链表，栈，队列这种顺序结构了，它是一个非线性结构，所以树是有属于自己的遍历方法的

在访问树的节点过程中，这个是有先后顺序的，按照某个顺序进行访问，且每个节点只可以访问一次，对于这个遍历，我们有两种方法：1，深度优先    2，广度优先    3，图搜索技术
这个图搜索技术，我们还没有学完图，所以我们值考虑前两个方法

1，广度优先思想

我们会逐层访问

1，我们访问第一层，记录9
2，我们访问第二层，记录7，15
3，我们访问第三层，记录4，6，12，16
4，我们访问第四层，记录3，5，14
5，我们访问第五层，记录10
总的次序：9，7，15，4，6，12，16，3，5，14，10

先访问同一层次的节点，当访问完这个层次的节点，再到下一深度的层次继续访问

2，深度优先思想

对于这个我们有三种情况

前序	<root><left><right>
中序	<left><root><right>
后序	<left><right><root>

第一个为先访问根，再访问左子树，再访问右子树 
顺序：9，7，4，3，5，6，15，12，14，10，16
第二个为先访问左子树，再访问根，再访问右子树 
顺序：7，4，3，5，6，9，15，12，14，10，16
第三个为先访问右子树，再访问左子树，再访问根 
顺序：7，4，3，5，6，15，12，14，10，16，9

就是把子树访问顺序

三，广度优先的代码实现

我们这种逐层的访问不就是很像队列么，先把根放入队列，然后放入孩子，然后把根弹出，再放入孩子的孩子，再把孩子弹出……

接下来我们来实现这个代码 

实际我们运行代码，代码会帮我们优化为这样

         9/   \7     15/ \    /  \4   8  12   16/ \     / \3   5   10  14

代码实现

#include<iostream>
#include<queue>using namespace std;struct BstNode {BstNode* left;int data;BstNode* right;
};BstNode* Insert(BstNode* root, int x);
BstNode* GetNode(int x);
void leveread(BstNode* root);int main() {BstNode* root = NULL;root = Insert(root, 9);  // 根节点root = Insert(root, 7);  // 左子树root = Insert(root, 15); // 右子树root = Insert(root, 4);  // 7 的左子树root = Insert(root, 8);  // 7 的右子树root = Insert(root, 12); // 15 的左子树root = Insert(root, 16); // 15 的右子树root = Insert(root, 3);  // 4 的左子树root = Insert(root, 5);  // 4 的右子树root = Insert(root, 10); // 12 的左子树root = Insert(root, 14); // 12 的右子树leveread(root);
}BstNode* Insert(BstNode* root, int x) {if (root == NULL) {root = GetNode(x);return root;}else if (root->data > x) {root->left = Insert(root->left, x);}else if (root->data < x) {root->right = Insert(root->right, x);}return root;
}BstNode* GetNode(int x) {BstNode* newNode = new BstNode();newNode->data = x;newNode->left = NULL;newNode->right = NULL;return newNode;
}void leveread(BstNode* root) {if (root == NULL)return;queue<BstNode*>Q;Q.push(root);while (!Q.empty()){BstNode* current = Q.front();cout << current->data << " ";if (current->left!=NULL) {Q.push(current->left);}if (current -> right != NULL) {Q.push(current->right);}Q.pop();}
}

我们来看这个广度搜索的代码，最后面的函数就是把所有的元素放入到队列里面，然后再进行读取弹出，我们利用队列的顺序，一一的把这个孩子的孩子都放入到队列里面

时间为O(n)

四，深度优先代码实现

前序

         9/   \7     15/ \    /  \4   8  12   16/ \     / \3   5   10  14

代码实现

#include<iostream>
#include<queue>using namespace std;struct BstNode {BstNode* left;int data;BstNode* right;
};BstNode* Insert(BstNode* root, int x);
BstNode* GetNode(int x);
void preread(BstNode* root);int main() {BstNode* root = NULL;root = Insert(root, 9);  // 根节点root = Insert(root, 7);  // 左子树root = Insert(root, 15); // 右子树root = Insert(root, 4);  // 7 的左子树root = Insert(root, 8);  // 7 的右子树root = Insert(root, 12); // 15 的左子树root = Insert(root, 16); // 15 的右子树root = Insert(root, 3);  // 4 的左子树root = Insert(root, 5);  // 4 的右子树root = Insert(root, 10); // 12 的左子树root = Insert(root, 14); // 12 的右子树preread(root);
}BstNode* Insert(BstNode* root, int x) {if (root == NULL) {root = GetNode(x);return root;}else if (root->data > x) {root->left = Insert(root->left, x);}else if (root->data < x) {root->right = Insert(root->right, x);}return root;
}BstNode* GetNode(int x) {BstNode* newNode = new BstNode();newNode->data = x;newNode->left = NULL;newNode->right = NULL;return newNode;
}void preread(BstNode* root) {if (root == NULL) {return;}cout << root->data << " ";preread(root->left);preread(root->right);
}

分析

这个就是把这个cout放到递归上面，为什么呢？如果不知道证明你基础太差了，回炉重造吧，然后进入递归，我们会把左边的全部都找完，因为只要有left为NULL则会返回去找左子树的右子树的值，然后进入的根的左子树的时候，就会跳到根的右子树进行查找，先进去右子树的左子树，然后再进入到右子树的右子树

中序跟后序跟这个前序差不多，这里放了代码，读者可以自行思考

中序

void Inread(BstNode* root) {if (root == NULL) {return;}Inread(root->left);cout << root->data << " ";Inread(root->right);
}

后序

void proread(BstNode* root) {if (root == NULL) {return;}proread(root->left);proread(root->right);cout << root->data << " ";
}

时间为O(n) 

五，判断是否为二叉搜索树

 下面这个代码的时间复杂度为O(n)

​
bool Isreallytree(BstNode* root,int minvalue,int maxvalue) {if (root == NULL)return true;if (root->data > minvalue&& root->data < maxvalue&& Isreallytree(root->left, minvalue, root->data)&& Isreallytree(root->right, root->data, maxvalue))return true;elsereturn false;
}​

 分析
我们再if里面进行不断地判断

逻辑梳理

每次我进行递归地时候，先进行左子树的判断，然后对比这个左子树的最大值和最小值，这个最大值每次是需要不断地改进地，就是这个节点，然后当我们地左子树地左边全部判断完了之后，就会执行right语句，也就是去判断这个树地右边进行判断，然后再到根的右子树进行判断，最后决定是返回true还是false

六，删除一个节点

这个东西就比较复杂，因为我们删除之后还要恢复树的平衡

我们把删除的情况分为:1，删除子叶节点    2，删除有两个孩子的节点   3，删除有一个孩子的节点

1,删除子叶节点

我们可以看到，我们可以直接删除即可

直接删除

2，删除含有一个孩子的节点

 我们不难看出，当我们删除一个节点的时候，我们直接把这个节点删除，然后把这个节点跟上就好了，十分的简单，如果你怕有风险，可以试试3或者13，我们试一下，你会发现这都是没有问题的

先连接当前节点的下一个节点，然后再把这个节点删除

3，删除有两个孩子的节点

我们可以看到这个有两种方法

方法一：
就是把15这个节点删除，然后在左子树寻找最大值放到删除的节点
方法二：
就是把15这个节点删除，然后再右子树寻找最小值放到删除的节点

在左子树寻找最大值，在右子树寻找最大值

接下来我们就用代码来实现

BstNode* remove(BstNode* root, int data) {if (root == NULL) {return root;}else if (data < root->data) {root->left = remove(root->left, data);}else if (data < root->data) {root->right = remove(root->right, data);}else {//NO childrenif (root->left == NULL && root == NULL) {delete root;root = NULL;return root;}//One childrenelse if (root->left == NULL) {BstNode* temp = root;root = root->right;delete temp;return root;}else if (root->right == NULL) {BstNode* temp = root;root = root->left;delete temp;return root;}//two childrenelse {BstNode* temp = MAX(root->left);root->data = temp->data;root->left = remove(root->left, temp->data);}}
}BstNode* MAX(BstNode* root) {if (root == NULL) {cout << "未找到" << endl;return NULL;}BstNode* current = root;while (current -> right != NULL) {current = current->right;}return current;
}

 这个MAX就不用多说了，这个就是不断地到树的最右边进行查找，我们来看看这个删除的代码

第一部分

if (root == NULL) {return root;
}
else if (data < root->data) {root->left = remove(root->left, data);
}
else if (data < root->data) {root->right = remove(root->right, data);
}

这个是我们进行查找到这个值，直到我们找到那个值跳到else语句里面，这个为什么前面要有一个root->left/right进行接收呢？这个就是我们上一篇文章讨论的问题，我们需要不断地接受新的子树，不可以还是为原来地子树

第二部分

//NO children
if (root->left == NULL && root == NULL) {delete root;root = NULL;return root;
}

这个是我直接删除叶子节点

第三部分

//One children
else if (root->left == NULL) {BstNode* temp = root;root = root->right;delete temp;return root;
}
else if (root->right == NULL) {BstNode* temp = root;root = root->left;delete temp;return root;
}

 这个是我们需要进行左右子树的删除我们root节点，这个节点我们用一个指针指着，然后把这个root节点改掉，改成指向root->right，然后返回这个root删除temp，左右子树都是一样的

第四部分

//two children
else {BstNode* temp = MAX(root->left);root->data = temp->data;root->left = remove(root->left, temp->data);
}

这个就是我们把这个最大值找打，然后赋予给这个删除的地方，接下来我们就要找到这个节点并且删除，当我们找到之后，我们就又可以判断这个节点是哪一种，如果为两个孩子还要进行递归，如果为其他两种情况的话就是结束了

这个就是把两个孩子变成一个孩子或者没有孩子的情况 

七，二叉收索树的中序后续节点

这个就是让你去判断你要使用中序的方法读取的那个节点的后面那个节点是多少，这个读者可以自行思考，后续也会更新这个代码的实现方法，这个就是让你用中序方法，假设为7，让你判断7后面那个几点为多少

---

总结

1，二叉搜索树的高度的计算
就是利用递归找到树的最低端头，先进行左子树的进行判断，然后在进行右子树的判断

2，广度优先VS深度优先
这两个就是，广度优先就是利用队列的方法把对应的推入到队列里面，然后再进行cout，然后利用pop弹出

3，判断是否为二叉搜索树
这个就是利用二叉树的性质，找到最大值和最小值，然后进行判断，运用递归，注意判断每个子树的时候要修改最值

4，删除节点
这个就是有三个方法，无孩子，1个孩子，2个孩子，2个孩子就是寻找最值然后再降为1个孩子或者没有孩子的情况