快捷導(dǎo)航

Java中二叉樹(shù)數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)示例

更新時(shí)間：2015年08月06日 11:57:20 作者：zinss26914

這篇文章主要介紹了Java中二叉樹(shù)數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)示例,包括前中后序遍歷和求二叉樹(shù)深度的方法,需要的朋友可以參考下

來(lái)看一個(gè)具體的習(xí)題實(shí)踐：

題目
根據(jù)二叉樹(shù)前序遍歷序列例如：7,-7,8,#,#,-3,6,#,9,#,#,#,-5,#,#，構(gòu)建二叉樹(shù)，并且用前序、中序、后序進(jìn)行遍歷

代碼

 import java.util.Scanner; 
   
  public class BinaryTree { 
    public static String[] str; 
    public static int count; 
   
    /** 
     * 靜態(tài)內(nèi)部類(lèi)，定義二叉樹(shù)節(jié)點(diǎn) 
     */ 
    static class TreeNode { 
      public String data; 
      TreeNode lchild; 
      TreeNode rchild; 
   
      public TreeNode(String x) { 
        this.data = x; 
      } 
    } 
   
    /** 
     * 根據(jù)前序序列遞歸構(gòu)建二叉樹(shù) 
     * 
     * @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(); 
      } 
    } 
  }

二叉樹(shù)的深度

下面是是實(shí)現(xiàn)二叉樹(shù)的遞歸算法的實(shí)現(xiàn)，其思想就是，若為空，則其深度為0，否則，其深度等于左子樹(shù)和右子樹(shù)的深度的最大值加1：

class Node{
 String name;
 Node left;
 Node right;
 public Node(String name) {
 this.name = name;
 }
 @Override
 public String toString() {
 return name;
 }
}
//定義二叉樹(shù)
class BinaryTree{
 Node root;
 
 public BinaryTree(){
 root = null;
 }
 //為了方便起見(jiàn)，我就直接寫(xiě)個(gè)初始化的二叉樹(shù)，詳細(xì)的可以見(jiàn)以前的日志
 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;
 }
 //求二叉樹(shù)的深度
 int length(Node root){
 int depth1;
 int depth2;
 if(root == null) return 0;
 //左子樹(shù)的深度
 depth1 = length(root.right);
 //右子樹(shù)的深度
 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));
 }
}

您可能感興趣的文章: