一、树的定义
树（Tree）是 n （n>=0）个结点的有限集。n == 0 时成为空树，任意一棵非空树中，有且仅有一个特定的称为跟（Root）的结点。
-
树的度：树内各结点的度的最大值。
-
孩子：结点的子树的根
-
双亲： 子树的根的上一层结点
-
深度：树中结点的最大层次
树的存储结构：
-
双亲表示法
-
孩子表示法
-
孩子兄弟表示法
二、二叉树
二叉树（Binary Tree）是 n （n>=0）个结点的有限集。n == 0 时成为空二叉树，n >= 0 时由一个人根节点和两棵互不相交的、分别称为根节点的左子树和右子树组成。
- 特殊的二叉树：斜树、满二叉树、完全二叉树
二叉树的性质：
-
在二叉树的第 i 层上至多有 2^(i-1) 个结点
-
深度为 k 的二叉树最多有 2^k -1 个结点
-
对于任何一棵二叉树，如果其叶子结点的数量为 n0, 度为 2 的结点数为 n2,那么 n0 = n2 +1
1. 二叉树的存储结构
二叉树每个结点最多有两个孩子，所以设计成一个数据域和两个指针域的结点，这样的链表称为二叉链表。
2. 二叉树的遍历方法
- 前序遍历
规则：若二叉树为空，则返回；否则先访问根结点，然后前序遍历左子树再前序遍历右子树。
前序遍历算法：采用递归实现
/**
* 前序遍历算法,递归
* @param tree
*/
public static void preOrderTraverse(BiTreeNode tree){
if(tree == null){
System.out.println("这是空的二叉树");
return;
}
System.out.println("结点数据："+ tree.data);
//前序递归遍历左子树
preOrderTraverse(tree.lchild);
//前序递归遍历右子树
preOrderTraverse(tree.rchild);
}
- 中序遍历
规则：若二叉树为空，则返回；否则先从根结点开始（注意并不是先访问开头的根结点，而是从左子树的最左叶子结点开始访问）。中序遍历根结点的左子树，然后访问根结点，最后中序遍历右子树。
中序遍历算法：采用递归实现
/**
* 中序遍历算法,递归
* @param tree
*/
public static void inOrderTraverse(BiTreeNode tree){
if(tree == null){
System.out.println("这是空的二叉树");
return;
}
System.out.println("中序遍历");
//中序递归遍历左子树
inOrderTraverse(tree.lchild);
System.out.println("结点数据："+ tree.data);
//中序递归遍历右子树
inOrderTraverse(tree.rchild);
}
- 后序遍历
规则：若二叉树为空，则返回；否则从左到右先叶子后结点的方式遍历左右子树，最后访问根结点。
后序遍历算法：采用递归实现
/**
* 后序遍历算法,递归
* @param tree
*/
public static void postOrderTraverse(BiTreeNode tree){
if(tree == null){
System.out.println("这是空的二叉树");
return;
}
System.out.println("后序遍历");
//后序递归遍历左子树
postOrderTraverse(tree.lchild);
//后序递归遍历右子树
postOrderTraverse(tree.rchild);
System.out.println("结点数据："+ tree.data);
}
测试代码：
/**
* 二叉树节点
* @author innovator
*
*/
public class BiTreeNode {
public String data;
public BiTreeNode lchild;
public BiTreeNode rchild;
public BiTreeNode(String d){
this.data = d;
}
}
public static void main(String[] args){
BiTreeNode A = new BiTreeNode("A");
BiTreeNode B = new BiTreeNode("B");
BiTreeNode C = new BiTreeNode("C");
BiTreeNode D = new BiTreeNode("D");
BiTreeNode E = new BiTreeNode("E");
BiTreeNode F = new BiTreeNode("F");
BiTreeNode G = new BiTreeNode("G");
BiTreeNode H = new BiTreeNode("H");
BiTreeNode I = new BiTreeNode("I");
BiTreeNode J = new BiTreeNode("J");
BiTreeNode K = new BiTreeNode("K");
A.lchild = B;
A.rchild = C;
B.lchild = D;
B.rchild = E;
C.lchild = F;
C.rchild = G;
D.lchild = H;
H.rchild = K;
F.lchild = I;
G.rchild = J;
// preOrderTraverse(A);
// inOrderTraverse(A);
postOrderTraverse(A);
}
三、二叉树面试题
- 剑指 Offer 面试题 6（Java 版）：重建二叉树
题目：输入某二叉树的前序遍历和中序遍历的结果，请重新构造出该二叉树。假设输入的前序遍历和中序遍历的结果中不包含重复的数字。例如输入的前序遍历序列为｛1，2，4，7，3，5，6，8｝和中序遍历为{4，7，2，1，5，3，8，6}，则重建出二叉树并输出它的头结点。
思路：在二叉树的前序遍历序列中，第一个数字总是树的根节点的值。但在中序遍历中，根节点的值在序列的中间，左子树的结点的值位于根节点的值的左边，而右子树的结点的值位于根节点的右边。因此只要扫描中序遍历序列，就能找到根节点的值，从而区分出左子树和右子树。然后递归构建左子树和右子树。
show my code
/**
* 二叉树结点
* @author innovator
*
*/
public class BinaryTreeNode {
public int value;
public BinaryTreeNode leftNode;
public BinaryTreeNode rightNode;
public BinaryTreeNode(int value){
this.value = value ;
}
}
/**
* 输入前序遍历和中序遍历重建二叉树
* @author innovator
*
*/
public class ConstructBinaryTree {
/**
* 重建二叉树
* @param preOrder 前序遍历序列
* @param inOrder 中序遍历序列
* @param length 序列长度
* @return
* @throws InvalidPutException
*/
public static BinaryTreeNode constructMyTree(int[] preOrder,int[] inOrder,int length) throws InvalidPutException{
if(preOrder == null || inOrder == null || length <= 0){
System.out.println("输入不合法");
return null;
}
try {
return constructCore(preOrder, 0, preOrder.length-1, inOrder, 0, inOrder.length-1);
} catch (InvalidPutException e) {
e.printStackTrace();
return null;
}
}
/**
* 重建二叉树递归算法
* @param preOrder 前序遍历序列
* @param startPreIndex 前序序列开始位置
* @param endPreIndex 前序序列结束位置
* @param inOrder 中序遍历序列
* @param startInIndex 中序序列开始位置
* @param endInIndex 中序序列结束位置
* @return 根结点
* @throws InvalidPutException
*/
public static BinaryTreeNode constructCore(int[] preOrder,int startPreIndex,int endPreIndex,
int[] inOrder,int startInIndex,int endInIndex) throws InvalidPutException{
//前序遍历序列的第一个数字就是根结点 root
int rootValue = preOrder[startPreIndex];
System.out.println("根结点的值："+rootValue);
BinaryTreeNode root = new BinaryTreeNode(rootValue);
//只有一个元素
if(startInIndex == endInIndex){
if (startInIndex == endInIndex
&& preOrder[startPreIndex] == inOrder[startInIndex]) {
System.out.println("only one element");
return root;
} else {
throw new InvalidPutException();
}
}
//找到中序遍历的root的位置，进而分成左子树和右子树
int inOrderRootIndex = startInIndex;
while (inOrderRootIndex <= endInIndex && inOrder[inOrderRootIndex] != rootValue) {
++ inOrderRootIndex;
}
//遍历完了中序序列也没找到 root 结点
if(inOrderRootIndex == inOrder.length && inOrder[inOrderRootIndex -1] != rootValue){
throw new InvalidPutException();
}
//左子树长度
int leftLength = inOrderRootIndex - startInIndex;
//前序遍历序列中左子树的末端位置
int leftPreOrderEndIndex = startPreIndex + leftLength;
//递归构造左子树
if(leftLength >0){
System.out.println("左子树长度："+leftLength);
root.leftNode = constructCore(preOrder, startPreIndex+1, leftPreOrderEndIndex, inOrder, startInIndex, inOrderRootIndex-1);
}
//递归构造右子树
if(leftLength < endPreIndex - startPreIndex){
//右子树有元素
root.rightNode = constructCore(preOrder, leftPreOrderEndIndex +1, endPreIndex, inOrder, inOrderRootIndex+1, endInIndex);
}
return root;
}
static class InvalidPutException extends Exception {
private static final long serialVersionUID = 1L;
public InvalidPutException(){
System.out.println("抛异常啦，输入不合法");
}
}
/**
* 后序遍历打印
* @param root
*/
public static void printPostOrder(BinaryTreeNode root) {
if (root == null) {
System.out.print("输入不合法");
return;
}
if (root.leftNode != null) {
printPostOrder(root.leftNode);
}
if (root.rightNode != null) {
printPostOrder(root.rightNode);
}
//打印结点信息
System.out.print(root.value + " ");
}
/**
* 前序遍历打印
* @param root
*/
public static void printPreOrder(BinaryTreeNode root) {
if (root == null) {
return;
} else {
System.out.print(root.value + " ");
}
if (root.leftNode != null) {
printPreOrder(root.leftNode);
}
if (root.rightNode != null) {
printPreOrder(root.rightNode);
}
}
public static void main(String[] args) throws Exception{
int[] preOrder={1,2,4,7,3,5,6,8};
int[] inOrder={4,7,2,1,5,3,8,6};
printPostOrder(constructMyTree(preOrder, inOrder, preOrder.length));
}
}
后序遍历次序
网友评论