二叉树的线索化与遍历

  1 package dataSrtuct.TreeAlgorithm;
  2 
  3 import com.sun.source.tree.Tree;
  4 
  5 public class ThreadBinaryTree {
  6     public static void main(String[] args) {
  7         TreeNode2 root = new TreeNode2(1, "M");
  8         TreeNode2 node2 = new TreeNode2(3, "N");
  9         TreeNode2 node3 = new TreeNode2(6, "O");
 10         TreeNode2 node4 = new TreeNode2(8, "P");
 11         TreeNode2 node5 = new TreeNode2(10, "Q");
 12         TreeNode2 node6 = new TreeNode2(14, "Z");
 13         root.setLeftNext(node2);
 14         root.setRightNext(node3);
 15         node2.setLeftNext(node4);
 16         node2.setRightNext(node5);
 17         node3.setLeftNext(node6);
 18         TBinaryTree tBinaryTree = new TBinaryTree();
 19         tBinaryTree.setRoot(root);
 20         tBinaryTree.infixOrder();
 21         tBinaryTree.threadBinaryTree(root);
 22         System.out.println("node5的前驱结点是："+node6.getLeftNext().getVal());
 23         System.out.println("node5的后继结点是："+node6.getRightNext().getVal());
 24         System.out.println("node4的前驱结点是："+node4.getLeftNext());
 25         tBinaryTree.threadBinaryTreePrint();
 26 
 27     }
 28 }
 29 //线索化二叉树
 30 class TBinaryTree{
 31     private TreeNode2 root;
 32     private TreeNode2 preNode;
 33     public TreeNode2 getRoot() {
 34         return root;
 35     }
 36 
 37     public void setRoot(TreeNode2 root) {
 38         this.root = root;
 39     }
 40 
 41     /**
 42      * 遍历线索话二叉树
 43      */
 44     public void threadBinaryTreePrint(){
 45         TreeNode2 node=this.root;
 46         while (node!=null){
 47             while (node.getLeftNodeType()==0){
 48                 node=node.getLeftNext();
 49             }
 50             System.out.println(node);
 51             while (node.getRightNodeType()==1){
 52                 node=node.getRightNext();
 53                 System.out.println(node);
 54             }
 55             node=node.getRightNext();
 56         }
 57     }
 58     /**
 59      *线索化二叉树
 60      * @param node 当前节点
 61      */
 62     public void threadBinaryTree(TreeNode2 node){
 63         if (node==null)
 64             return;
 65         threadBinaryTree(node.getLeftNext());
 66         if (node.getLeftNext()==null) {
 67             node.setLeftNext(preNode);
 68             node.setLeftNodeType(1);
 69         }
 70         if (preNode!=null&&preNode.getRightNext()==null) {
 71             preNode.setRightNext(node);
 72             preNode.setRightNodeType(1);
 73         }
 74         //整个线索化代码最难的地方，因为你的一个节点指定完前驱和后继之后一定会成为前驱节点，
 75         preNode=node;
 76         threadBinaryTree(node.getRightNext());
 77     }
 78     //先序遍历
 79     public void preOrder(){
 80         if (this.root!=null)
 81             this.root.preOrder();
 82         else
 83             System.out.println("二叉树为空，不能遍历");
 84     }
 85     ///中序遍历
 86     public void infixOrder(){
 87         if (this.root!=null)
 88             this.root.infixOrder();
 89         else
 90             System.out.println("二叉树为空，不能遍历");
 91     }
 92     //后序遍历
 93     public void postOrder(){
 94         if (this.root!=null)
 95             this.root.postOrder();
 96         else
 97             System.out.println("二叉树为空，不能遍历");
 98     }
 99     //前、后、中序查找
100     //先序查找
101     public TreeNode2 preOrderSearch(int val){
102         if (this.root!=null)
103             return this.root.preOrderSearch(val);
104         else {
105             System.out.println("二叉树为空，不能遍历");
106             return null;
107         }
108     }
109     //中序查找
110     public TreeNode2 infixOrderSearch(int val){
111         if (this.root!=null)
112             return this.root.infixOrderSearch(val);
113         else {
114             System.out.println("二叉树为空，不能遍历");
115             return null;
116         }
117     }
118     //后序查找
119     public TreeNode2 postOrderSearch(int val){
120         if (this.root!=null)
121             return this.root.postOrderSearch(val);
122         else {
123             System.out.println("二叉树为空，不能遍历");
124             return null;
125         }
126 
127     }
128 }
129 //创建各个节点
130 class TreeNode2{
131     private int val;
132     private String name;
133     //0为指向树，1为事项前后节点
134     private TreeNode2 leftNext;
135     private TreeNode2 rightNext;
136     private int leftNodeType;
137     private int rightNodeType;
138     public static int countPre;
139     public static int countInfix;
140     public static int countPost;
141     static {
142         countPre=0;
143         countInfix=0;
144         countPost=0;
145     }
146 
147     public TreeNode2(int val, String name) {
148         this.val = val;
149         this.name = name;
150     }
151 
152     public int getLeftNodeType() {
153         return leftNodeType;
154     }
155 
156     public void setLeftNodeType(int leftNodeType) {
157         this.leftNodeType = leftNodeType;
158     }
159 
160     public int getRightNodeType() {
161         return rightNodeType;
162     }
163 
164     public void setRightNodeType(int rightNodeType) {
165         this.rightNodeType = rightNodeType;
166     }
167 
168     public int getVal() {
169         return val;
170     }
171 
172     public void setVal(int val) {
173         this.val = val;
174     }
175 
176     public String getName() {
177         return name;
178     }
179 
180     public void setName(String name) {
181         this.name = name;
182     }
183 
184     public TreeNode2 getLeftNext() {
185         return leftNext;
186     }
187 
188     public void setLeftNext(TreeNode2 leftNext) {
189         this.leftNext = leftNext;
190     }
191 
192     public TreeNode2 getRightNext() {
193         return rightNext;
194     }
195 
196     public void setRightNext(TreeNode2 rightNext) {
197         this.rightNext = rightNext;
198     }
199 
200     @Override
201     public String toString() {
202         return "TreeNode2{" +
203                 "val=" + val +
204                 ", name='" + name + '\'' +
205                 '}';
206     }
207     //先序查找
208     public TreeNode2 preOrderSearch(int val){
209         TreeNode2.countPre++;
210         if (this.val==val)
211             return this;
212         TreeNode2 tempNode=null;
213         if (this.leftNext!=null)
214             tempNode=this.leftNext.preOrderSearch(val);
215         if (tempNode!=null)
216             return tempNode;
217         if (this.rightNext!=null)
218             tempNode= this.rightNext.preOrderSearch(val);
219         return tempNode;
220     }
221     //中序查找
222     public TreeNode2 infixOrderSearch(int val){
223         TreeNode2.countInfix++;
224         TreeNode2 tempNode=null;
225         if (this.leftNext!=null)
226             tempNode=this.leftNext.infixOrderSearch(val);
227         if (tempNode!=null)
228             return tempNode;
229         if (this.val==val)
230             return this;
231         if (this.rightNext!=null)
232             tempNode=this.rightNext.infixOrderSearch(val);
233         return tempNode;
234     }
235     //后序查找
236     public TreeNode2 postOrderSearch(int val){
237         TreeNode2.countPost++;
238         TreeNode2 tempNode=null;
239         if (this.leftNext!=null)
240             tempNode=this.leftNext.postOrderSearch(val);
241         if (tempNode!=null)
242             return tempNode;
243         if (this.rightNext!=null)
244             tempNode=this.rightNext.postOrderSearch(val);
245         if (tempNode!=null)
246             return tempNode;
247         if (this.val==val)
248             return this;
249         return tempNode;
250 
251     }
252     //先序遍历
253     public void preOrder(){
254         System.out.println(this);
255         if (this.leftNext!=null)
256             this.leftNext.preOrder();
257         if (this.rightNext!=null)
258             this.rightNext.preOrder();
259     }
260     ///中序遍历
261     public void infixOrder(){
262         if (this.leftNext!=null)
263             this.leftNext.infixOrder();
264         System.out.println(this);
265         if (this.rightNext!=null)
266             this.rightNext.infixOrder();
267     }
268     //后序遍历
269     public void postOrder(){
270         if (this.leftNext!=null)
271             this.leftNext.postOrder();
272         if (this.rightNext!=null)
273             this.rightNext.postOrder();
274         System.out.println(this);
275     }
276 }