Java中二叉树数据结构的实现示例

来看一个具体的习题实践：

题目
根据二叉树前序遍历序列例如：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;
     }
   }

/**
    * 根据前序序列递归构建二叉树
    *
    * @return
    */
   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;
   }

/**
    * 前序遍历
    *
    * @param root
    */
   public static void preTraverse(TreeNode root) {
     if (root != null) {
       System.out.print(root.data + " ");
       preTraverse(root.lchild);
       preTraverse(root.rchild);
     }
   }

/**
    * 中序遍历
    *
    * @param root
    */
   public static void inTraverse(TreeNode root) {
     if (root != null) {
       inTraverse(root.lchild);
       System.out.print(root.data + " ");
       inTraverse(root.rchild);
     }
   }

/**
    * 后序遍历
    *
    * @param root
    */
   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));
}
}