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

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