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

Z时代
2024-01-10
分类：综合
coding
  1import java.util.LinkedList;
  2import java.util.Stack;
  3
  4publicclass BinarySearchTree1<E extends Comparable <? super E>>{
  5
  6privatestaticclass BinaryNode<E> {
  7
  8        E element;
  9         BinaryNode<E> left;
 10         BinaryNode<E> right;
 11
 12        BinaryNode(E theElement) {
 13this(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
 24private BinaryNode<E>root;
 25publicvoid insert(E x){
 26         root = insert(x,root);
 27    }
 28
 29private BinaryNode<E> insert(E x, BinaryNode<E> t){
 30
 31if (t == null){
 32returnnew BinaryNode<>(x,null,null);
 33        }
 34int compareResult = x.compareTo(t.element);
 35if (compareResult < 0){
 36             t.left = insert(x,t.left);
 37         }elseif (compareResult > 0){
 38             t.right = insert(x,t.right);
 39         }else {
 40            ;
 41        }
 42return t;
 43
 44    }
 45
 46//        前序遍历递归
 47publicvoid PreOrder(BinaryNode<E> Node){
 48if (Node != null){
 49             System.out.print(Node.element + " ");
 50            PreOrder(Node.left);
 51            PreOrder(Node.right);
 52        }
 53    }
 54//        前序遍历非递归
 55publicvoid preOrder(BinaryNode<E> Node){
 56if (Node == null){
 57return;
 58        }
 59         Stack<BinaryNode<E>> s = new Stack<>();
 60while (Node != null || !s.empty()) {
 61if (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//        中序遍历递归
 72publicvoid MidOrder(BinaryNode<E> Node){
 73if (Node != null){
 74            MidOrder(Node.left);
 75             System.out.print(Node.element + " ");
 76            MidOrder(Node.right);
 77        }
 78    }
 79//        中序遍历非递归
 80publicvoid midOrder(BinaryNode<E> Node){
 81if (Node == null){
 82return;
 83        }
 84         Stack<BinaryNode<E>> s = new Stack<>();
 85while (Node != null || !s.empty()){
 86if (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//        后序遍历递归
 97publicvoid PosOrder(BinaryNode<E> Node){
 98if (Node != null){
 99            PosOrder(Node.left);
100            PosOrder(Node.right);
101             System.out.print(Node.element + " ");
102        }
103    }
104//        后序遍历非递归
105publicvoid posOrder(BinaryNode<E> Node){
106if (Node == null){
107return;
108        }
109         Stack<BinaryNode<E>> s = new Stack<>();
110         BinaryNode<E> NowNode;
111         BinaryNode<E> BefNode;
112         NowNode = Node;
113         BefNode = Node;
114//把NowNode移到左子树下边
115while (NowNode != null){
116            s.push(NowNode);
117             NowNode = NowNode.left;
118        }
119while (s != null){
120             NowNode = s.pop();
121//无右子树或右子树已被访问
122if (NowNode.right != null && NowNode.right != BefNode){
123                s.push(NowNode);
124                 NowNode = NowNode.left;
125if (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//        层序遍历队列
136publicvoid levelOrder(BinaryNode<E> Node){
137         LinkedList<BinaryNode<E>> list = new LinkedList<>();
138        list.add(Node);
139while (!list.isEmpty()){
140             Node = list.poll();
141             System.out.print(Node.element + " ");
142if (Node.left != null){
143                list.offer(Node.left);
144            }
145if (Node.right != null){
146                list.offer(Node.right);
147            }
148        }
149
150    }
151
152//    树的深度
153publicint Depth(BinaryNode<E> Node){
154
155if (Node == null){
156return 0;
157        }
158int l = Depth(Node.left);
159int r = Depth(Node.right);
160if (l > r){
161return l+1;
162         }else {
163return r+1;
164        }
165
166    }
167
168//    桉树状打印二叉树
169publicvoid PrintTree(BinaryNode<E> Node,int high){
170if (Node == null){
171return;
172        }
173         PrintTree(Node.right,high+1);
174for (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
181publicstaticvoid main(String[] args) {
182int [] input = {4,2,6,1,3,5,7,8,10};
183         BinarySearchTree1<Integer> tree = new BinarySearchTree1<>();
184for (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    }
210211 }