潍坊建设银行网站,怎么做网站邮箱,wordpress资源类主题,天元建设集团有限公司滨州分公司二叉树的种类二叉树的主要形式#xff1a;满二叉树和完全二叉树。满二叉树深度为k#xff0c;有2^k-1个节点的二叉树完全二叉树除了最底层节点可能没填满外#xff0c;其余每层节点数都达到最大值#xff0c;并且最下面一层的节点都集中在该层最左边的若干位置。二叉搜索树…二叉树的种类二叉树的主要形式满二叉树和完全二叉树。满二叉树深度为k有2^k-1个节点的二叉树完全二叉树除了最底层节点可能没填满外其余每层节点数都达到最大值并且最下面一层的节点都集中在该层最左边的若干位置。二叉搜索树二叉搜索树是一个有序树若它的左子树不空则左子树上所有结点的值均小于它的根结点的值若它的右子树不空则右子树上所有结点的值均大于它的根结点的值它的左、右子树也分别为二叉排序树平衡二叉搜索树AVL树它是一棵空树或它的左右两个子树的高度差的绝对值不超过1并且左右两个子树都是一棵平衡二叉树。C中map、set、multimapmultiset的底层实现都是平衡二叉搜索树所以map、set的增删操作时间时间复杂度是logn注意我这里没有说unordered_map、unordered_setunordered_map、unordered_map底层实现是哈希表。二叉树的存储方式二叉树可以链式存储也可以顺序存储。链式存储方式就是用指针顺序存储的方式就是用数组了解。顺序存储的元素在内存是连续分布的而链式存储则是通过指针把分布在各个地址的节点串联一起。二叉树的遍历方式深度优先遍历先往深处走遇到叶子节点再往回走。前、中、后序遍历广度优先遍历一层一层的遍历。层序遍历二叉树的定义链式存储的二叉树节点定义struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};二叉树的递归遍历递归三要素确定递归函数的参数和返回值确定哪些参数是递归的过程中需要处理的那么就在递归函数里加上这个参数 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。确定终止条件写完了递归算法, 运行的时候经常会遇到栈溢出的错误就是没写终止条件或者终止条件写的不对操作系统也是用一个栈的结构来保存每一层递归的信息如果递归没有终止操作系统的内存栈必然就会溢出。确定单层逻辑确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。二叉树的递归遍历递归的实现就是每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中然后递归返回的时候从栈顶弹出上一次递归的各项参数所以这就是递归为什么可以返回上一层位置的原因。前序遍历是中左右每次先处理的是中间节点那么先将根节点放入栈中然后将右孩子加入栈再加入左孩子。迭代法写中序遍历就需要借用指针的遍历来帮助访问节点栈则用来处理节点上的元素。先序遍历是中左右后续遍历是左右中那么我们只需要调整一下先序遍历的代码顺序就变成中右左的遍历顺序然后在反转result数组输出的结果顺序就是左右中了例题1、从上到下打印二叉树、从上到下打印二叉树II、从上到下打印二叉树III剑指12、树的子结构、翻转二叉树、对称二叉树剑指1--树的子结构关于二叉树的层序遍历广度优先算法用队列用size记录每层的个数每pop一个节点判断其左右孩子是否为空不为空就push进队列。1.二叉树的层序遍历 、二叉树的层序遍历II、二叉树的右视图判断当前层遍历的元素是否为最后一个元素如果是的话就添加到数组里2.二叉树的层平均值求均值的时候要做强制类型转换3.N叉树的层序遍历注意N叉树节点的定义节点的孩子是一个Node数组class Node {
public:int val;vectorNode* children;Node() {}Node(int _val) {val _val;}Node(int _val, vectorNode* _children) {val _val;children _children;}
};关于二叉树的高度、深度等问题二叉树节点的深度指从根节点到该节点的最长简单路径边的条数或者节点数取决于深度从0开始还是从1开始二叉树节点的高度指从该节点到叶子节点的最长简单路径二叉树的最小深度边的条数后者节点数取决于高度从0开始还是从1开始二叉树的最大深度、二叉树的最小深度关于完全二叉树与平衡二叉树问题完全二叉树的节点个数后序遍历在求完全二叉树的节点个数时可以利用其性质先一路向左一路向右找最大深度看看是否一致相等的话则这个节点往下为满二叉树可以用公式2的n次方-1。平衡二叉树后序遍历用返回-1的方式表达此时该节点已经不为平衡二叉树注意这里获取高度时如果为平衡二叉树返回值为该节点目前的高度。与二叉树的最大深度这个题目搭配可以很妙。关于二叉树的路径问题二叉树的所有路径所有路径肯定涉及回溯了用中左右前序遍历。终止条件判断是否为叶子节点中的处理要放在前面在处理左右时要防止空指针异常。注意这里的中处理时将节点push进数组的操作要在终止条件之前做因为最后一个节点也要放入数组中。
