乐达淄博网站建设制作,网站阶段推广计划,网络规划设计师适合干什么,网站设计接单文章目录
前言
一#xff0c;二叉搜索树的高度 二#xff0c;广度优先VS深度优先
三#xff0c;广度优先的代码实现
四#xff0c;深度优先代码实现
五#xff0c;判断是否为二叉搜索树
六#xff0c;删除一个节点
七#xff0c;二叉收索树的中序后续节点
总结 … 文章目录
前言
一二叉搜索树的高度 二广度优先VS深度优先
三广度优先的代码实现
四深度优先代码实现
五判断是否为二叉搜索树
六删除一个节点
七二叉收索树的中序后续节点
总结 前言
我们上一篇学习了树的基本知识和树的分类二叉搜索树是作为我们学习的重点内容所以我将继续深入学习二叉搜索树 一二叉搜索树的高度 我们来复习一下树的高度和深度 树的高度节点到子叶节点的距离树的深度节点到根节点的距离 接下来我们就要用代码来实现树的高度的计算 #includeiostreamusing 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的计算为例子 左子树 左子树的根是 33 是叶子节点它没有左子树和右子树所以它的左右子树的高度都为 0那么3 的高度是 max(0, 0) 1 1 右子树 右子树的根是 55 是叶子节点它同样没有左右子树所以5 的高度是 max(0, 0) 1 1 我们不难想出再寻找NULL的时候这个是每一个子树的左右子树都是要进行比较的这个就是递归nb的地方然后计算完了4又会跑到右子树进行计算然后最后把左右两个子树进行比较这个后面的1是给子树赋值的 二广度优先VS深度优先 树不再像我们之前所学的链表栈队列这种顺序结构了它是一个非线性结构所以树是有属于自己的遍历方法的 在访问树的节点过程中这个是有先后顺序的按照某个顺序进行访问且每个节点只可以访问一次对于这个遍历我们有两种方法1深度优先 2广度优先 3图搜索技术 这个图搜索技术我们还没有学完图所以我们值考虑前两个方法 1广度优先思想 我们会逐层访问 1我们访问第一层记录9 2我们访问第二层记录715 3我们访问第三层记录461216 4我们访问第四层记录3514 5我们访问第五层记录10 总的次序9715461216351410 先访问同一层次的节点当访问完这个层次的节点再到下一深度的层次继续访问 2深度优先思想 对于这个我们有三种情况 前序rootleftright中序leftrootright后序leftrightroot 第一个为先访问根再访问左子树再访问右子树 顺序9743561512141016 第二个为先访问左子树再访问根再访问右子树 顺序7435691512141016 第三个为先访问右子树再访问左子树再访问根 顺序7435615121410169 就是把子树访问顺序 三广度优先的代码实现 我们这种逐层的访问不就是很像队列么先把根放入队列然后放入孩子然后把根弹出再放入孩子的孩子再把孩子弹出…… 接下来我们来实现这个代码 实际我们运行代码代码会帮我们优化为这样 9/ \7 15/ \ / \4 8 12 16/ \ / \3 5 10 14代码实现 #includeiostream
#includequeueusing 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;queueBstNode*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代码实现 #includeiostream
#includequeueusing 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个孩子或者没有孩子的情况
