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