# 树的遍历

Posted by icoding168 on 2020-03-25 01:23:11

## 概念

• 前序遍历：根结点 ---> 左子树 ---> 右子树
• 中序遍历：左子树---> 根结点 ---> 右子树
• 后序遍历：左子树 ---> 右子树 ---> 根结点

#### Pre-order, NLR

1. Access the data part of the current node (in the figure: position red).
2. Traverse the left subtree by recursively calling the pre-order function.
3. Traverse the right subtree by recursively calling the pre-order function.

The pre-order traversal is a topologically sorted one, because a parent node is processed before any of its child nodes is done.

#### In-order, LNR

1. Traverse the left subtree by recursively calling the in-order function.
2. Access the data part of the current node (in the figure: position green).
3. Traverse the right subtree by recursively calling the in-order function.

In a binary search tree ordered such that in each node the key is greater than all keys in its left subtree and less than all keys in its right subtree, in-order traversal retrieves the keys in ascending sorted order.[6]

#### Reverse in-order, RNL

1. Traverse the right subtree by recursively calling the reverse in-order function.
2. Access the data part of the current node.
3. Traverse the left subtree by recursively calling the reverse in-order function.

In a binary search tree, reverse in-order traversal retrieves the keys in descending sorted order.

#### Post-order, LRN

1. Traverse the left subtree by recursively calling the post-order function.
2. Traverse the right subtree by recursively calling the post-order function.
3. Access the data part of the current node (in the figure: position blue).

## 代码

``````import java.util.Arrays;

public class TreeTraversals {

public static void main(String[] args) {
int[] a = new int[]{1, 2, 3, 4, 5};

BinaryTree tree = new BinaryTree();
tree.root = new Node(a[0]);
tree.root.left = new Node(a[1]);
tree.root.right = new Node(a[2]);
tree.root.left.left = new Node(a[3]);
tree.root.left.right = new Node(a[4]);

System.out.println("原数组：" + Arrays.toString(a));

System.out.println("\n前序遍历：");
tree.printPreorder(tree.root);

System.out.println("\n中序遍历：");
tree.printInorder(tree.root);

System.out.println("\n后序遍历：");
tree.printPostorder(tree.root);

System.out.println("\n层次遍历：");
tree.printLevelOrder();
}

}

class Node {
int key;
Node left, right;

public Node(int item) {
key = item;
left = right = null;
}
}

class BinaryTree {

Node root;

BinaryTree() {
root = null;
}

void printPostorder(Node node) {
if (node == null) {
return;
}

printPostorder(node.left);

printPostorder(node.right);

System.out.print(node.key + " ");
}

void printInorder(Node node) {
if (node == null) {
return;
}

printInorder(node.left);

System.out.print(node.key + " ");

printInorder(node.right);
}

void printPreorder(Node node) {
if (node == null) {
return;
}

System.out.print(node.key + " ");

printPreorder(node.left);

printPreorder(node.right);
}

void printLevelOrder() {
int h = height(root);
int i;
for (i = 1; i <= h; i++) {
printGivenLevel(root, i);
}

}

int height(Node root) {
if (root == null) {
return 0;
} else {
int lheight = height(root.left);
int rheight = height(root.right);

if (lheight > rheight) {
return (lheight + 1);
} else {
return (rheight + 1);
}
}
}

void printGivenLevel(Node root, int level) {
if (root == null) {
return;
}

if (level == 1) {
System.out.print(root.key + " ");
} else if (level > 1) {
printGivenLevel(root.left, level - 1);
printGivenLevel(root.right, level - 1);
}
}

}``````