7.3树与二叉树

树的基本概念

树的度

节点的度

树的层次

分支节点

根节点

内部节点

叶子节点

兄弟节点

二叉树

满二叉树

完全二叉树

非完全二叉树

完全二叉树的总节点数n不超过$n<2 ^ i -1$

完全二叉树的子节点树m不超过$m < 2^{i-1}$

对任何一颗二叉树，叶子节点数$n_0=n_1+1$(n1为度为2的结点数)

完全二叉树的节点值为k，

​ 其父节点值为k/2取整

​ 其左子节点值为2k，若2k>n，无左子节点

​ 右子节点值为2k+1，若2k+1>n，无右子节点

提示：i为树的层次

树的遍历

前序遍历

中序遍历

后序遍历

层次遍历

前、中、后指的是父节点的位置

根据遍历结果还原二叉树

注意：想要通过遍历结果还原二叉树必须要有中序遍历结果

树转二叉树

转换规则

树的孩子节点位于左子树

树的右兄弟节点位于右子树

根据权值求汉夫曼树（最优二叉树）

从最小权值依次构建

插入二叉树

插入节点值比父节点小，位于左子树；比父节点大，位于右子树

删除二叉树

• 若删除节点只存在一个子节点，删除待删除节点，子节点移到删除节点的位置

• 如删除节点存在两个子节点，删除待删除节点，在左子树中序遍历出节点值最大的节点并移到删除节点的位置

线索二叉树

平衡二叉树

任意节点的左右子数深度之差不超过1