- 数据结构与算法
- DSA - 主页
- DSA - 概述
- DSA - 环境设置
- 数据结构
- DSA - 数据结构基础知识
- DSA - 数据结构和类型
- DSA - 数组数据结构
- 链表
- DSA - 链表基础知识
- DSA - 双向链表
- DSA - 循环链表
- 堆栈和队列
- DSA - 堆栈
- DSA - 表达式解析
- DSA-队列
- 图数据结构
- DSA - 图数据结构
- DSA-深度优先遍历
- DSA-广度优先遍历
- DSA——生成树
- 树数据结构
- DSA - 树数据结构
- DSA - 树遍历
- DSA - 二叉搜索树
- DSA - AVL 树
- DSA - 红黑树
- DSA - B 树
- DSA - B+ 树
- DSA - 八字树
- DSA - 尝试
- DSA-堆
- 递归
- DSA - 递归基础知识
- DSA - 河内塔
- DSA - 斐波那契数列
- DSA 有用资源
- DSA - 问题与解答
- DSA - 快速指南
- DSA - 有用的资源
- DSA - 讨论
数据结构与算法-树遍历
遍历是访问树的所有节点并也可以打印它们的值的过程。因为，所有节点都通过边（链接）连接，我们总是从根（头）节点开始。也就是说，我们不能随机访问树中的节点。我们使用三种方法来遍历树 -
中序遍历
预购遍历
后序遍历
通常，我们遍历一棵树来搜索或定位树中的给定项目或键，或者打印它包含的所有值。
中序遍历
在这种遍历方法中，首先访问左子树，然后访问根，最后访问右子树。我们应该永远记住，每个节点可能代表一个子树本身。
如果按顺序遍历二叉树，输出将产生按升序排序的键值。
我们从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 tree is empty
if(root == NULL) {
root = tempNode;
} else {
current = root;
parent = NULL;
while(1) {
parent = current;
//go to left of the tree
if(data < parent->data) {
current = current->leftChild;
//insert to the left
if(current == NULL) {
parent->leftChild = tempNode;
return;
}
}//go to right of the tree
else {
current = current->rightChild;
//insert to the right
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("\nInorder traversal: ");
inorder_traversal(root);
return 0;
}
输出
Inorder traversal: 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 tree is empty
if(root == NULL) {
root = tempNode;
} else {
current = root;
parent = NULL;
while(1) {
parent = current;
//go to left of the tree
if(data < parent->data) {
current = current->leftChild;
//insert to the left
if(current == NULL) {
parent->leftChild = tempNode;
return;
}
}//go to right of the tree
else {
current = current->rightChild;
//insert to the right
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("\nInorder traversal: ");
inorder_traversal(root);
return 0;
}
输出
Inorder traversal: 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("\nInorder traversal: ");
tree.inorder_traversal(tree.root);
}
}
输出
Inorder traversal: 44 12 17 27 56 3
class Node:
def __init__(self, key):
self.leftChild = None
self.rightChild = None
self.data = key
# Create a function to perform inorder tree traversal
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("\nInorder traversal of binary tree is")
InorderTraversal(root)
输出
Inorder traversal of binary tree is 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 tree is empty
if(root == NULL) {
root = tempNode;
} else {
current = root;
parent = NULL;
while(1) {
parent = current;
//go to left of the tree
if(data < parent->data) {
current = current->leftChild;
//insert to the left
if(current == NULL) {
parent->leftChild = tempNode;
return;
}
}//go to right of the tree
else {
current = current->rightChild;
//insert to the right
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("\nPreorder traversal: ");
pre_order_traversal(root);
return 0;
}
输出
Preorder traversal: 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 tree is empty
if(root == NULL) {
root = tempNode;
} else {
current = root;
parent = NULL;
while(1) {
parent = current;
//go to left of the tree
if(data < parent->data) {
current = current->leftChild;
//insert to the left
if(current == NULL) {
parent->leftChild = tempNode;
return;
}
}//go to right of the tree
else {
current = current->rightChild;
//insert to the right
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("\nPreorder traversal: ");
pre_order_traversal(root);
return 0;
}
输出
Preorder traversal: 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("\nPreorder traversal: ");
tree.pre_order_traversal(tree.root);
}
}
输出
Preorder traversal: 27 12 44 17 3 56
class Node:
def __init__(self, key):
self.leftChild = None
self.rightChild = None
self.data = key
# Create a function to perform postorder tree traversal
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("\nPreorder traversal of binary tree is")
PreorderTraversal(root)
输出
Preorder traversal of binary tree is 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 tree is empty
if(root == NULL) {
root = tempNode;
} else {
current = root;
parent = NULL;
while(1) {
parent = current;
//go to left of the tree
if(data < parent->data) {
current = current->leftChild;
//insert to the left
if(current == NULL) {
parent->leftChild = tempNode;
return;
}
}//go to right of the tree
else {
current = current->rightChild;
//insert to the right
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("\nPost order traversal: ");
post_order_traversal(root);
return 0;
}
输出
Post order traversal: 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 tree is empty
if(root == NULL) {
root = tempNode;
} else {
current = root;
parent = NULL;
while(1) {
parent = current;
//go to left of the tree
if(data < parent->data) {
current = current->leftChild;
//insert to the left
if(current == NULL) {
parent->leftChild = tempNode;
return;
}
}//go to right of the tree
else {
current = current->rightChild;
//insert to the right
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("\nPost order traversal: ");
post_order_traversal(root);
return 0;
}
输出
Post order traversal: 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("\nPost order traversal: ");
tree.post_order_traversal(tree.root);
}
}
输出
Post order traversal: 44 17 12 56 3 27
class Node:
def __init__(self, key):
self.leftChild = None
self.rightChild = None
self.data = key
# Create a function to perform preorder tree traversal
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("\nPostorder traversal of binary tree is")
PostorderTraversal(root)
输出
Postorder traversal of binary tree is 54 65 26 12 42 3
查看树遍历的C实现请点击这里
执行
遍历是访问树的所有节点并也可以打印它们的值的过程。因为，所有节点都通过边（链接）连接，我们总是从根（头）节点开始。也就是说，我们不能随机访问树中的节点。我们使用三种方法来遍历树 -
中序遍历
预购遍历
后序遍历
现在我们将使用以下二叉树来了解 C 编程语言中树遍历的实现 -
例子
以下是此操作在各种编程语言中的实现 -
#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 tree is empty
if(root == NULL) {
root = tempNode;
} else {
current = root;
parent = NULL;
while(1) {
parent = current;
//go to left of the tree
if(data < parent->data) {
current = current->leftChild;
//insert to the left
if(current == NULL) {
parent->leftChild = tempNode;
return;
}
}//go to right of the tree
else {
current = current->rightChild;
//insert to the right
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("\nPreorder traversal: ");
pre_order_traversal(root);
printf("\nInorder traversal: ");
inorder_traversal(root);
printf("\nPost order traversal: ");
post_order_traversal(root);
return 0;
}
输出
Preorder traversal: 27 14 10 19 35 31 42 Inorder traversal: 10 14 19 27 31 35 42 Post order traversal: 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 tree is empty
if(root == NULL) {
root = tempNode;
} else {
current = root;
parent = NULL;
while(1) {
parent = current;
//go to left of the tree
if(data < parent->data) {
current = current->leftChild;
//insert to the left
if(current == NULL) {
parent->leftChild = tempNode;
return;
}
}//go to right of the tree
else {
current = current->rightChild;
//insert to the right
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("\nPreorder traversal: ");
pre_order_traversal(root);
printf("\nInorder traversal: ");
inorder_traversal(root);
printf("\nPost order traversal: ");
post_order_traversal(root);
return 0;
}
输出
Preorder traversal: 27 14 10 19 35 31 42 Inorder traversal: 10 14 19 27 31 35 42 Post order traversal: 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("\nInorder traversal: ");
tree.inorder_traversal(tree.root);
System.out.println("\nPreorder traversal: ");
tree.pre_order_traversal(tree.root);
System.out.println("\nPost order traversal: ");
tree.post_order_traversal(tree.root);
}
}
输出
Inorder traversal: 44 12 17 27 56 3 Preorder traversal: 27 12 44 17 3 56 Post order traversal: 44 17 12 56 3 27
class Node:
def __init__(self, key):
self.leftChild = None
self.rightChild = None
self.data = key
# Create a function to perform inorder tree traversal
def InorderTraversal(root):
if root:
InorderTraversal(root.leftChild)
print(root.data)
InorderTraversal(root.rightChild)
# Create a function to perform preorder tree traversal
def PostorderTraversal(root):
if root:
PostorderTraversal(root.leftChild)
PostorderTraversal(root.rightChild)
print(root.data)
# Create a function to perform postorder tree traversal
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("\nInorder traversal of binary tree is")
InorderTraversal(root)
print("\nPreorder traversal of binary tree is")
PreorderTraversal(root)
print("\nPostorder traversal of binary tree is")
PostorderTraversal(root)
输出
Inorder traversal of binary tree is 54 26 65 3 12 42 Preorder traversal of binary tree is 3 26 54 65 42 12 Postorder traversal of binary tree is 54 65 26 12 42 3