树遍历
遍历是访问树中所有节点的过程，也可能打印它们的值。由于所有节点都通过边（链接）连接，因此我们始终从根（头）节点开始。也就是说，我们无法随机访问树中的节点。我们有三种方法可以遍历一棵树 −
中序遍历
前序遍历
后序遍历
通常，我们遍历一棵树是为了在树中搜索或定位给定的元素或键，或者打印它包含的所有值。
中序遍历
在这种遍历方法中，首先访问左子树，然后访问根，最后访问右子树。我们应该始终记住，每个节点本身都可能代表一棵子树。
如果二叉树按顺序遍历，输出将按升序排列键值。
我们从A开始，按顺序遍历后，移动到它的左子树B。B也按顺序遍历。该过程持续进行，直到所有节点都被访问。这棵树按顺序遍历的输出结果为 −
D → B → E → A → F → C → G
算法
直到所有节点都遍历完毕 −
步骤 1 − 递归遍历左子树。 步骤 2 − 访问根节点。 步骤 3 − 递归遍历右子树。
示例
以下是此操作在各种编程语言中的实现 −
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node *leftChild;
struct node *rightChild;
};
struct node *root = NULL;
void insert(int data){
struct node *tempNode = (struct node*) malloc(sizeof(struct node));
struct node *current;
struct node *parent;
tempNode->data = data;
tempNode->leftChild = NULL;
tempNode->rightChild = NULL;
//如果树为空
if(root == NULL) {
root = tempNode;
} else {
current = root;
parent = NULL;
while(1) {
parent = current;
//去树的左边
if(data < parent->data) {
current = current->leftChild;
//插入到左侧
if(current == NULL) {
parent->leftChild = tempNode;
return;
}
}//去树的右边
else {
current = current->rightChild;
//插入到右侧
if(current == NULL) {
parent->rightChild = tempNode;
return;
}
}
}
}
}
void inorder_traversal(struct node* root){
if(root != NULL) {
inorder_traversal(root->leftChild);
printf("%d ",root->data);
inorder_traversal(root->rightChild);
}
}
int main(){
int i;
int array[7] = { 27, 14, 35, 10, 19, 31, 42 };
for(i = 0; i < 7; i++)
insert(array[i]);
printf("中序遍历：");
inorder_traversal(root);
return 0;
}
输出
中序遍历：10 14 19 27 31 35 42
#include <iostream>
struct node {
int data;
struct node *leftChild;
struct node *rightChild;
};
struct node *root = NULL;
void insert(int data){
struct node *tempNode = (struct node*) malloc(sizeof(struct node));
struct node *current;
struct node *parent;
tempNode->data = data;
tempNode->leftChild = NULL;
tempNode->rightChild = NULL;
//如果树为空
if(root == NULL) {
root = tempNode;
} else {
current = root;
parent = NULL;
while(1) {
parent = current;
//去树的左边
if(data < parent->data) {
current = current->leftChild;
//插入到左侧
if(current == NULL) {
parent->leftChild = tempNode;
return;
}
}//去树的右边
else {
current = current->rightChild;
//插入到右侧
if(current == NULL) {
parent->rightChild = tempNode;
return;
}
}
}
}
}
void inorder_traversal(struct node* root){
if(root != NULL) {
inorder_traversal(root->leftChild);
printf("%d ",root->data);
inorder_traversal(root->rightChild);
}
}
int main(){
int i;
int array[7] = { 27, 14, 35, 10, 19, 31, 42 };
for(i = 0; i < 7; i++)
insert(array[i]);
printf("中序遍历：");
inorder_traversal(root);
return 0;
}
输出
中序遍历：10 14 19 27 31 35 42
class Node {
int data;
Node leftChild;
Node rightChild;
public Node(int key) {
data = key;
leftChild = rightChild = null;
}
}
public class TreeDataStructure {
Node root = null;
void inorder_traversal(Node node) {
if(node != null) {
inorder_traversal(node.leftChild);
System.out.print(node.data + " ");
inorder_traversal(node.rightChild);
}
}
public static void main(String args[]) {
TreeDataStructure tree = new TreeDataStructure();
tree.root = new Node(27);
tree.root.leftChild = new Node(12);
tree.root.rightChild = new Node(3);
tree.root.leftChild.leftChild = new Node(44);
tree.root.leftChild.rightChild = new Node(17);
tree.root.rightChild.leftChild = new Node(56);
System.out.println("中序遍历：");
tree.inorder_traversal(tree.root);
}
}
输出
中序遍历： 44 12 17 27 56 3
class Node:
def __init__(self, key):
self.leftChild = None
self.rightChild = None
self.data = key
# 创建一个函数来执行中序树遍历
def InorderTraversal(root):
if root:
InorderTraversal(root.leftChild)
print(root.data)
InorderTraversal(root.rightChild)
# Main class
if __name__ == "__main__":
root = Node(3)
root.leftChild = Node(26)
root.rightChild = Node(42)
root.leftChild.leftChild = Node(54)
root.leftChild.rightChild = Node(65)
root.rightChild.leftChild = Node(12)
# Function call
print("二叉树的中序遍历是")
InorderTraversal(root)
输出
二叉树的中序遍历是 54 26 65 3 12 42
前序遍历
在此遍历方法中，首先访问根节点，然后访问左子树，最后访问右子树。
我们从A开始，按照前序遍历，首先访问A本身，然后移动到其左子树B。B也按前序遍历。该过程一直持续到所有节点都被访问。这棵树的前序遍历的输出为 −
A → B → D → E → C → F → G
算法
直到所有节点都遍历完毕 −
步骤 1 − 访问根节点。 步骤 2 − 递归遍历左子树。 步骤 3 − 递归遍历右子树。
示例
以下是此操作在各种编程语言中的实现 −
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node *leftChild;
struct node *rightChild;
};
struct node *root = NULL;
void insert(int data){
struct node *tempNode = (struct node*) malloc(sizeof(struct node));
struct node *current;
struct node *parent;
tempNode->data = data;
tempNode->leftChild = NULL;
tempNode->rightChild = NULL;
//如果树为空
if(root == NULL) {
root = tempNode;
} else {
current = root;
parent = NULL;
while(1) {
parent = current;
//去树的左边
if(data < parent->data) {
current = current->leftChild;
//插入到左侧
if(current == NULL) {
parent->leftChild = tempNode;
return;
}
}//去树的右边
else {
current = current->rightChild;
//插入到右侧
if(current == NULL) {
parent->rightChild = tempNode;
return;
}
}
}
}
}
void pre_order_traversal(struct node* root){
if(root != NULL) {
printf("%d ",root->data);
pre_order_traversal(root->leftChild);
pre_order_traversal(root->rightChild);
}
}
int main(){
int i;
int array[7] = { 27, 14, 35, 10, 19, 31, 42 };
for(i = 0; i < 7; i++)
insert(array[i]);
printf("前序遍历：");
pre_order_traversal(root);
return 0;
}
输出
前序遍历：27 14 10 19 35 31 42
#include <iostream>
struct node {
int data;
struct node *leftChild;
struct node *rightChild;
};
struct node *root = NULL;
void insert(int data){
struct node *tempNode = (struct node*) malloc(sizeof(struct node));
struct node *current;
struct node *parent;
tempNode->data = data;
tempNode->leftChild = NULL;
tempNode->rightChild = NULL;
//如果树为空
if(root == NULL) {
root = tempNode;
} else {
current = root;
parent = NULL;
while(1) {
parent = current;
//去树的左边
if(data < parent->data) {
current = current->leftChild;
//插入到左侧
if(current == NULL) {
parent->leftChild = tempNode;
return;
}
}//去树的右边
else {
current = current->rightChild;
//插入到右侧
if(current == NULL) {
parent->rightChild = tempNode;
return;
}
}
}
}
}
void pre_order_traversal(struct node* root){
if(root != NULL) {
printf("%d ",root->data);
pre_order_traversal(root->leftChild);
pre_order_traversal(root->rightChild);
}
}
int main(){
int i;
int array[7] = { 27, 14, 35, 10, 19, 31, 42 };
for(i = 0; i < 7; i++)
insert(array[i]);
printf("前序遍历：");
pre_order_traversal(root);
return 0;
}
输出
前序遍历：27 14 10 19 35 31 42
class Node {
int data;
Node leftChild;
Node rightChild;
public Node(int key) {
data = key;
leftChild = rightChild = null;
}
}
public class TreeDataStructure {
Node root = null;
void pre_order_traversal(Node node) {
if(node != null) {
System.out.print(node.data + " ");
pre_order_traversal(node.leftChild);
pre_order_traversal(node.rightChild);
}
}
public static void main(String args[]) {
TreeDataStructure tree = new TreeDataStructure();
tree.root = new Node(27);
tree.root.leftChild = new Node(12);
tree.root.rightChild = new Node(3);
tree.root.leftChild.leftChild = new Node(44);
tree.root.leftChild.rightChild = new Node(17);
tree.root.rightChild.leftChild = new Node(56);
System.out.println("前序遍历：");
tree.pre_order_traversal(tree.root);
}
}
输出
前序遍历： 27 12 44 17 3 56
class Node:
def __init__(self, key):
self.leftChild = None
self.rightChild = None
self.data = key
# 创建一个函数来执行后序树遍历
def PreorderTraversal(root):
if root:
print(root.data)
PreorderTraversal(root.leftChild)
PreorderTraversal(root.rightChild)
# Main class
if __name__ == "__main__":
root = Node(3)
root.leftChild = Node(26)
root.rightChild = Node(42)
root.leftChild.leftChild = Node(54)
root.leftChild.rightChild = Node(65)
root.rightChild.leftChild = Node(12)
print("二叉树的前序遍历是")
PreorderTraversal(root)
输出
二叉树的前序遍历是 3 26 54 65 42 12
后序遍历
在这种遍历方法中，根节点最后被访问，因此得名。我们首先遍历左子树，然后是右子树，最后是根节点。
我们从A开始，按照前序遍历，首先访问左子树B。B也按后序遍历。该过程一直持续到所有节点都被访问。这棵树的后序遍历输出为 −
D → E → B → F → G → C → A
算法
直到所有节点都遍历完毕 −
步骤 1 − 递归遍历左子树。 步骤 2 − 递归遍历右子树。 步骤 3 − 访问根节点。
示例
以下是此操作在各种编程语言中的实现 −
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node *leftChild;
struct node *rightChild;
};
struct node *root = NULL;
void insert(int data){
struct node *tempNode = (struct node*) malloc(sizeof(struct node));
struct node *current;
struct node *parent;
tempNode->data = data;
tempNode->leftChild = NULL;
tempNode->rightChild = NULL;
//如果树为空
if(root == NULL) {
root = tempNode;
} else {
current = root;
parent = NULL;
while(1) {
parent = current;
//去树的左边
if(data < parent->data) {
current = current->leftChild;
//插入到左侧
if(current == NULL) {
parent->leftChild = tempNode;
return;
}
}//去树的右边
else {
current = current->rightChild;
//插入到右侧
if(current == NULL) {
parent->rightChild = tempNode;
return;
}
}
}
}
}
void post_order_traversal(struct node* root){
if(root != NULL) {
post_order_traversal(root->leftChild);
post_order_traversal(root->rightChild);
printf("%d ", root->data);
}
}
int main(){
int i;
int array[7] = { 27, 14, 35, 10, 19, 31, 42 };
for(i = 0; i < 7; i++)
insert(array[i]);
printf("后序遍历：");
post_order_traversal(root);
return 0;
}
输出
后序遍历：10 19 14 31 42 35 27
#include <iostream>
struct node {
int data;
struct node *leftChild;
struct node *rightChild;
};
struct node *root = NULL;
void insert(int data){
struct node *tempNode = (struct node*) malloc(sizeof(struct node));
struct node *current;
struct node *parent;
tempNode->data = data;
tempNode->leftChild = NULL;
tempNode->rightChild = NULL;
//如果树为空
if(root == NULL) {
root = tempNode;
} else {
current = root;
parent = NULL;
while(1) {
parent = current;
//去树的左边
if(data < parent->data) {
current = current->leftChild;
//插入到左侧
if(current == NULL) {
parent->leftChild = tempNode;
return;
}
}//去树的右边
else {
current = current->rightChild;
//插入到右侧
if(current == NULL) {
parent->rightChild = tempNode;
return;
}
}
}
}
}
void post_order_traversal(struct node* root){
if(root != NULL) {
post_order_traversal(root->leftChild);
post_order_traversal(root->rightChild);
printf("%d ", root->data);
}
}
int main(){
int i;
int array[7] = { 27, 14, 35, 10, 19, 31, 42 };
for(i = 0; i < 7; i++)
insert(array[i]);
printf("后序遍历：");
post_order_traversal(root);
return 0;
}
输出
后序遍历：10 19 14 31 42 35 27
class Node {
int data;
Node leftChild;
Node rightChild;
public Node(int key) {
data = key;
leftChild = rightChild = null;
}
}
public class TreeDataStructure {
Node root = null;
void post_order_traversal(Node node) {
if(node != null) {
post_order_traversal(node.leftChild);
post_order_traversal(node.rightChild);
System.out.print(node.data + " ");
}
}
public static void main(String args[]) {
TreeDataStructure tree = new TreeDataStructure();
tree.root = new Node(27);
tree.root.leftChild = new Node(12);
tree.root.rightChild = new Node(3);
tree.root.leftChild.leftChild = new Node(44);
tree.root.leftChild.rightChild = new Node(17);
tree.root.rightChild.leftChild = new Node(56);
System.out.println("后序遍历：");
tree.post_order_traversal(tree.root);
}
}
输出
后序遍历： 44 17 12 56 3 27
class Node:
def __init__(self, key):
self.leftChild = None
self.rightChild = None
self.data = key
# 创建一个函数来执行前序树遍历
def PostorderTraversal(root):
if root:
PostorderTraversal(root.leftChild)
PostorderTraversal(root.rightChild)
print(root.data)
# Main class
if __name__ == "__main__":
root = Node(3)
root.leftChild = Node(26)
root.rightChild = Node(42)
root.leftChild.leftChild = Node(54)
root.leftChild.rightChild = Node(65)
root.rightChild.leftChild = Node(12)
print("二叉树的后序遍历是")
PostorderTraversal(root)
输出
二叉树的后序遍历是 54 65 26 12 42 3
完整实现
现在让我们看看各种编程语言中树遍历的完整实现 −
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node *leftChild;
struct node *rightChild;
};
struct node *root = NULL;
void insert(int data){
struct node *tempNode = (struct node*) malloc(sizeof(struct node));
struct node *current;
struct node *parent;
tempNode->data = data;
tempNode->leftChild = NULL;
tempNode->rightChild = NULL;
//如果树为空
if(root == NULL) {
root = tempNode;
} else {
current = root;
parent = NULL;
while(1) {
parent = current;
//去树的左边
if(data < parent->data) {
current = current->leftChild;
//插入到左侧
if(current == NULL) {
parent->leftChild = tempNode;
return;
}
}//去树的右边
else {
current = current->rightChild;
//插入到右侧
if(current == NULL) {
parent->rightChild = tempNode;
return;
}
}
}
}
}
void pre_order_traversal(struct node* root){
if(root != NULL) {
printf("%d ",root->data);
pre_order_traversal(root->leftChild);
pre_order_traversal(root->rightChild);
}
}
void inorder_traversal(struct node* root){
if(root != NULL) {
inorder_traversal(root->leftChild);
printf("%d ",root->data);
inorder_traversal(root->rightChild);
}
}
void post_order_traversal(struct node* root){
if(root != NULL) {
post_order_traversal(root->leftChild);
post_order_traversal(root->rightChild);
printf("%d ", root->data);
}
}
int main(){
int i;
int array[7] = { 27, 14, 35, 10, 19, 31, 42 };
for(i = 0; i < 7; i++)
insert(array[i]);
printf("前序遍历：");
pre_order_traversal(root);
printf("
中序遍历：");
inorder_traversal(root);
printf("
后序遍历：");
post_order_traversal(root);
return 0;
}
输出
前序遍历：27 14 10 19 35 31 42 中序遍历：10 14 19 27 31 35 42 后序遍历：10 19 14 31 42 35 27
#include <iostream>
struct node {
int data;
struct node *leftChild;
struct node *rightChild;
};
struct node *root = NULL;
void insert(int data){
struct node *tempNode = (struct node*) malloc(sizeof(struct node));
struct node *current;
struct node *parent;
tempNode->data = data;
tempNode->leftChild = NULL;
tempNode->rightChild = NULL;
//如果树为空
if(root == NULL) {
root = tempNode;
} else {
current = root;
parent = NULL;
while(1) {
parent = current;
//去树的左边
if(data < parent->data) {
current = current->leftChild;
//插入到左侧
if(current == NULL) {
parent->leftChild = tempNode;
return;
}
}//去树的右边
else {
current = current->rightChild;
//插入到右侧
if(current == NULL) {
parent->rightChild = tempNode;
return;
}
}
}
}
}
void pre_order_traversal(struct node* root){
if(root != NULL) {
printf("%d ",root->data);
pre_order_traversal(root->leftChild);
pre_order_traversal(root->rightChild);
}
}
void inorder_traversal(struct node* root){
if(root != NULL) {
inorder_traversal(root->leftChild);
printf("%d ",root->data);
inorder_traversal(root->rightChild);
}
}
void post_order_traversal(struct node* root){
if(root != NULL) {
post_order_traversal(root->leftChild);
post_order_traversal(root->rightChild);
printf("%d ", root->data);
}
}
int main(){
int i;
int array[7] = { 27, 14, 35, 10, 19, 31, 42 };
for(i = 0; i < 7; i++)
insert(array[i]);
printf("前序遍历：");
pre_order_traversal(root);
printf("
中序遍历：");
inorder_traversal(root);
printf("
后序遍历：");
post_order_traversal(root);
return 0;
}
输出
前序遍历：27 14 10 19 35 31 42 中序遍历：10 14 19 27 31 35 42 后序遍历：10 19 14 31 42 35 27
class Node {
int data;
Node leftChild;
Node rightChild;
public Node(int key) {
data = key;
leftChild = rightChild = null;
}
}
public class TreeDataStructure {
Node root = null;
void inorder_traversal(Node node) {
if(node != null) {
inorder_traversal(node.leftChild);
System.out.print(node.data + " ");
inorder_traversal(node.rightChild);
}
}
void pre_order_traversal(Node node) {
if(node != null) {
System.out.print(node.data + " ");
pre_order_traversal(node.leftChild);
pre_order_traversal(node.rightChild);
}
}
void post_order_traversal(Node node) {
if(node != null) {
post_order_traversal(node.leftChild);
post_order_traversal(node.rightChild);
System.out.print(node.data + " ");
}
}
public static void main(String args[]) {
TreeDataStructure tree = new TreeDataStructure();
tree.root = new Node(27);
tree.root.leftChild = new Node(12);
tree.root.rightChild = new Node(3);
tree.root.leftChild.leftChild = new Node(44);
tree.root.leftChild.rightChild = new Node(17);
tree.root.rightChild.leftChild = new Node(56);
System.out.println("中序遍历：");
tree.inorder_traversal(tree.root);
System.out.println("
前序遍历：");
tree.pre_order_traversal(tree.root);
System.out.println("
后序遍历：");
tree.post_order_traversal(tree.root);
}
}
输出
中序遍历： 44 12 17 27 56 3 前序遍历： 27 12 44 17 3 56 后序遍历： 44 17 12 56 3 27
class Node:
def __init__(self, key):
self.leftChild = None
self.rightChild = None
self.data = key
# 创建一个函数来执行中序树遍历
def InorderTraversal(root):
if root:
InorderTraversal(root.leftChild)
print(root.data)
InorderTraversal(root.rightChild)
# 创建一个函数来执行前序树遍历
def PostorderTraversal(root):
if root:
PostorderTraversal(root.leftChild)
PostorderTraversal(root.rightChild)
print(root.data)
# 创建一个函数来执行后序树遍历
def PreorderTraversal(root):
if root:
print(root.data)
PreorderTraversal(root.leftChild)
PreorderTraversal(root.rightChild)
# Main class
if __name__ == "__main__":
root = Node(3)
root.leftChild = Node(26)
root.rightChild = Node(42)
root.leftChild.leftChild = Node(54)
root.leftChild.rightChild = Node(65)
root.rightChild.leftChild = Node(12)
# Function call
print("二叉树的中序遍历是")
InorderTraversal(root)
print("
二叉树的前序遍历是")
PreorderTraversal(root)
print("
二叉树的后序遍历是")
PostorderTraversal(root)
输出
二叉树的中序遍历是 54 26 65 3 12 42 二叉树的前序遍历是 3 26 54 65 42 12 二叉树的后序遍历是 54 65 26 12 42 3
