做音乐网站建设的开发平台,合肥网络科技有限公司做网站,济南网站建设多少费用,logo制作规范理论基础、前中后序遍历的递归法和迭代法、层序遍历 1#xff0c;二叉树的种类满二叉树完全二叉树二叉搜索树平衡二叉搜索树 2#xff0c;存储方式链式存储线式存储 3#xff0c;二叉树的遍历深度优先搜索前序遍历#xff08;递归法、迭代法#xff09;中序遍历#xff0… 理论基础、前中后序遍历的递归法和迭代法、层序遍历 1二叉树的种类满二叉树完全二叉树二叉搜索树平衡二叉搜索树 2存储方式链式存储线式存储 3二叉树的遍历深度优先搜索前序遍历递归法、迭代法中序遍历递归法、迭代法后序遍历递归法、迭代法 广度优先搜索层次遍历迭代法、递归法 4二叉树的定义 1二叉树的种类
满二叉树
除最后一层无任何子节点外每一层上的所有结点都有两个子结点的二叉树。
完全二叉树
一个深度为k的有n个节点的二叉树对树中的节点按从上至下、从左到右的顺序进行编号如果编号为i1≤i≤n的结点与满二叉树中编号为i的结点在二叉树中的位置相同则这棵二叉树称为完全二叉树。
二叉搜索树
二叉搜索树(Binary Search Tree)又名二叉排序树(Binary Sort Tree)。
二叉搜索树是具有有以下性质的二叉树
若左子树不为空则左子树上所有节点的值均小于或等于它的根节点的值。 若右子树不为空则右子树上所有节点的值均大于或等于它的根节点的值。 左、右子树也分别为二叉搜索树。
平衡二叉搜索树
平衡二叉搜索树的任何结点的左子树和右子树高度最多相差1。并且左右两个子树都是一棵平衡二叉树。
容器map、set、multimap、multiset的底层原理都是平衡二叉搜索树 所以map中key和set中的元素都是有序的
unordered map和unordered set的底层原理为哈希表
2存储方式
分为链式存储和线式存储
链式存储
链式存储方式就用指针
线式存储
用的少了解即可
顺序存储的方式就是用数组。
线式存储时有一点i他的左孩子下标为2i1他的右孩子下标为2i2
3二叉树的遍历
分为深度优先搜索和广度优先搜索
深度优先搜索
分为前序遍历、中序遍历、后续遍历 写法可以分为递归法和迭代法
递归的底层原理是栈
确定递归函数的参数和返回值 确定终止条件 确定单层递归的逻辑
迭代法就是模拟递归的过程因为递归的底层原理为栈所以迭代法用栈展示
面试简单的可能需要写出简单的非递归代码
前序遍历递归法、迭代法
中左右 递归法
class Solution {
public:void traversal(TreeNode* cur, vectorint vec) {if (cur NULL) return;vec.push_back(cur-val); // 中traversal(cur-left, vec); // 左traversal(cur-right, vec); // 右}vectorint preorderTraversal(TreeNode* root) {vectorint result;traversal(root, result);return result;}
};迭代法 因为模拟栈的过程前序遍历是中左右但是栈是先进后出的所以入栈顺序为右左中
访问顺序和处理顺序相同后续遍历也是如此所以稍作改动就可以变为后续遍历
class Solution {
public:vectorint preorderTraversal(TreeNode* root) {stackTreeNode* st;vectorint result;if (root NULL) return result;st.push(root);while (!st.empty()) {TreeNode* node st.top(); // 中st.pop();result.push_back(node-val);if (node-right) st.push(node-right); // 右空节点不入栈if (node-left) st.push(node-left); // 左空节点不入栈}return result;}
};中序遍历递归法、迭代法
左中右 递归法
void traversal(TreeNode* cur, vectorint vec) {if (cur NULL) return;traversal(cur-left, vec); // 左vec.push_back(cur-val); // 中traversal(cur-right, vec); // 右
}迭代法 访问顺序和处理顺序不同所以代码和前后续遍历不同
class Solution {
public:vectorint inorderTraversal(TreeNode* root) {vectorint result;stackTreeNode* st;TreeNode* cur root;while (cur ! NULL || !st.empty()) {if (cur ! NULL) { // 指针来访问节点访问到最底层st.push(cur); // 将访问的节点放进栈cur cur-left; // 左} else {cur st.top(); // 从栈里弹出的数据就是要处理的数据放进result数组里的数据st.pop();result.push_back(cur-val); // 中cur cur-right; // 右}}return result;}
};后序遍历递归法、迭代法
左右中 递归法
void traversal(TreeNode* cur, vectorint vec) {if (cur NULL) return;traversal(cur-left, vec); // 左traversal(cur-right, vec); // 右vec.push_back(cur-val); // 中
}迭代法 访问顺序和处理顺序相同
class Solution {
public:vectorint postorderTraversal(TreeNode* root) {stackTreeNode* st;vectorint result;if (root NULL) return result;st.push(root);while (!st.empty()) {TreeNode* node st.top();st.pop();result.push_back(node-val);if (node-left) st.push(node-left); // 相对于前序遍历这更改一下入栈顺序 空节点不入栈if (node-right) st.push(node-right); // 空节点不入栈}reverse(result.begin(), result.end()); // 将结果反转之后就是左右中的顺序了return result;}
};广度优先搜索
层次遍历迭代法、递归法
借助一个队列保存每一层的节点
队列记录当前层的元素个数弹出时按队列里储存的个数弹出
迭代法
class Solution {
public:vectorvectorint levelOrder(TreeNode* root) {queueTreeNode* que;if (root ! NULL) que.push(root);vectorvectorint result;while (!que.empty()) {int size que.size();vectorint vec;// 这里一定要使用固定大小size不要使用que.size()因为que.size是不断变化的for (int i 0; i size; i) {TreeNode* node que.front();que.pop();vec.push_back(node-val);if (node-left) que.push(node-left);if (node-right) que.push(node-right);}result.push_back(vec);}return result;}
};递归法
class Solution {
public:void order(TreeNode* cur, vectorvectorint result, int depth){if (cur nullptr) return;if (result.size() depth) result.push_back(vectorint());result[depth].push_back(cur-val);order(cur-left, result, depth 1);order(cur-right, result, depth 1);}vectorvectorint levelOrder(TreeNode* root) {vectorvectorint result;int depth 0;order(root, result, depth);return result;}
};4二叉树的定义
struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
