网站建社石家庄,产品网站建设建议,甘肃省第九建设集团网站首页,定西市建设厅官方网站二叉树
性质
1, 我们把树中结点的第一个子结点作为这个结点左结点
2, 我们把一个结点右兄弟结点, 作为右结点
通过上述操作可以将普通的树转换为二叉树
二叉树中的节点最多有两个子节点#xff0c;左右子节点有严格划分#xff0c;次序不能颠倒
特点#xff1a;
二叉…二叉树
性质
1, 我们把树中结点的第一个子结点作为这个结点左结点
2, 我们把一个结点右兄弟结点, 作为右结点
通过上述操作可以将普通的树转换为二叉树
二叉树中的节点最多有两个子节点左右子节点有严格划分次序不能颠倒
特点
二叉树在第i层至多有2的(i-1)次方个节点
层次为k的二叉树至多有2的k次方 - 1个节点
对任何一颗二叉树T如果其叶子节点数为n0 , 度为2的节点数为n2则n0 n2 1
具有n个节点的完全二叉树树的高度为log2n (向下取整)。
如果对一颗有n个结点的完全二叉树的结点按层序从1开始编号则对任意一结点有 如果编号i为1则该结点是二叉树的根; 如果编号i 1则其双亲结点编号为 parent(i) i/2, 若 2i n 则该结点没有左孩子否则其左孩子的编号为 2i, 若 2i 1 n 则该结点没有右孩子否则其右孩子的编号为 2i 1。
二叉树的遍历
广度遍历:
深度遍历
对于一个树深度遍历右6种情况, 如果限定先左后右的话还剩3中 根 左 右 -- 先序/先根 遍历 左 根 右 -- 中序/中根 遍历 左 右 根 -- 后序/后根 遍历
运用的是递归的分治思想将每个节点的划分为左子树和右子树
二叉树的建树
前序和后序确定的是根节点的位置中序用来划分左右子树
所以只有前序中序或者中序后序才能建树
二叉搜索树
每一个节点的左子节点都比他小右子节点都比他大
自平衡的二叉搜索树
在二叉搜索树的基础上每一个节点都满足左右子树的高度相差不超过1
设计的原因是因为二叉树在频繁的添加和删除的过程中造成树变得稀疏于是可以通过旋转的方式来改进
红黑树
根节点可以任意变换颜色没有连续的红色黑高平衡
通过旋转来保证黑高平衡先左旋再右旋先右旋再左旋分情况
