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

所属分类：软件编程 / java 阅读数： 65

收藏 0赞 0分享

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

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

更多精彩内容其他人还在看