浙江省建设局城市平台网站,wordpress apicloud,沈阳网站建设优秀公司,营销网站建设培训B树和B树的区别 B树#xff0c;也即balance树#xff0c;是一棵多路自平衡的搜索树。它类似普通的平衡二叉树#xff0c;不同的一点是B树允许每个节点有更多的子节点。 B树内节点不存储数据#xff0c;所有关键字都存储在叶子节点上。B树#xff1a; B树#xff1a; 二叉…B树和B树的区别 B树也即balance树是一棵多路自平衡的搜索树。它类似普通的平衡二叉树不同的一点是B树允许每个节点有更多的子节点。 B树内节点不存储数据所有关键字都存储在叶子节点上。B树 B树 二叉树理论基础 1.种类满二叉树、完全二叉树、二叉搜索树、平衡二叉树。 完全二叉树是最后一行从左到右连续但不一定全满。 二叉搜索树必须有一定顺序。查询和添加都是Ologn因为添加就是查询的过程。 平衡二叉搜索树左右子树高度差的绝对值不超过1。map,set,multimap,multiset底层都是平衡二叉搜索树是红黑树红黑树是一种平衡二叉搜索树。 2.存储方式链表、数组。 链表就是valTreenode* left Treenode *right 数组一开始从0开始左孩子就是2k1右孩子就是2k2 3.遍历方式 深度优先搜索前序中左右、中序左中右、后序左右中。一般用递归实现也可以迭代实现。 广度优先搜索层序遍历是其中一种。 图的深度优先搜索就对应树的前中后序图的广度优先搜索就对应树的层序遍历。 1. 二叉树的前,中后序遍历 - 递归 leetcode144.94.145 20231026 代码随想录又卡了栈与队列最后那题打着C已实现的优先队列的旗号实际上是堆而堆本身又是完全二叉树.....优先队列那题还不是直接拿的priority_queue去实现的还自定义了它的比较规则这又引出一个函数对象的概念总之是无从下手遂转战二叉树。今天看了看二叉树的理论知识感觉还行结果写题的时候又被递归摆了一道完全忘了return和题干给的函数有什么用。 总之题干给的preorderTraversal没动自己重新实现了一个函数调用之即可。下面两题是类似的。 class Solution {
public:void preorder(TreeNode* cur, vectorint vct) {if(cur nullptr){return;}vct.push_back(cur-val);preorder(cur-left,vct);preorder(cur-right,vct);}vectorint preorderTraversal(TreeNode* root){vectorint vct;preorder(root,vct);return vct;}}; 2. 二叉树的前中后序遍历 - 迭代leetcode144.94.145 20231027 迭代分为前后中两种理解起来其实还是很困难的看代码貌似记住了自己写对了但是再过几天让我写是绝对写不出来的 前后之所以说是“一种”因为后序可以由前序倒一下左右再reverse一下数组就能得到。他们遍历和处理的顺序都是一样的而中序就不一样了。 下面来看一下具体的代码~ 前序后序在这里就只放前序了
class Solution {
public:vectorint preorderTraversal(TreeNode* root) {stackTreeNode* stk;vectorint vct;if(root nullptr)return vct;stk.push(root);while(!stk.empty()){TreeNode* cur stk.top();stk.pop();vct.push_back(cur-val);if(cur-right !nullptr)stk.push(cur-right);if(cur-left !nullptr)stk.push(cur-left);}return vct;}
}; 定义一个stk用于模拟递归一个vct用户返回数组。因为要先push root进去所以先得判断一下是否为空。 root被push进去以后只要栈不为空就pop栈顶出来再把刚出的栈顶push到 vct 里面去然后先往栈里push右边再往栈里push左边。这样的话之后vct就会从栈顶开始出就会先被push_back到vct里面去而后又是往复的右左栈入中栈里元素左右vct出。 中序 class Solution {
public:vectorint inorderTraversal(TreeNode* root) {vectorint vct;stackTreeNode* stk;TreeNode* cur root;while(cur ! nullptr || !stk.empty()){if(cur ! nullptr){stk.push(cur);cur cur-left;//入栈然后cur一直到最左边}else{cur stk.top();//已经为空了就取栈头的成为现在的curstk.pop();vct.push_back(cur-val);cur cur-right;}}return vct;}
}; 未完待续
