Java 实现二叉树

原文链接:

http://www.cnblogs.com/lzq198754/p/5857597.html

 1 public class TreeNode {
 2     private TreeNode leftNode;
 3     private TreeNode rightNode;
 4     private int value;
 5     private boolean isdeleteOrNot;
 6 
 7     public TreeNode getLeftNode() {
 8         return leftNode;
 9     }
10 
11     public void setLeftNode(TreeNode leftNode) {
12         this.leftNode = leftNode;
13     }
14 
15     public TreeNode getRightNode() {
16         return rightNode;
17     }
18 
19     public TreeNode() {
20         super();
21     }
22 
23     public void setRightNode(TreeNode rightNode) {
24         this.rightNode = rightNode;
25     }
26 
27     public int getValue() {
28         return value;
29     }
30 
31     public void setValue(int value) {
32         this.value = value;
33     }
34 
35     public boolean isIsdeleteOrNot() {
36         return isdeleteOrNot;
37     }
38 
39     public void setIsdeleteOrNot(boolean isdeleteOrNot) {
40         this.isdeleteOrNot = isdeleteOrNot;
41     }
42 
43     public TreeNode(int value) {
44         this(null, null, value, false);
45     }
46 
47     public TreeNode(TreeNode leftNode, TreeNode rightNode, int value, boolean isdeleteOrNot) {
48         super();
49         this.leftNode = leftNode;
50         this.rightNode = rightNode;
51         this.value = value;
52         this.isdeleteOrNot = isdeleteOrNot;
53     }
54 
55 }

  1 /**
  2  * 二叉树的 Java 实现
  3  * 
  4  */
  5 public class BinTree {
  6     private TreeNode rootNode;
  7 
  8     public TreeNode getRootNode() {
  9         return rootNode;
 10     }
 11 
 12     /**
 13      * 二叉树的插入操作
 14      */
 15     public void insertValue(int value) {
 16         TreeNode newNode = new TreeNode(value);
 17         // 如果根节点为空, 则新节点即是根节点
 18         if (rootNode == null) {
 19             rootNode = newNode;
 20             rootNode.setLeftNode(null);
 21             rootNode.setRightNode(null);
 22         } else {
 23             TreeNode currenNode = rootNode;
 24             TreeNode parenNode;
 25             while (true) {
 26                 parenNode = currenNode;
 27                 // 放在右边
 28                 if (newNode.getValue() > currenNode.getValue()) {
 29                     currenNode = currenNode.getRightNode();
 30                     if (currenNode == null) {
 31                         parenNode.setRightNode(newNode);
 32                         return;
 33                     }
 34                 } else {
 35                     // 放在左边
 36                     currenNode = currenNode.getLeftNode();
 37                     if (currenNode == null) {
 38                         parenNode.setLeftNode(newNode);
 39                         return;
 40                     }
 41 
 42                 }
 43             }
 44         }
 45     }
 46 
 47     /**
 48      * 二叉树的升序遍历
 49      */
 50     public void orderByAsc(TreeNode treeNode) {
 51         if (treeNode != null && treeNode.isIsdeleteOrNot() == false) {
 52             orderByAsc(treeNode.getLeftNode());
 53             System.out.println(treeNode.getValue());
 54             orderByAsc(treeNode.getRightNode());
 55         }
 56     }
 57 
 58     /**
 59      * 二叉树的降序遍历
 60      */
 61     public void orderByDesc(TreeNode treeNode) {
 62         if (treeNode != null && treeNode.isIsdeleteOrNot() == false) {
 63             orderByDesc(treeNode.getRightNode());
 64             System.out.println(treeNode.getValue());
 65             orderByDesc(treeNode.getLeftNode());
 66         }
 67     }
 68 
 69     /**
 70      * 二叉树的查找
 71      */
 72     public TreeNode findKey(int key) {
 73         TreeNode currenNode = rootNode;
 74         if (currenNode != null) {
 75             while (currenNode.getValue() != key) {
 76                 if (currenNode.getValue() > key) {
 77                     currenNode = currenNode.getLeftNode();
 78                 } else {
 79                     currenNode = currenNode.getRightNode();
 80                 }
 81                 if (currenNode == null) {
 82                     return null;
 83                 }
 84             }
 85             if (currenNode.isIsdeleteOrNot()) {
 86                 return null;
 87             } else {
 88                 return currenNode;
 89             }
 90         } else {
 91             return null;
 92         }
 93     }
 94 
 95     public static void main(String[] args) {
 96         BinTree binTree = new BinTree();
 97         binTree.insertValue(10);
 98         binTree.insertValue(12);
 99         binTree.insertValue(13);
100         binTree.orderByAsc(binTree.getRootNode());
101         System.out.println("-------------------");
102         binTree.orderByDesc(binTree.getRootNode());
103         System.out.println("-------------------");
104         System.out.println(binTree.findKey(10));
105     }
106 
107 }