使用递归和非递归算法实现二叉搜索树的遍历

【使用递归和非递归实现二叉搜索树的遍历】

　　 使用递归和非递归实现二叉搜索树的遍历

1.遍历的基本概念：所谓遍历(Traversal)，是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础。

2.使用递归算法分别执行先序，中序，后序遍历:

 1 public class BinaryTree {
 2     // 初始化二叉树
 3     public Node init() {
 4         Node I = new Node(8, null, null);
 5         Node H = new Node(4, null, null);
 6         Node G = new Node(2, null, null);
 7         Node F = new Node(7, null, I);
 8         Node E = new Node(5, H, null);
 9         Node D = new Node(1, null, G);
10         Node C = new Node(9, F, null);
11         Node B = new Node(3, D, E);
12         Node A = new Node(6, B, C);
13         // 返回根节点
14         return A;
15     }
16 
17     // 访问节点
18     public void printNode(Node node) {
19         System.out.println(node.getData());
20     }
21 
22     // 先序遍历
23     public void theFirstTraversal(Node root) {
24         printNode(root);
25         // 使用递归遍历左孩子
26         if (root.getLeftNode() != null) {
27             theFirstTraversal(root.getLeftNode());
28         }
29         // 使用递归遍历右孩子
30         if (root.getRightNode() != null) {
31             theFirstTraversal(root.getRightNode());
32         }
33     }
34 
35     // 中序遍历
36     public void theInOrderTraversal(Node root) {
37         // 递归遍历左孩子
38         if (root.getLeftNode() != null) {
39             theInOrderTraversal(root.getLeftNode());
40         }
41         printNode(root);
42         // 遍历右孩子
43         if (root.getRightNode() != null) {
44             theInOrderTraversal(root.getRightNode());
45         }
46     }
47 
48     // 后序遍历
49     public void thePostOrderTraveral(Node root) {
50         // 递归遍历左孩子
51         if (root.getLeftNode() != null) {
52             theInOrderTraversal(root.getLeftNode());
53         }
54 
55         // 遍历右孩子
56         if (root.getRightNode() != null) {
57             theInOrderTraversal(root.getRightNode());
58         }
59         printNode(root);
60 
61     }
62 
63     public static void main(String[] args) {
64         BinaryTree t = new BinaryTree();
65         Node node = t.init();
66         System.out.println("先序遍历:");
67         t.theFirstTraversal(node);
68         System.out.println("中序遍历:");
69         t.theInOrderTraversal(node);
70         System.out.println("后序遍历:");
71         t.thePostOrderTraveral(node);
72 
73     }
74 
75 }

2.使用非递归算法分别执行先序，中序，后序遍历：

 1 public class BinaryTree1 {
 2     // 初始化二叉树
 3     public Node init() {
 4         Node I = new Node(8, null, null);
 5         Node H = new Node(4, null, null);
 6         Node G = new Node(2, null, null);
 7         Node F = new Node(7, null, I);
 8         Node E = new Node(5, H, null);
 9         Node D = new Node(1, null, G);
10         Node C = new Node(9, F, null);
11         Node B = new Node(3, D, E);
12         Node A = new Node(6, B, C);
13         // 返回根节点
14         return A;
15     }
16 
17     public void printNode(Node node) {
18         System.out.print(node.getData());
19     }
20 
21     public void theFirstTraversal_Stack(Node root) { // 先序遍历
22     Stack<Node> stack = new Stack<Node>();
23         Node node = root;
24         while (node != null || stack.size() > 0) { // 将所有左孩子压栈
25             if (node != null) { // 压栈之前先访问
26                 printNode(node);
27             
28                 stack.push(node);
29                 
30                 node = node.getLeftNode();
31                 
32             } else {
33                 node = stack.pop();
34                 
35                 node = node.getRightNode();
36                 
37             }
38         }
39     }
40 
41     public void theInOrderTraversal_Stack(Node root) { // 中序遍历
42         Stack<Node> stack = new Stack<Node>();
43         Node node = root;
44         while (node != null || stack.size() > 0) {
45             if (node != null) {
46                 stack.push(node); // 直接压栈
47                 node = node.getLeftNode();
48             } else {
49                 node = stack.pop(); // 出栈并访问
50                 printNode(node);
51                 node = node.getRightNode();
52             }
53         }
54     }
55 
56     public void thePostOrderTraversal_Stack(Node root) { // 后序遍历
57         Stack<Node> stack = new Stack<Node>();
58         Stack<Node> output = new Stack<Node>();// 构造一个中间栈来存储逆后序遍历的结果
59         Node node = root;
60         while (node != null || stack.size() > 0) {
61             if (node != null) {
62                 output.push(node);
63                 
64                 stack.push(node);
65                 
66                 node = node.getRightNode();
67                 
68             } else {
69                 node = stack.pop();
70                 node = node.getLeftNode();
71             }
72         }
73         System.out.println(output.size());
74         while (output.size() > 0) {
75 
76             printNode(output.pop());
77         }
78     }
79 
80     public static void main(String[] args) {
81         BinaryTree1 tree = new BinaryTree1();
82         Node root = tree.init();
83         System.out.println("先序遍历");
84         tree.theFirstTraversal_Stack(root);
85         System.out.println("");
86         System.out.println("中序遍历");
87         tree.theInOrderTraversal_Stack(root);
88         System.out.println("");
89         System.out.println("后序遍历");
90         tree.thePostOrderTraversal_Stack(root);
91 
92     }
93 }