黑马程序员技术交流社区

标题: java 树结构 [打印本页]
作者: pi408637535    时间: 2015-7-14 16:08
标题: java 树结构
  1. import java.util.*;


  4. public class Main
  5. {
  6.     public static void main(String[] args)
  7.     {
  8.             BinaryTree biTree = new BinaryTree();  
  9.               
  10.         int[] data = { 2, 8, 7, 4 ,9,3,1,6,7,5};  
  11.   
  12.         biTree.buildTree(data);  
  13.   
  14.         biTree.printTree();  
  15.   
  16.     }  

  18. }
复制代码

//实现
  1. public class BinaryTree {
  2.         private Node root;  
  3.    
  4.     /**
  5.      * 内部类实现结点类，可提高安全性
  6.      * @author nishiting
  7.      *
  8.      */  
  9.   
  10.     private static class Node {  
  11.         Node left;  
  12.         Node right;  
  13.         int data;  
  14.   
  15.         Node(int newData) {  
  16.             left = null;  
  17.             right = null;  
  18.             data = newData;  
  19.         }  
  20.   
  21.     }  
  22.   
  23.     /**
  24.      * 创建一个空的二叉树
  25.      */  
  26.   
  27.     public BinaryTree() {  
  28.         root = null;  
  29.     }  
  30.       
  31.     /**
  32.      * 递归的插入数值
  33.      * @param data  要插入的数值
  34.      */  
  35.   
  36.     public void insert(int data) {  
  37.         root = insert(root, data);  
  38.     }  
  39.       
  40.     /**
  41.      * 将数值插入到二叉树中，比当前结点小或等于当前结点的插在当前结点的左侧，比当前结点大的数插在当前结点的右侧，每次从根结点开始递归比较
  42.      * @param node  当前的结点，就是根结点，只是每次根结点的左右子孙更新
  43.      * @param data  要插入的数值
  44.      * @return  新排好的二叉树
  45.      */  
  46.   
  47.     private Node insert(Node node, int data) {  
  48.   
  49.         if (node == null) {  
  50.   
  51.             node = new Node(data);  
  52.   
  53.         } else {  
  54.             if (data <= node.data) {  
  55.                 node.left = insert(node.left, data);  
  56.             } else {  
  57.                 node.right = insert(node.right, data);  
  58.             }  
  59.         }  
  60.         return (node);  
  61.     }  
  62.       
  63.     /**
  64.      * 将数值输入构建二叉树
  65.      * @param data  要输入的数值
  66.      */  
  67.   
  68.     public void buildTree(int[] data) {  
  69.   
  70.         for (int i = 0; i < data.length; i++) {  
  71.   
  72.             insert(data[i]);  
  73.   
  74.         }  
  75.   
  76.     }  
  77.       
  78.     /**
  79.      * 递归打印出二叉树
  80.      */  
  81.   
  82.     public void printTree() {  
  83.   
  84.         printTree(root);  
  85.   
  86.         System.out.println();  
  87.   
  88.     }  
  89.       
  90.     /**
  91.      * 从根结点开始遍历，从树的最高层叶子结点开始输出，从左至右
  92.      * @param node  当前的结点
  93.      */  
  94.   
  95.     private void printTree(Node node) {  
  96.   
  97.         if (node == null)  
  98.             return;  
  99.   
  100.         // left, node itself, right  
  101.   
  102.         printTree(node.left);  
  103.   
  104.         System.out.print(node.data + "  ");  
  105.   
  106.         printTree(node.right);  
  107.   
  108.     }  
  109. }
复制代码




欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2