正文
数据结构——Java实现二叉树
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
相关概念
存储结构：
- 顺序存储结构：二叉树的顺序存储结构适用于完全二叉树，对完全二叉树进行顺序编号，通过二叉树的性质五（第1个结点为根结点，第i个结点的左孩子为第2i个结点，右孩子为第2i+1个结点）。
- 链式存储结构：一般情况下，采用链式存储结构来存储二叉树。每个结点有3个域：data、left、right。
遍历：
- 先根次序：根->左->右。
- 中根次序：左->根->右。
- 后根次序：左->右->根。
遍历算法：
- 递归
- 非递归：通过设立一个栈。
声明二叉树结点类
/**
* Copyright 2016 Zhengbin's Studio.
* All right reserved.
* 2016年7月16日 上午8:19:15
*/
package Two;
/**
* @author zhengbinMac
*
*/
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
/**
* 先根遍历
* @param p
*/
public void preorder(TreeNode p) {
if(p != null) {
System.out.print(p.val + " ");
preorder(p.left);
preorder(p.right);
}
}
/**
* 中根遍历
* @param p
*/
public void inorder(TreeNode p) {
if(p != null) {
preorder(p.left);
System.out.print(p.val + " ");
preorder(p.right);
}
}
/**
* 后根遍历
* @param p
*/
public void postorder(TreeNode p) {
if(p != null) {
preorder(p.left);
preorder(p.right);
System.out.print(p.val + " ");
}
}
}
声明二叉树类 和 由先根遍历与中根遍历构造二叉树
/**
* Copyright 2016 Zhengbin's Studio.
* All right reserved.
* 2016年7月16日 上午8:19:15
*/
package Two; /**
* @author zhengbinMac
*
*/
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
/**
* 先根遍历
* @param p
*/
public void preorder(TreeNode p) {
if(p != null) {
System.out.print(p.val + " ");
preorder(p.left);
preorder(p.right);
}
}
/**
* 中根遍历
* @param p
*/
public void inorder(TreeNode p) {
if(p != null) {
preorder(p.left);
System.out.print(p.val + " ");
preorder(p.right);
}
}
/**
* 后根遍历
* @param p
*/
public void postorder(TreeNode p) {
if(p != null) {
preorder(p.left);
preorder(p.right);
System.out.print(p.val + " ");
}
}
}
建立一颗二叉树必须明确以下两点：
- 结点与双亲结点及孩子结点间的层次关系。
- 兄弟结点间的左右子树的顺序关系。
先根次序或后根次序反映双亲与孩子结点的层次关系，中根次序反映兄弟结点间的左右次序。所以，已知先根和中根两种遍历序列，或中根和后根两种遍历序列才能够唯一确定一颗二叉树。而已知先根和后根两种遍历序列仍无法唯一确定一颗二叉树。
/**
* Copyright 2016 Zhengbin's Studio.
* All right reserved.
* 2016年7月16日 上午9:30:01
*/
package Two; import java.util.Arrays; /**
* @author zhengbinMac
*
*/
public class Tree {
protected TreeNode root;
public Tree() {
root = null;
}
public Tree(int[] pre, int[] in) {
// root = reConstructBinaryTree(pre, in);
root = reConstructBinaryTree1(pre, in);
}
/**
* 先根次序
*/
public void preorderTraversal() {
System.out.println("先根次序遍历：");
if(root != null) {
root.preorder(root);
}
}
/**
* 中根次序
*/
public void inorderTraversal() {
System.out.println("中根次序遍历：");
if(root != null) {
root.inorder(root);
}
}
/**
* 后根次序
*/
public void postorderTraversal() {
System.out.println("后根次序遍历：");
if(root != null) {
root.postorder(root);
}
}
/**
* 通过先根遍历与中根遍历构造二叉树（1）
*/
public TreeNode reConstructBinaryTree1(int[] pre, int[] in) {
if(pre.length == 0 || in.length == 0) {
return null;
}
TreeNode p = new TreeNode(pre[0]);
for (int i = 0; i < in.length; i++) {
if(pre[0] == in[i]) {
p.left = reConstructBinaryTree1(Arrays.copyOfRange(pre, 1, i+1), Arrays.copyOfRange(in, 0, i));
p.right = reConstructBinaryTree1(Arrays.copyOfRange(pre, i+1, pre.length), Arrays.copyOfRange(in, i+1, in.length));
}
}
return p;
}
/**
* 通过先根遍历与中根遍历构造二叉树（2）
*/
public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
if(pre == null || in == null) {
return null;
}
TreeNode p = null;
int first;
int n = pre.length;
int k = 0;
if(n > 0) {
// 取第一个为根
first = pre[0];
p = new TreeNode(first);
// 确定根结点在中根序列中的位置
for (int i = 0; i < in.length; i++) {
if(in[i] == first) {
k = i;
break;
}
}
// 左子树
int[] presubLeft = new int[k];
int[] insubLeft = new int[k];
// 先根
for (int i = 1, j = 0; i <= k; i++, j++) {
presubLeft[j] = pre[i];
}
// 中根
for (int i = 0, j = 0; i <= k-1; i++, j ++) {
insubLeft[j] = in[i];
}
p.left = reConstructBinaryTree(presubLeft, insubLeft);
// 右子树
int[] presubRight = new int[n-1-k];
int[] insubRight = new int[n-1-k];
// 先根
for (int i = k+1, j = 0; i <= n-1; i++,j++) {
presubRight[j] = pre[i];
}
// 中根
for (int i = k+1, j = 0; i <= n-1; i++,j++) {
insubRight[j] = in[i];
}
p.right = reConstructBinaryTree(presubRight, insubRight);
}
return p;
}
}
测试类
/**
* Copyright 2016 Zhengbin's Studio.
* All right reserved.
* 2016年7月16日 上午9:27:40
*/
package Two;
/**
* @author zhengbinMac
*
*/
public class Test {
public static void main(String[] args) {
int[] pre = {1,2,4,3,5,6};
int[] in = {4,2,1,5,3,6};
Tree t = new Tree(pre, in);
t.inorderTraversal();
System.out.println();
t.postorderTraversal();
System.out.println();
t.preorderTraversal();
}
}
在线编程：
/**
* Copyright 2016 Zhengbin's Studio.
* All right reserved.
* 2016年7月16日 上午9:27:40
*/
package Two; /**
* @author zhengbinMac
*
*/
public class Test { public static void main(String[] args) {
int[] pre = {1,2,4,3,5,6};
int[] in = {4,2,1,5,3,6};
Tree t = new Tree(pre, in);
t.inorderTraversal();
System.out.println();
t.postorderTraversal();
System.out.println();
t.preorderTraversal();
}
}
牛客网——《剑指Offer》-重建二叉树
