package edu.cumt.jnotnull;   

1.   

2. import java.util.Stack;   

3.   

4. public class BinaryTree {   

5.     protected Node root;   

6.   

7.     public BinaryTree(Node root) {   

8.         this.root = root;   

9.     }   

10.   

11.     public Node getRoot() {   

12.         return root;   

13.     }   

14.   

15.     /** 構(gòu)造樹 */  

16.     public static Node init() {   

17.         Node a = new Node('A');   

18.         Node b = new Node('B', null, a);   

19.         Node c = new Node('C');   

20.         Node d = new Node('D', b, c);   

21.         Node e = new Node('E');   

22.         Node f = new Node('F', e, null);   

23.         Node g = new Node('G', null, f);   

24.         Node h = new Node('H', d, g);   

25.         return h;// root   

26.     }   

27.   

28.     /** 訪問節(jié)點 */  

29.     public static void visit(Node p) {   

30.         System.out.print(p.getKey() + " ");   

31.     }   

32.   

33.     /** 遞歸實現(xiàn)前序遍歷 */  

34.     protected static void preorder(Node p) {   

35.         if (p != null) {   

36.             visit(p);   

37.             preorder(p.getLeft());   

38.             preorder(p.getRight());   

39.         }   

40.     }   

41.   

42.     /** 遞歸實現(xiàn)中序遍歷 */  

43.     protected static void inorder(Node p) {   

44.         if (p != null) {   

45.             inorder(p.getLeft());   

46.             visit(p);   

47.             inorder(p.getRight());   

48.         }   

49.     }   

50.   

51.     /** 遞歸實現(xiàn)后序遍歷 */  

52.     protected static void postorder(Node p) {   

53.         if (p != null) {   

54.             postorder(p.getLeft());   

55.             postorder(p.getRight());   

56.             visit(p);   

57.         }   

58.     }   

59.   

60.     /** 非遞歸實現(xiàn)前序遍歷 */  

61.     protected static void iterativePreorder(Node p) {   

62.         Stack<Node> stack = new Stack<Node>();   

63.         if (p != null) {   

64.             stack.push(p);   

65.             while (!stack.empty()) {   

66.                 p = stack.pop();   

67.                 visit(p);   

68.                 if (p.getRight() != null)   

69.                     stack.push(p.getRight());   

70.                 if (p.getLeft() != null)   

71.                     stack.push(p.getLeft());   

72.             }   

73.         }   

74.     }   

75.   

76.     /** 非遞歸實現(xiàn)前序遍歷2 */  

77.     protected static void iterativePreorder2(Node p) {   

78.         Stack<Node> stack = new Stack<Node>();   

79.         Node node = p;   

80.         while (node != null || stack.size() > 0) {   

81.             while (node != null) {//壓入所有的左節(jié)點，壓入前訪問它   

82.                 visit(node);   

83.                 stack.push(node);   

84.                 node = node.getLeft();   

85.             }   

86.             if (stack.size() > 0) {//   

87.                 node = stack.pop();   

88.                 node = node.getRight();   

89.             }   

90.         }   

91.     }   

92.   

93.     /** 非遞歸實現(xiàn)后序遍歷 */  

94.     protected static void iterativePostorder(Node p) {   

95.         Node q = p;   

96.         Stack<Node> stack = new Stack<Node>();   

97.         while (p != null) {   

98.             // 左子樹入棧   

99.             for (; p.getLeft() != null; p = p.getLeft())   

100.                 stack.push(p);   

101.             // 當(dāng)前節(jié)點無右子或右子已經(jīng)輸出   

102.             while (p != null && (p.getRight() == null || p.getRight() == q)) {   

103.                 visit(p);   

104.                 q = p;// 記錄上一個已輸出節(jié)點   

105.                 if (stack.empty())   

106.                     return;   

107.                 p = stack.pop();   

108.             }   

109.             // 處理右子   

110.             stack.push(p);   

111.             p = p.getRight();   

112.         }   

113.     }   

114.   

115.     /** 非遞歸實現(xiàn)后序遍歷 雙棧法 */  

116.     protected static void iterativePostorder2(Node p) {   

117.         Stack<Node> lstack = new Stack<Node>();   

118.         Stack<Node> rstack = new Stack<Node>();   

119.         Node node = p, right;   

120.         do {   

121.             while (node != null) {   

122.                 right = node.getRight();   

123.                 lstack.push(node);   

124.                 rstack.push(right);   

125.                 node = node.getLeft();   

126.             }   

127.             node = lstack.pop();   

128.             right = rstack.pop();   

129.             if (right == null) {   

130.                 visit(node);   

131.             } else {   

132.                 lstack.push(node);   

133.                 rstack.push(null);   

134.             }   

135.             node = right;   

136.         } while (lstack.size() > 0 || rstack.size() > 0);   

137.     }   

138.   

139.     /** 非遞歸實現(xiàn)后序遍歷 單棧法*/  

140.     protected static void iterativePostorder3(Node p) {   

141.         Stack<Node> stack = new Stack<Node>();   

142.         Node node = p, prev = p;   

143.         while (node != null || stack.size() > 0) {   

144.             while (node != null) {   

145.                 stack.push(node);   

146.                 node = node.getLeft();   

147.             }   

148.             if (stack.size() > 0) {   

149.                 Node temp = stack.peek().getRight();   

150.                 if (temp == null || temp == prev) {   

151.                     node = stack.pop();   

152.                     visit(node);   

153.                     prev = node;   

154.                     node = null;   

155.                 } else {   

156.                     node = temp;   

157.                 }   

158.             }   

159.   

160.         }   

161.     }   

162.   

163.     /** 非遞歸實現(xiàn)后序遍歷4 雙棧法*/  

164.     protected static void iterativePostorder4(Node p) {   

165.         Stack<Node> stack = new Stack<Node>();   

166.         Stack<Node> temp = new Stack<Node>();   

167.         Node node = p;   

168.         while (node != null || stack.size() > 0) {   

169.             while (node != null) {   

170.                 temp.push(node);   

171.                 stack.push(node);   

172.                 node = node.getRight();   

173.             }   

174.             if (stack.size() > 0) {   

175.                 node = stack.pop();   

176.                 node = node.getLeft();   

177.             }   

178.         }   

179.         while (temp.size() > 0) {   

180.             node = temp.pop();   

181.             visit(node);   

182.         }   

183.     }   

184.   

185.     /** 非遞歸實現(xiàn)中序遍歷 */  

186.     protected static void iterativeInorder(Node p) {   

187.         Stack<Node> stack = new Stack<Node>();   

188.         while (p != null) {   

189.             while (p != null) {   

190.                 if (p.getRight() != null)   

191.                     stack.push(p.getRight());// 當(dāng)前節(jié)點右子入棧   

192.                 stack.push(p);// 當(dāng)前節(jié)點入棧   

193.                 p = p.getLeft();   

194.             }   

195.             p = stack.pop();   

196.             while (!stack.empty() && p.getRight() == null) {   

197.                 visit(p);   

198.                 p = stack.pop();   

199.             }   

200.             visit(p);   

201.             if (!stack.empty())   

202.                 p = stack.pop();   

203.             else  

204.                 p = null;   

205.         }   

206.     }   

207.   

208.     /** 非遞歸實現(xiàn)中序遍歷2 */  

209.     protected static void iterativeInorder2(Node p) {   

210.         Stack<Node> stack = new Stack<Node>();   

211.         Node node = p;   

212.         while (node != null || stack.size() > 0) {   

213.             while (node != null) {   

214.                 stack.push(node);   

215.                 node = node.getLeft();   

216.             }   

217.             if (stack.size() > 0) {   

218.                 node = stack.pop();   

219.                 visit(node);   

220.                 node = node.getRight();   

221.             }   

222.         }   

223.     }   

224.   

225.     /**  

226.      * @param args  

227.      */  

228.     public static void main(String[] args) {   

229.         BinaryTree tree = new BinaryTree(init());   

230.         System.out.print(" Pre-Order:");   

231.         preorder(tree.getRoot());   

232.         System.out.println();   

233.         System.out.print("  In-Order:");   

234.         inorder(tree.getRoot());   

235.         System.out.println();   

236.         System.out.print("Post-Order:");   

237.         postorder(tree.getRoot());   

238.         System.out.println();   

239.         System.out.print(" Pre-Order:");   

240.         iterativePreorder(tree.getRoot());   

241.         System.out.println();   

242.         System.out.print("Pre-Order2:");   

243.         iterativePreorder2(tree.getRoot());   

244.         System.out.println();   

245.         System.out.print("  In-Order:");   

246.         iterativeInorder(tree.getRoot());   

247.         System.out.println();   

248.         System.out.print(" In-Order2:");   

249.         iterativeInorder2(tree.getRoot());   

250.         System.out.println();   

251.         System.out.print(" Post-Order:");   

252.         iterativePostorder(tree.getRoot());   

253.         System.out.println();   

254.         System.out.print("Post-Order2:");   

255.         iterativePostorder2(tree.getRoot());   

256.         System.out.println();   

257.         System.out.print("Post-Order3:");   

258.         iterativePostorder3(tree.getRoot());   

259.         System.out.println();   

260.         System.out.print("Post-Order4:");   

261.         iterativePostorder4(tree.getRoot());   

262.         System.out.println();   

263.   

264.     }   

265.   

266. }  

 

1. package edu.cumt.jnotnull;   

2.   

3. public class Node {   

4.     private char key;   

5.     private Node left, right;   

6.   

7.     public Node(char key) {   

8.         this(key, null, null);   

9.     }   

10.   

11.     public Node(char key, Node left, Node right) {   

12.         this.key = key;   

13.         this.left = left;   

14.         this.right = right;   

15.     }   

16.   

17.     public char getKey() {   

18.         return key;   

19.     }   

20.   

21.     public void setKey(char key) {   

22.         this.key = key;   

23.     }   

24.   

25.     public Node getLeft() {   

26.         return left;   

27.     }   

28.   

29.     public void setLeft(Node left) {   

30.         this.left = left;   

31.     }   

32.   

33.     public Node getRight() {   

34.         return right;   

35.     }   

36.   

37.     public void setRight(Node right) {   

38.         this.right = right;   

39.     }   

40. }