1、二叉树定义和特点
- 1.1、定义
- 二叉树(Binary Tree)是 **n**(n>=0)个结点的有限集合;
- 该集合或者为空集(空二叉树);
- 或者由一棵根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成
- 1.2、特点
- 每个节点最多有2棵子树(度最大为2)
- 左子树和右子树是有顺序的
- 即使某个节点只有一棵子树,也要区分它是左子树还是右子树
2、二叉树的遍历
从根节点出发,按照某种次序依次访问二叉树中所有节点,使得每个节点被访问一次且仅被访问一次
- 2.1、前序遍历:先访问根节点,然后前序遍历左子树,再前序遍历右子树

public void preOrderTraverse(Node<E> node) {
if (node == null) return;
System.out.println(node.element); // 打印
preOrderTraverse(node.left);
preOrderTraverse(node.right);
}
-
2.2、中序遍历:从根节点开始(⚠️并不先访问根节点),中序遍历根节点的左子树,然后访问根节点,最后中序遍历右子树。(⚠️二叉搜索树的中序遍历结果是升序或降序)
中序遍历:GDHBAEICF
public void inOrderTraver(Node<E> node) {
if (node == null) return;
inOrderTraver(node.left);
System.out.println(node.element);
inOrderTraver(node.right);
}
- 2.3、后序遍历:从左到右先叶子后结点的方式遍历访问左右子树,最后是访问根节点

public void postOrderTraverse(Node<E> node) {
if (node == null) return;
postOrderTraverse(node.left);
postOrderTraverse(node.right);
System.out.println(node.element);
}
-
2.4、层序遍历:从树的第一层开始访问(也就是根节点),从上而下逐层遍历,在同一层中,按从左到右的顺序对结点逐个访问
层序遍历:ABCDEFGHI
public void levelOrderTraverse(){
if (root == null) return;
// 使用队列来实现:先进先出 ✨✨✨✨✨
Queue<Node<E>> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
Node<E> node = queue.poll();
System.out.println(node.element);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
- 2.4、根据遍历结果重构二叉树
以下结果可以保证重构出唯一一棵二叉树✨✨✨
- 前序遍历 + 中序遍历
- 后序遍历 + 中序遍历
例:已知一棵二叉树的前序遍历序列为:ABCDEF,中序遍历序列为:CBAEDF,请问这棵二叉树的后续遍历结果是多少?
思路:
- 根据:前序遍历 + 中序遍历 还原二叉树,再查后续遍历
- 前序遍历,第一个结点一定是根结点✨✨✨
解题
- 前序遍历:ABCDEF => 根节点为A
- 中序遍历:CBAEDF => 左子树(CB)、右子树(EDF), 即图2.4.1
- 前序,先 B 后 C => 所以 C 是 B 的孩子(未确定左右)
- 中序,先 C 后 B => C 是 B 的左孩子, 即图2.4.2
同理,根据以上顺序,得出右子树
⚠️
- 如果不是特别熟练的话,一定要从还原出的树中走一遍前、中、后,与题目是否相对
- 前序遍历 + 后序遍历 无法确定一个二叉树,因为不知道根节点,可能存在多种情况



3、特殊的二叉树
- 3.1、真二叉树(Proper Binary Tree)
所有节点的度要么为0,要么为2

- 3.2、满二叉树(Full Binary Tree)
- 所有节点的度要么为0,要么为2,且所有的叶子节点都在最后一层
- 在同样高度的二叉树中,满二叉树的叶子节点数量最多,总节点数量最多
- 满二叉树一定是真二叉树,真二叉树不一定是满二叉树 ✨

- 3.3、完全二叉树(Complete Binary Tree)
叶子节点只会出现"最后2层",且"最后1层"的叶子节点都靠"左对齐"
- 完全二叉树从根节点至倒数第2层是一棵满二叉树
- 满二叉树一定是完全二叉树,完全二叉树不一定是满二叉树

4、前驱节点、后继节点
- 4.1、前驱节点:中序遍历时的前一个节点
⚠️如果是二叉搜索树,前驱节点就是前一个比它小的节点
情况一:node.left != null
predecessor = node.left.right.right.right...
终止条件:right = null
情况二:node.left == null
predecessor = node.parent.parent.parent.parent...
终止条件:node 在 parent的右子树中
情况三:node.left == null && node.parent == null
没有前驱
protected Node<E> predecessor(Node<E> node) {
if (node == null) return node;
// 前驱节点在左子树当中(left.right.right.right...)
Node<E> p = node.left;
if (p.left != null) {
while(p.right != null) {
p = p.right;
}
return p;
}
// 从父节点,祖父节点寻找前驱节点
while(node.parent != null && node == node.parent.left){
node = node.parent;
}
return node.parent;
}
- 4.2、后继节点:中序遍历时的后一个节点
⚠️- 如果是二叉搜索树,前驱节点就是后一个比它大的节点
情况一:node.right != null
successor = node.right.left.left.left...
终止条件:left 为 null
情况二:node.right == null && node.parent != null
successor = node.parent.parent.parent.parent...
终止条件:node在parent左子树中
情况三:node.right == null && node.parent == null
没有后继节点
protected Node<E> successor(Node<E> node) {
if (node == null) return node;
Node<E> p = node.right;
if (p.right != null) {
while(p.left != null) {
p = p.left;
}
return p;
}
while(node.parent != null && node == node.parent.right){
node = node.parent;
}
return node.parent;
}
5、其他重要性质
- 二叉树的第i层,最多有2^(i-1)个节点(i>=1)✨
- 在高度为h的二叉树上最多有2^h - 1个节点(h>=1)✨
- 对于任何一棵二叉树,如果叶子节点的个数为n0,度为2的节点个数为n2,则有:n0 = n2 + 1;✨✨✨✨
验证:
假设度为1的节点个数为n1,那么二叉树的节点总数 n=n0+n1+n2;✨✨
二叉树的边树 T = n1 + 2*n2 = n-1 = n0 + n1 + n2 - 1;
消除等号左右共项:n0 = n2 + 1;
待补充:TODO()
网友评论