1. 二叉树存储结构
二叉树中每一个节点使用孩子表示法结构创建
以A节点(根)为例:
A的左孩子(左子树) 等于 B节点对象的引用，A的右孩子(右子树) 等于 C节点对象的引用
class TreeNode {
// 左孩子
public TreeNode left;
// 右孩子
public TreeNode right;
public char val;
public TreeNode(char val) {
this.val = val;
}
}一个个节点通过引用进行连接 从而构建一颗二叉树
public class BinaryTree {
static class TreeNode {
public TreeNode left;
public TreeNode right;
public char val;
public TreeNode(char val) {
this.val = val;
}
}
public TreeNode createTree() {
// 手动连接
TreeNode A = new TreeNode('A');
TreeNode B = new TreeNode('B');
TreeNode C = new TreeNode('C');
TreeNode D = new TreeNode('D');
TreeNode E = new TreeNode('E');
TreeNode F = new TreeNode('F');
TreeNode G = new TreeNode('G');
TreeNode H = new TreeNode('H');
A.left = B;
A.right = C;
B.left = D;
B.right = E;
C.left = F;
C.right = G;
E.right = H;
return A;
}
public static void main(String[] args) {
BinaryTree binaryTree = new BinaryTree();
BinaryTree.TreeNode root = binaryTree.createTree();
}
}注意:
上述代码并不是创建二叉树的方式，真正创建二叉树方式后序重点介绍
2. 二叉树前中后序遍历
前中后序遍历概念
什么是前中后序遍历 ？
前中后序遍历是3种访问一颗树上节点的顺序
访问结点所做的操作依赖于具体的应用问题(比如：打印节点内容)
前序遍历: 首先访问树的根节点, 然后访问树的左子树，最后访问树的右子树
中序遍历: 左子树 ——》 根 ——》右子树
后序遍历: 左子树 ——》 右子树 ——》根
例子:
前序: B -> D -> null -> null -> E -> null -> H -> null -> null
中序: null -> D -> null -> B -> null -> E -> null -> H -> null
后序: null -> null -> D -> null -> null -> null -> H -> E -> B
二叉树遍历的4个练习 (重要)
1.某完全二叉树按层次输出（同一层从左到右）的序列为 ABCDEFGH 。该完全二叉树的前序序列为()
A: ABDHECFG B: ABCDEFGH C: HDBEAFCG D: HDEBFGCA
2. 二叉树的先序遍历和中序遍历如下：先序遍历：E F H I G J K;中序遍历：HFI E JKG. 画出这棵树
先序判断根, 中序判断左右子树
3.设一课二叉树的中序遍历序列：b a dce，后序遍历序列：b d e c a，画出这棵树
后序判断根, 中序判断左右子树
问题：给定一个前序和后序遍历 可以画出一颗二叉树吗 ?
答：不可以，因为前序和后序遍历只能确定根的位置，无法确定左右子树, 所以一定要有中序遍历判断左右子树
递归实现前中后序
// 前序遍历 (根左右) - 递归实现
public void preOrder(TreeNode root) {
if (root == null) {
System.out.print("null ");
return;
}
System.out.print(root.val + " ");
preOrder(root.left);
preOrder(root.right);
}
// 中序遍历 (左根右) - 递归实现
public void inOrder(TreeNode root) {
if (root == null) {
System.out.print("null ");
return;
}
inOrder(root.left);
System.out.print(root.val + " ");
inOrder(root.right);
}
// 后序遍历 (左右根) - 递归实现
public void postOrder(TreeNode root) {
if (root == null) {
System.out.print("null ");
return;
}
postOrder(root.left);
postOrder(root.right);
System.out.print(root.val + " ");
}