Java实现树的遍历以及打印（递归，非递归）

2019-11-06 09:40:45来源：博客园阅读 ()

Java实现树的遍历以及打印（递归，非递归）

  1 import java.util.LinkedList;
  2 import java.util.Stack;
  3 
  4 public class BinarySearchTree1<E extends Comparable <? super E>>{
  5 
  6     private static class BinaryNode<E> {
  7 
  8         E element;
  9         BinaryNode<E> left;
 10         BinaryNode<E> right;
 11 
 12         BinaryNode(E theElement) {
 13             this(theElement, null, null);
 14         }
 15 
 16         BinaryNode(E theElement, BinaryNode<E> lt, BinaryNode<E> rt) {
 17             element = theElement;
 18             left = lt;
 19             right = rt;
 20         }
 21 
 22     }
 23 
 24     private BinaryNode<E>root;
 25     public void insert(E x){
 26         root = insert(x,root);
 27     }
 28 
 29     private BinaryNode<E> insert(E x, BinaryNode<E> t){
 30 
 31         if (t == null){
 32             return new BinaryNode<>(x,null,null);
 33         }
 34         int compareResult = x.compareTo(t.element);
 35         if (compareResult < 0){
 36             t.left = insert(x,t.left);
 37         }else if (compareResult > 0){
 38             t.right = insert(x,t.right);
 39         }else {
 40             ;
 41         }
 42         return t;
 43 
 44     }
 45 
 46 //        前序遍历递归
 47     public void PreOrder(BinaryNode<E> Node){
 48         if (Node != null){
 49             System.out.print(Node.element + " ");
 50             PreOrder(Node.left);
 51             PreOrder(Node.right);
 52         }
 53     }
 54 //        前序遍历非递归
 55     public void preOrder(BinaryNode<E> Node){
 56         if (Node == null){
 57             return;
 58         }
 59         Stack<BinaryNode<E>> s = new Stack<>();
 60         while (Node != null || !s.empty()) {
 61             if (Node != null) {
 62                 System.out.print(Node.element + " ");
 63                 s.push(Node);
 64                 Node = Node.left;
 65             } else {
 66                 Node = s.pop();
 67                 Node = Node.right;
 68             }
 69         }
 70     }
 71 //        中序遍历递归
 72     public void MidOrder(BinaryNode<E> Node){
 73         if (Node != null){
 74             MidOrder(Node.left);
 75             System.out.print(Node.element + " ");
 76             MidOrder(Node.right);
 77         }
 78     }
 79 //        中序遍历非递归
 80     public void midOrder(BinaryNode<E> Node){
 81         if (Node == null){
 82             return;
 83         }
 84         Stack<BinaryNode<E>> s = new Stack<>();
 85         while (Node != null || !s.empty()){
 86             if (Node != null) {
 87                 s.push(Node);
 88                 Node = Node.left;
 89             }else {
 90                 Node = s.pop();
 91                 System.out.print(Node.element + " ");
 92                 Node = Node.right;
 93             }
 94         }
 95     }
 96 //        后序遍历递归
 97     public void PosOrder(BinaryNode<E> Node){
 98         if (Node != null){
 99             PosOrder(Node.left);
100             PosOrder(Node.right);
101             System.out.print(Node.element + " ");
102         }
103     }
104 //        后序遍历非递归
105     public void posOrder(BinaryNode<E> Node){
106         if (Node == null){
107             return;
108         }
109         Stack<BinaryNode<E>> s = new Stack<>();
110         BinaryNode<E> NowNode;
111         BinaryNode<E> BefNode;
112         NowNode = Node;
113         BefNode = Node;
114         //把NowNode移到左子树下边
115         while (NowNode != null){
116             s.push(NowNode);
117             NowNode = NowNode.left;
118         }
119         while (s != null){
120             NowNode = s.pop();
121             //无右子树或右子树已被访问
122             if (NowNode.right != null && NowNode.right != BefNode){
123                 s.push(NowNode);
124                 NowNode = NowNode.left;
125                 if (NowNode != null){
126                     s.push(NowNode);
127                     NowNode = NowNode.left;
128                 }
129             }else {
130                 System.out.print(NowNode.element + " ");
131                 BefNode = NowNode;
132             }
133         }
134     }
135 //        层序遍历队列
136     public void levelOrder(BinaryNode<E> Node){
137         LinkedList<BinaryNode<E>> list = new LinkedList<>();
138         list.add(Node);
139         while (!list.isEmpty()){
140             Node = list.poll();
141             System.out.print(Node.element + " ");
142             if (Node.left != null){
143                 list.offer(Node.left);
144             }
145             if (Node.right != null){
146                 list.offer(Node.right);
147             }
148         }
149 
150     }
151 
152     //    树的深度
153     public int Depth(BinaryNode<E> Node){
154 
155         if (Node == null){
156             return 0;
157         }
158         int l = Depth(Node.left);
159         int r = Depth(Node.right);
160         if (l > r){
161             return l+1;
162         }else {
163             return r+1;
164         }
165 
166     }
167 
168     //    桉树状打印二叉树
169     public void PrintTree(BinaryNode<E> Node,int high){
170         if (Node == null){
171             return;
172         }
173         PrintTree(Node.right,high+1);
174         for (int i = 0 ; i < high ; i++) {
175             System.out.print(" ");
176         }
177             System.out.println(Node.element + " ");
178             PrintTree(Node.left,high+1);
179     }
180 
181     public static void main(String[] args) {
182         int [] input = {4,2,6,1,3,5,7,8,10};
183         BinarySearchTree1<Integer> tree = new BinarySearchTree1<>();
184         for (int i = 0 ; i < input.length ; i++){
185             tree.insert(input[i]);
186         }
187         System.out.print("递归前序遍历：  ");
188         tree.PreOrder(tree.root);
189         System.out.println();
190         System.out.print("非递归前序遍历：");
191         tree.preOrder(tree.root);
192         System.out.println();
193         System.out.print("递归中序遍历：  ");
194         tree.MidOrder(tree.root);
195         System.out.println();
196         System.out.print("非递归中序遍历：");
197         tree.midOrder(tree.root);
198         System.out.println();
199         System.out.print("递归后序遍历：  ");
200         tree.PosOrder(tree.root);
201         System.out.println();
202 //        System.out.print("非递归后序遍历：");
203 //        tree.posOrder(tree.root);
204 //        System.out.println();
205         System.out.print("队列层序遍历：  ");
206         tree.levelOrder(tree.root);
207         System.out.println();
208         tree.PrintTree(tree.root,tree.Depth(tree.root));
209     }
210 
211 }