线索化二叉树

1. class IntThreadedTreeNode {
2.     protected int key;
3.     protected boolean hasSuccessor;                    //右子女指针是否是线索：线索 - true, 孩子 - false
4.     protected IntThreadedTreeNode left, right;
5.     public IntThreadedTreeNode() {
6.         left = right = null; hasSuccessor = false;
7.     }
8.     public IntThreadedTreeNode(int el) {
9.         this(el,null,null);
10.     }
11.     public IntThreadedTreeNode(int el, IntThreadedTreeNode lt,
12.                                        IntThreadedTreeNode rt) {
13.         key = el; left = lt; right = rt; hasSuccessor = false;
14.     }
15. }
16.  
17. public class IntThreadedTree {
18.     private IntThreadedTreeNode root;
19.     public IntThreadedTree() {
20.         root = null;
21.     }
22.     protected void visit(IntThreadedTreeNode p) {
23.         System.out.print(p.key + " ");
24.     }
25.     
26.     /**
27.     *        插入
28.     **/
29.     public void threadedInsert(int el) {
30.         IntThreadedTreeNode newNode = new IntThreadedTreeNode(el);
31.         if (root == null) {              // tree is empty
32.               root = newNode;
33.               return;
34.         }
35.         IntThreadedTreeNode p = root, prev = null;
36.         while (p != null) {              // find a place to insert newNode;
37.              prev = p;
38.              if (el < p.key)
39.                   p = p.left;
40.              else if (!p.hasSuccessor)   // go to the right node only if it is
41.                   p = p.right;           // a descendant, not a successor;
42.              else break;                 // don‘t follow successor link;
43.         }
44.         if (el < prev.key) {             // if newNode is left child of
45.              prev.left  = newNode;       // its parent, the parent becomes
46.              newNode.hasSuccessor = true;// also its successor;
47.              newNode.right = prev;
48.         }
49.         else if (prev.hasSuccessor) {    // if parent of the newNode
50.              newNode.hasSuccessor = true;// is not the right-most node,
51.              prev.hasSuccessor = false;  // make parent‘s successor
52.              newNode.right = prev.right; // newNode‘s successor,
53.              prev.right = newNode;
54.         }
55.         else prev.right = newNode;       // otherwise has no successor;
56.     }
57.     
58.     /**
59.     *    中序遍历
60.     **/
61.     protected void threadedInorder() {
62.         IntThreadedTreeNode prev = null, p = root;
63.         if (p != null) {                 // process only non-empty trees;
64.             while (p.left != null)       // go to the leftmost node;
65.                 p = p.left;
66.             while (p != null) {
67.                 visit(p);
68.                 prev = p;
69.                 p = p.right;             // go to the right node and only
70.                 if (p != null && !prev.hasSuccessor)// if it is a descendant
71.                     while (p.left != null)          // go to the leftmost node,
72.                         p = p.left;      // otherwise visit the successor;
73.             }
74.         }
75.     }
76.     
77.     /**
78.     *    中序遍历
79.     **/
80.     protected void threadedInorderPlus() {
81.         IntThreadedTreeNode prev = null, p = root;
82.  
83.         while (p != null) {
84.             if (p.left != null) {
85.                 p = p.left;
86.             } else {
87.                 visit(p);
88.                 prev = p;
89.                 p = p.right;
90.                 if (prev.hasSuccessor) {
91.                     visit(p);
92.                     p = p.right;
93.                 }
94.             }
95.         }
96.     }
97.  
98.     public static void testThreadedInorderPlus() {
99.         IntThreadedTree tree = new IntThreadedTree();
100.         int[] array = {4, 2, 6, 1, 3, 5, 7, };
101.         for (int el : array) {
102.             tree.threadedInsert(el);
103.         }
104.         tree.threadedInorder();
105.     }
106.  
107.     public static void main(String[] args) {
108.         testThreadedInorderPlus();
109.     }
110. }