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));
 }
}