二叉树基础理论

二叉树基础理论

要点

• 二叉树种类
• 二叉树存储方式
• 二叉树遍历方式
• 二叉树定义

1. 二叉树种类

大体有如下四类：

• 满二叉树：整棵树看起来像一个完美的金字塔，没有缺失的枝丫

• 完全二叉树：这棵树除了最下面一层，上面几层都长得满满当当。而最下面一层，叶子从左到右依次排列，中间没有空缺，但右边可能缺几个。

• 二叉搜索树：左边子树的所有值都比它小，右边子树的所有值都比它大

• 平衡二叉搜索树：在二叉搜索树的基础上，它要求每个节点的左右子树高度差不超过1

2. 二叉树存储方式

顺序存储

把树上的节点按照“从上到下、从左到右”的顺序一个个放进格子里。

一般就是规整的 0 1 2 3 4 5 6

左孩子在下标 2*i + 1 的格子里。 右孩子在下标 2*i + 2 的格子里。 父节点在下标 (i-1) / 2 的格子里（计算机整数除法会自动取整）。

链式存储

链式存储中，二叉树本质就是链表。链表的next一分为二，变为左孩子和右孩子节点。

publicclassTreeNode{intval;TreeNodeleft;TreeNoderight;TreeNode(){}TreeNode(intval){this.val=val;}TreeNode(intval,TreeNodeleft,TreeNoderight){this.val=val;this.left=left;this.right=right;}}

3. 二叉树遍历方式

假设树长这样：

A / \ B C / \ \ D E F

前序遍历

• 顺序：先看当前节点（根），然后去左边，最后去右边。（中左右）

• 遍历结果：A → B → D → E → C → F

• 特点：深度优先，先处理自己，再处理孩子。常用于复制一棵树（先复制根，再复制左右）。

中序遍历

• 顺序：先去左边，再看当前节点，最后去右边。（左中右）

• 遍历结果：D → B → E → A → C → F

• 特点：深度优先，对于二叉搜索树，中序遍历得到升序序列。

后序遍历

• 顺序：先去左边，再去右边，最后看当前节点。（左右中）

• 遍历结果：D → E → B → F → C → A

• 特点：深度优先，常用于删除树（先删孩子，再删自己），或计算文件夹大小（先算子文件夹，再累加自己）。

层序遍历

• 顺序：先访问第一层，再第二层，同一层从左到右。

• 遍历结果：A → B → C → D → E → F

• 特点：广度优先，就像扫描仪一样一层层扫过去。常用于寻找最短路径、判断树是否对称。