二叉树的定义
- 二叉树是 n （n >= 0）个节点的有限集合，该集合或者为空集（称为空二叉树）或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成
图1
- 折半规律很适合作为二叉树建模
图2
-
二叉树特点
- 每个节点最多有两棵子树
- 左子树和右子树是有顺序的，次序不能任意颠倒
- 即使树中某节点只有一棵子树也要区分它是左子树还是右子树
-
特殊二叉树
- 斜树：所有的节点都只有左子树的二叉树叫做左斜树，反之右斜树
- 满二叉树：所有分支节点都存在左子树和右子树，并且所有叶子都在同一层上
满二叉树- 完全二叉树：叶子节点只能出现在最下两层，最下层的叶子一定集中在左部连续位置，倒数二层，若有叶子节点，一定都在右部连续位置，如果节点度为 1，则该节点只有左孩子，既不存在右子树情况，同样节点数的二叉树，完全二叉树的深度最小
完全二叉树
二叉树的性质
二叉树性质1
- 在二叉树的第 i 层上至多有 2的i-1次方个节点 (i>=1)
二叉树性质2
- 深度为 k 的二叉树至多有 2的k次方-1个节点 （k>=1）
二叉树性质3
- 如果端节点数为 n0，度为 2 的节点数为 n2，则 n0=n2+1
- 终端节点其实就是叶子节点数，而一棵二叉树除了叶子节点外，剩下的就是度为 1 或 2 的节点数了，我们设 n1 为度是 1 的节点数，则树节点总数是 n=n0+n1+n2
- 图5 度为2的节点数 n2 = 4，则叶子节点数 n0 = 4+1，树节点总数 n=4+1+5
图5
二叉树性质4
- 具有 n 个节点的完全二叉树的深度为 [log2n]+1 ([x] 表示不大于 x 的最大整数)
- 如 图1 有 10 个节点，则深度 4 = log 以2为底10的对数 + 1 = 3 + 1
二叉树性质5
- 对于一棵有 n 个节点的完全二叉树（其深度为 [log2n]+1）的节点按层序编号（从第 1 层到第 [log2n]+1 层，每层从左到右），对任一节点 i 有：
- 如果 i =1，则节点 i 是二叉树的根，则无双亲，如果 i > 1，则其双亲是节点 [i/2]（下图节点7，它的双亲就是 [7/2] = 3）
- 如果 2i > n，则节点 i 无左子树（节点 i 为叶子节点），否则其左子树是节点 2i，（下图节点6，因为 2*6=12 超过了节点总数 10，所以它无左子树，而节点5 因为等于10，所以它的左子树节点为 10）
- 如果 2i + 1 > n，则节点 i 无右子树，否则其右子树是节点 2i+1，（下图节点5，因为 2*5+1=11 大于节点总数 10，所以它无右子树，因为节点2 小于 10，所以它的右子树节点为 7）
图6
二叉树的存储结构
二叉树顺序存储
- 二叉树的顺序存储结构就是用一维数组存储二叉树中的节点，并且节点的存储位置，也就是数组的下标要能体现节点之间的逻辑关系，比如双亲与子节点、兄弟节点的关系
图7
- 对于一般的二叉树，层序编号不能反应逻辑关系，但是可以将其按完全二叉树编号，把不存在的节点设置为 "^"
图8
- 考虑一种极端情况，一棵深度为 k 的右斜树，它只有 k 个节点，却要分配 2的k次方-1 个存储单元空间，这显然是对存储空间的浪费，所以顺序存储结构一般只用于完全二叉树
图9
二叉链表
- 二叉树每个节点最多有两个子节点，所以为它设计一个数据域与两个指针域
| lchild | data | rchild |
|---|
遍历二叉树
- 二叉树的遍历是指从根节点触发，按照某种次序依次访问二叉树中所有的节点，使得每个节点都被访问一次且仅被访问一次
1. 前序遍历
- 先访问根节点，然后前序遍历左子树，再前序遍历右子树，遍历顺序为：ABDGHCEIF
2. 中序遍历
- 中序遍历根节点的左子树，然后访问根节点，最后中序遍历右子树，遍历顺序为：GDHBAEICF
3. 后续遍历
- 从左到右先叶子后节点的方式遍历左右子树，最后访问根节点，遍历顺序为：GHDBIEFCA
4. 层序遍历
- 从树的根节点开始访问，从上而下逐层遍历，在同一层中，从左到右顺序对节点逐个访问，遍历顺序为：ABCDEFGHI
简单的二叉树代码例子
import java.util.ArrayList;
import java.util.List;
public class BinTree {
private BinTree root; // 根节点
private BinTree lChild; // 左子树
private BinTree rChild; // 右子树
private Object data; // 数据域
private List<BinTree> datas; // 存储的所有节点
public BinTree(BinTree lChild, BinTree rChild, Object data) {
this.lChild = lChild;
this.rChild = rChild;
this.data = data;
}
public BinTree(Object data) {
this.data = data;
}
public BinTree() {
}
public void createTree(Object[] objs) {
datas = new ArrayList<>();
for (Object object : objs) {
datas.add(new BinTree(object));
}
root = datas.get(0);// 将第一个节点作为根节点
for (int i = 0; i < datas.size() / 2; i++) {
datas.get(i).lChild = datas.get(i * 2 + 1); // 设置左子树
if ((i * 2 + 2) < datas.size()) { // 避免越界
datas.get(i).rChild = datas.get(i * 2 + 2); // 设置右子树
}
}
}
// 前序遍历：从根节点开始，先遍历左子树，再遍历右子树
public void preorder(BinTree root) {
if (root != null) {
System.out.println(root.getData());
preorder(root.lChild);
preorder(root.rChild);
}
}
// 中序遍历：从根节点先遍历左子树，在根节点，最后右子树
public void inorder(BinTree root) {
if (root != null) {
inorder(root.lChild);
System.out.println(root.getData());
inorder(root.rChild);
}
}
// 后续遍历：从左到右最后再根节点
public void afterorder(BinTree root){
if(root != null){
afterorder(root.lChild);
afterorder(root.rChild);
System.out.println(root.getData());
}
}
public Object getData() {
return data;
}
public BinTree getRoot() {
return root;
}
public static void main(String[] args) {
BinTree binTree = new BinTree();
Object[] objects = new Object[]{1, 2, 3, 4, 5, 6, 7, 8,9,10};
binTree.createTree(objects);
binTree.afterorder(binTree.getRoot());
}
}
