二叉树基础知识

¶1.二叉树的性质

¶性质：

左孩子、右孩子、左子树、右子树；
二叉树第$i$层(i>=1)最多$2^{i-1}$个节点；
一个$n$层满二叉树，共$2^n-1$个节点；
完全二叉树：只在最后一层的最后有缺失编号的满二叉树；
根到节点$u$的距离为节点$u$的深度；节点$u$到到它的叶子节点的距离为节点u的高度；根的高度最大，称为树的高。

¶二叉树的优势：

(1)访问效率高。一棵有$N$个节点的平衡二叉树，从根到叶子节点只需$log_2N$步；但不平衡的二叉树，极端情况下会退化成“链”，访问效率会降低。维护二叉树的平衡是高级数据结构的主要任务之一。
(2)很适合整体到局部、局部到整体的操作。如求区间最值、区间和、区间翻转、区间合并、区间分裂等。
(3)基于二叉树的算法容易设计与实现。如$DFS、BFS$。

¶2.二叉树的存储结构

¶(1)动态二叉树。

每次$new$一个节点，使用完$delete$。不浪费空间，但需要管理，容易出错。

¶(2)静态数组存储二叉树。

编码简单，速度快。
用数组实现完全二叉树，左右子节点都不用定义：
总节点个数为$k$的完全二叉树，编号$i>1$的节点，父节点$i/2$;
若$2i>k$，则节点$i$没有子节点，若$2i+1>k$,则节点i没有右子节点；
如果节点$i$有子节点，那么左子节点是$2i$，右子节点是$2i+1$。

¶(3)多叉树转化为二叉树

¶3.二叉树的遍历

¶1.$BFS$ 按层遍历

如图，按$E-BG-ADFI-CH$顺序搜索。

¶2.$DFS$

¶(1)先序遍历。父-左-右

如图，按$EBADCGFIH$顺序遍历。

¶(2)中序遍历。左-父-右

如图，按$ABCDEFGHI$顺序遍历。
二叉搜索树中排序是中序遍历，特征：
若已知根节点，则根节点左边的数都在左子树上，右边的数都在右子树上，对其子树也是如此。

¶(3)后序遍历。左-右-父

如图，按$ACDBFHIGE$顺序遍历。

¶已知中序遍历和另一种遍历顺序，则可把这棵树构造出来：由先序遍历或后序遍历知根节点，而中序遍历中根节点左端的为左子树，右端的右子树，再由先序遍历或后序遍历知子根节点，递归地构造子树。