数据结构之二叉树

1 //节点类，用于存储二叉树的结点信息
2 class Node {
3     public int data;
4     public Node leftChild;
5     public Node rightChild;
6 
7 }

 1 class Tree {
 2     private Node root;
 3     Node current = root;
 4 
 5     // 查找元素
 6     public Node findNode(int key) {
 7         while (current.data != key) {
 8             if (key < current.data) {
 9                 current = current.leftChild;
10             } else {
11                 current = current.rightChild;
12             }
13             if (current == null) {
14                 return null;
15             }
16         }
17         return current;
18     }
19 
20     // 插入元素
21     public void insert(int key) {
22         Node newNode = new Node();
23         newNode.data = key;
24         if (root == null) {
25             root = newNode;
26         } else {
27             Node current = root;
28             // 定义parent，存储最后遇到的一个不是null的节点
29             Node parent = current;
30             while (true) {
31                 if (key < current.data) {
32                     current = current.leftChild;
33                     if (current == null) {
34                         current.leftChild = newNode;
35                         return;
36                     }
37                 } else {
38                     current = current.rightChild;
39                     if (current == null) {
40                         current.rightChild = newNode;
41                         return;
42                     }
43                 }
44             }
45         }
46     }
47}

 1     /*
 2      * 二叉树的中序遍历：遍历操作不只是针对二叉排序树，遍历的原理不关注节点的关键字值，而只是看这个节点是不是存在子树
 3      *  1.调用自身来遍历节点的左子树 
 4      *  2.访问这个节点 
 5      *  3.调用自身来遍历节点的右子树
 6      */
 7     public void inSort(Node root){
 8         if(root!=null){
 9             inSort(root.leftChild);
10             System.out.println(root.data);
11             inSort(root.rightChild);
12         }
13     }

/* 二叉树的前序遍历(preOrderTraverse）
       1.访问这个节点 
     * 2.调用自身来遍历节点的左子树 
     * 3.调用自身来遍历节点的右子树
     * 
     */

1 public void preOrderTraverse(Node root){
2         if(root!=null){
3             System.out.println(root.data);
4             preOrderTraverse(root.leftChild);
5             preOrderTraverse(root.rightChild);
6         }
7     }

/* 二叉树的后序遍历(OrderTraverse）
       1.访问这个节点 
     * 2.调用自身来遍历节点的左子树 
     * 3.调用自身来遍历节点的右子树
     * 
     */

1 public void postOrderTraverse(Node root){
2         if(root!=null){
3             postOrderTraverse(root.leftChild);
4             postOrderTraverse(root.rightChild);
5             System.out.println(root.data);
6         }
7     }

 1 /*
 2      * 二叉排序树查找最值
 3      */
 4     //查找最大值
 5     public Node maxNode(){
 6         Node current=root;
 7         Node lastNode = null;
 8         while(current!=null){
 9             lastNode=current;
10             current=current.leftChild;
11         }
12         return lastNode;    
13     }
14     /*
15      * 二叉排序树查找最值
16      */
17     //查找最小值
18     public Node minNode(){
19         Node current=root;
20         Node lastNode = null;
21         while(current!=null){
22             lastNode=current;
23             current=current.rightChild;
24         }
25         return lastNode;    
26     }