來看一個具體的習題實踐:
題目根據二叉樹前序周遊序列例如:7,-7,8,#,#,-3,6,#,9,#,#,#,-5,#,#,建構二叉樹,并且用前序、中序、後序進行周遊
代碼
import java.util.Scanner;
public class BinaryTree {
public static String[] str;
public static int count;
static class TreeNode {
public String data;
TreeNode lchild;
TreeNode rchild;
public TreeNode(String x) {
this.data = x;
}
}
public static TreeNode createBtree() {
TreeNode root = null;
if (count >= str.length || str[count++].equals("#")) {
root = null;
} else {
root = new TreeNode(str[count - 1]);
root.lchild = createBtree();
root.rchild = createBtree();
}
return root;
}
public static void preTraverse(TreeNode root) {
if (root != null) {
System.out.print(root.data + " ");
preTraverse(root.lchild);
preTraverse(root.rchild);
}
}
public static void inTraverse(TreeNode root) {
if (root != null) {
inTraverse(root.lchild);
System.out.print(root.data + " ");
inTraverse(root.rchild);
}
}
public static void postTraverse(TreeNode root) {
if (root != null) {
postTraverse(root.lchild);
postTraverse(root.rchild);
System.out.print(root.data + " ");
}
}
public static void main(String args[]) {
Scanner cin = new Scanner(System.in);
while (cin.hasNext()) {
String s = cin.nextLine();
str = s.split(",");
count = 0;
TreeNode root = createBtree();
// 前序周遊
preTraverse(root);
System.out.println();
// 中序周遊
inTraverse(root);
System.out.println();
// 後序周遊
postTraverse(root);
System.out.println();
}
}
}
二叉樹的深度
下面是是實作二叉樹的遞歸算法的實作,其思想就是,若為空,則其深度為0,否則,其深度等于左子樹和右子樹的深度的最大值加1:
class Node{
String name;
Node left;
Node right;
public Node(String name) {
this.name = name;
}
@Override
public String toString() {
return name;
}
}
//定義二叉樹
class BinaryTree{
Node root;
public BinaryTree(){
root = null;
}
//為了友善起見,我就直接寫個初始化的二叉樹,詳細的可以見以前的日志
public void initTree(){
Node node1 = new Node("a");
Node node2 = new Node("b");
Node node3 = new Node("c");
Node node4 = new Node("d");
Node node5 = new Node("e");
root = node1;
node1.left = node2;
node2.right = node3;
node1.right = node4;
node3.left = node5;
}
//求二叉樹的深度
int length(Node root){
int depth1;
int depth2;
if(root == null) return 0;
//左子樹的深度
depth1 = length(root.right);
//右子樹的深度
depth2 = length(root.left);
if(depth1>depth2)
return depth1+1;
else
return depth2+1;
}
}
public class TestMatch{
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
tree.initTree();
System.out.println(tree.length(tree.root));
}
}