# 从Java看数据结构之——树和他的操作集

2019/03/07 20:59

## 树的实现

 1 public class BinaryTree<T extends Comparable<T>> {
2     private BinaryTree<T> root;
3     //定义存储内容：内容、左子树、右子树
4     public class Node<T extends Comparable<T>>{
5         T data;
6         BinaryTree<T> left;
7         BinaryTree<T> right;
8         //也可以有父节点
9         BinaryTree<T> parent;
10
11         public Node(T data, BinaryTree<T> left, BinaryTree<T> right, BinaryTree<T> parent) {
12             this.data = data;
13             this.left = left;
14             this.right = right;
15             this.parent = parent;
16         }
17     }
18
19     //定义方法：增、删、查、改。
20
21     public boolean insert(int x){
22         ...
23     }
24     public boolean delete(int x){
25         ...
26     }
27 }

## 树的遍历

1 public void preOrderTraversal(BinaryTree<T> tree){
2     if(tree==null) return;
3     System.out.print(tree.node.data+" ");
4     preOrderTraversal(tree.node.left);
5     preOrderTraversal(tree.node.right);
6 }

1 //中序遍历
2 public void inOrderTraversal(BinaryTree<T> tree){
3     if(tree==null) return;
4     inOrderTraversal(tree.node.left);
5     System.out.print(tree.node.data+" ");
6     inOrderTraversal(tree.node.right);
7 }

1 //后序遍历
2 public void pastOrderTraversal(BinaryTree<T> tree){
3     if(tree==null) return;
4     pastOrderTraversal(tree.node.left);
5     pastOrderTraversal(tree.node.right);
6     System.out.print(tree.node.data+" ");
7 }

 1 public void preOrderTraversal(){
2     Stack<BinaryTree<T>> st = new Stack<>();
3     BinaryTree<T> tmp = this;
4     while(tmp!=null || !st.empty()){
5         while(tmp!=null){
6             System.out.print(tmp.node.data+" ");
7             st.push(tmp);
8             tmp=tmp.node.left;//一路向左
9         }
10         if(!st.empty()){
11             tmp=st.pop();
12             tmp=tmp.node.right;//偶尔向右
13         }
14     }
15     System.out.println();
16 }

 1 public void inOrderTraversal(){
2     Stack<BinaryTree<T>> st = new Stack<>();
3     BinaryTree<T> tmp = this;
4     while(tmp!=null || !st.empty()){
5         while(tmp!=null){
6             st.push(tmp);
7             tmp=tmp.node.left;
8         }
9         if(!st.empty()){
10             tmp=st.pop();
11             //输出变到这里，仅此而已
12             System.out.println(tmp.node.data);
13             tmp=tmp.node.right;
14         }
15     }
16 }

 1 //后续非递归
2 public void PastOrderTraversal(){
3     BinaryTree<T> Tmp = this;
4     Stack<BinaryTree<T>> st = new Stack<>();
5     while(Tmp!=null || !st.empty()){
6         while(Tmp!=null){
7             st.push(Tmp);
8             Tmp=Tmp.node.left;
9         }
10         if(!st.empty()){//if代码块
11             Tmp=st.pop();
12             if(Tmp.node.IsFirstTraversal){//这里判断是不是第一次进if代码块
13                 Tmp.node.IsFirstTraversal=false;//进来过了，置位false，下一次就可以输出了
14                 st.push(Tmp);
15                 Tmp=Tmp.node.right;
16             }
17             else{//不是第一次，输出
18                 System.out.print(Tmp.node.data+" ");
19             }
20         }
21     }
22 }

 1 //层序遍历
2 public void levelOrderTraversal(){
3     Queue<BinaryTree<T>> tQueue = new ArrayDeque<>();
4     BinaryTree<T> tmp = this;
6     while(!tQueue.isEmpty()){
7         tmp = tQueue.remove();
8         System.out.print(tmp.node.data+" ");
11     }
12 }

## 操作集

### 1.插入

 1     private BinaryTree<T> insert(BinaryTree<T> t, Node<T> n){
2         if(t==null) {
3             t = new BinaryTree<>();
4             t.node = n;
5             return t;
6         }
7         int cmp = n.data.compareTo(t.node.data);
8         if(cmp==0) return null;//节点存在
9         else if(cmp<0) t.node.left = insert(t.node.left, n);
10         else t.node.right = insert(t.node.right, n);
11         return t;
12     }
13
14     public void insert(T x){
15         Node<T> n = new Node<>(x,null, null, null);
16         if(this.node==null){
17             this.node = n;
18             return;
19         }
20         insert(this,n);
21     }

### 2.查找

 1 　　 /**
2      * 查找
3      * @param t 树
4      * @param x 查找的值
5      * @return 值所在树
6      */
7     private BinaryTree<T> find(BinaryTree<T> t, T x){
8         int cmp = x.compareTo(t.node.data);
9         if(cmp==0){//找到了
10             return t;
11         }
12         else if(cmp<0) return find(t.node.left,x);
13         else return find(t.node.right,x);
14     }
15
16     public BinaryTree<T> find(T x){
17         return find(this, x);
18     }

0 评论
0 收藏
0