上一节: 数据结构&算法 树
上一节
下一节: 数据结构&算法 二叉搜索树
下一节
数据结构&算法 树遍历
树遍历
遍历是访问树的所有节点并且也可以打印其值的过程。因为所有节点都是通过边（链接）连接的，所以我们总是从根（头）节点开始。也就是说，我们不能随机访问树中的节点。我们使用三种方式遍历树-
中序遍历
前序遍历
后序遍历
通常，我们遍历一棵树以搜索或定位树中的给定项或键，或打印其中包含的所有值。
中序遍历
在这种遍历方法中，首先访问左子树，然后访问根，然后再访问右子树。我们应该永远记住，每个节点本身都可以代表一个子树。
如果按顺序遍历二叉树，则输出将产生升序排序的键值。
我们从A开始，按照顺序遍历，移动到它的左子树B。B也是按顺序遍历的。这个过程一直进行，直到访问了所有节点。这个树的中序遍历的输出将是−
D → B → E → A → F → C → G
算法
Until all nodes are traversed −
Step 1 − Recursively traverse left subtree.
Step 2 − Visit root node.
Step 3 − Recursively traverse right subtree.
前序遍历
在这种遍历方法中，首先访问根节点，然后是左子树，最后是右子树。
我们从A开始，并在进行预遍历之后，首先访问A本身，然后移至其左子树B。B也进行了预遍历。 一直进行到访问所有节点为止。 该树的预遍历的输出将是-
A → B → D → E → C → F → G
算法
Until all nodes are traversed −
Step 1 − Visit root node.
Step 2 − Recursively traverse left subtree.
Step 3 − Recursively traverse right subtree.
后序遍历
在这种遍历方法中，根节点是最后访问的，因此是名称。首先，我们先遍历左侧子树，然后遍历右侧子树，最后遍历根节点。
我们从A开始，然后经过后序遍历，首先访问左子树B。B也经过后序遍历。 一直进行到访问所有节点为止。 该树的后遍历的输出将是-
D → E → B → F → G → C → A
算法
Until all nodes are traversed −
Step 1 − Recursively traverse left subtree.
Step 2 − Recursively traverse right subtree.
Step 3 − Visit root node.
示例
现在，我们将在这里使用以下二进制树查看C编程语言中树遍历的实现-
#include
#include
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;
}
}
}
}
}
struct node* search(int data) {
struct node *current = root;
printf("Visiting elements: ");
while(current->data != data) {
if(current != NULL)
printf("%d ",current->data);
//go to left tree
if(current->data > data) {
current = current->leftChild;
}
//else go to right tree
else {
current = current->rightChild;
}
//not found
if(current == NULL) {
return NULL;
}
}
return current;
}
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]);
i = 31;
struct node * temp = search(i);
if(temp != NULL) {
printf("[%d] Element found.", temp->data);
printf("\n");
}else {
printf("[ x ] Element not found (%d).\n", i);
}
i = 15;
temp = search(i);
if(temp != NULL) {
printf("[%d] Element found.", temp->data);
printf("\n");
}else {
printf("[ x ] Element not found (%d).\n", i);
}
printf("\nPreorder traversal: ");
pre_order_traversal(root);
printf("\nInorder traversal: ");
inorder_traversal(root);
printf("\nPost order traversal: ");
post_order_traversal(root);
return 0;
}
尝试一下
如果我们编译并运行上述程序，它将产生以下结果-
Visiting elements: 27 35 [31] Element found.
Visiting elements: 27 14 19 [ x ] Element not found (15).
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
上一节: 数据结构&算法 树
上一节
下一节: 数据结构&算法 二叉搜索树
下一节
查看笔记 分享笔记
笔记内容：
称呼：
Email：
站点：
分享笔记 重置
分类导航
前端
Ajax 教程
Angular 教程
Aurelia 教程
Bootstrap 教程
ChartJS 教程
CSS 教程
ES6 教程
FontAwesome 教程
HTML 教程
HTML 字符集 教程
HTML 游戏 教程
JavaScript 教程
jQuery 教程
Less 教程
React 教程
Sass 教程
Stylus 教程
TypeScript 教程
Unity 教程
Vue.js 教程
WebAssembly 教程
XAML 教程
颜色 教程
服务端
C# 教程
C++ 教程
COBOL 教程
C语言 教程
Fortran 教程
Go 教程
Groovy 教程
Java 教程
JSP 教程
JVM 教程
Kotlin 教程
Lisp 教程
Lua 教程
Node.js 教程
Pascal 教程
Perl 教程
PHP 教程
Python 教程
Python 3 教程
Ruby 教程
Rust 教程
Scala 教程
Spring 教程
Spring Boot 教程
Spring Cloud 教程
VB.Net 教程
移动端
Android 教程
IOS 教程
Objective-C 教程
React Native 教程
Swift 教程
小程序 教程
数据库
Access 教程
DB2 教程
Mariadb 教程
Memcached 教程
MongoDB 教程
MySQL 教程
Neo4j 教程
PL/SQL 教程
PostgreSQL 教程
Redis 教程
SQL 教程
SQL Server 教程
SQLite 教程
T-SQL 教程
数据格式
Jackson 教程
JSON 教程
SVG 教程
XML 教程
开发工具
ActiveMQ 教程
Ant 教程
Apache HttpClient 教程
Apache POI PPT 教程
AWS 教程
Docker 教程
ElasticSearch 教程
ExpressJS 教程
GIT 教程
GitLab 教程
Google Maps 教程
Gradle 教程
Java NIO 教程
JavaFX 教程
JavaMail 教程
JDBC 教程
jMeter 教程
JPA 教程
jsoup 教程
Junit 教程
KoaJS 教程
Kubernetes 教程
Log4j 教程
Logstash 教程
Lucene 教程
Makefile 教程
Maven 教程
RESTful 教程
Sed 教程
SEO 教程
Servlet 教程
SLF4J 教程
Socket.IO 教程
Struts 教程
SVN 教程
TestNG 教程
UML 教程
UNIX / LINUX 教程
WebSocket 教程
WPF 教程
xStream 教程
区块链 教程
数据处理
Flink 教程
Flume 教程
Hadoop 教程
Hbase 教程
Hive 教程
Kafka 教程
Kibana 教程
MapReduce 教程
MATLAB 教程
MyBatis 教程
Pig 教程
R语言 教程
Solr 教程
Spark 教程
Storm 教程
Zookeeper 教程
大数据分析 教程
数据仓库 教程
数据挖掘 教程
计算机基础
HTTP 教程
IPv4 教程
IPv6 教程
Ubantu 教程
WebServices 教程
嵌入式系统 教程
操作系统 教程
数据结构和算法 教程
汇编语言 教程
物联网 教程
电子电路基础 教程
编译器设计 教程
网站开发 教程
计算机 教程
计算机基础 教程
计算机网络 教程
设计模式 教程
AI
CNTK 教程
Keras 教程
PyTorch 教程
TensorFlow 教程
人工智能 教程
机器学习 教程
Python 技术
Django 教程
Flask 教程
NumPy 教程
Pandas 教程
Pillow 教程
PyGTK 教程
PyQt5 教程
PySpark 教程
pytest 教程
Python -数据科学 教程
Python MySQL 教程
Python 取证 教程
Python 数据结构 教程
Python 文本处理 教程
Python 网络编程 教程
Python 网页抓取 教程
Python 设计模式 教程
RxPY 教程
SciPy 教程
Seaborn 教程
SymPy 教程
wxPython 教程
框架
Laravel 教程
Web 图标Icon 教程
Web2py 教程
WebGL 教程
WebRTC 教程
WordPress 教程
Yii 教程
Zend Framework 教程
SAP
Crystal Reports 教程