使用递归和非递归算法遍历二进制搜索树

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

使用递归和非递归来遍历二叉搜索树

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. 使用非递归算法执行顺序，中间顺序和后顺序遍历:

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-267451-1.html