一招吃透C语言二叉树的遍历？二叉树的递归遍历与非递归遍历

大家好，欢迎来到IT知识分享网。

前言

上一章节主要讲解的是C语言哈希表，不清楚的可以回过头去复习一下。

本章节主要讲解的C语言描述的二叉树的存储和遍历。

二叉树

在计算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。而二叉搜索树和二叉堆在后续章节会介绍。

二叉树有五种基本形态

• (1).空二叉树；
• (2).只有一个根结点的二叉树；
• (3).只有左子树；
• (4).只有右子树；
• (5).完全二叉树；

注意：尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形.

二叉树相关概念

• 树的结点：包含一个数据元素及若干指向子树的分支；
• 孩子结点：结点的子树的根称为该结点的孩子；
• 双亲结点：B 结点是A 结点的孩子，则A结点是B 结点的双亲；
• 兄弟结点：同一双亲的孩子结点； 堂兄结点：同一层上结点；
• 祖先结点: 从根到该结点的所经分支上的所有结点
• 子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙
• 结点层：根结点的层定义为1；根的孩子为第二层结点，依此类推；
• 树的深度：树中最大的结点层
• 结点的度：结点子树的个数
• 树的度： 树中最大的结点度。
• 叶子结点：也叫终端结点，是度为 0 的结点；

分枝结点：

• 度不为0的结点；
• 有序树：子树有序的树，如：家族树；
• 无序树：不考虑子树的顺序；

二叉树遍历

遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。主要有以下四种遍历方式:

• 先序遍历
• 中序遍历
• 后序遍历
• 层次遍历

ps： 层次访问，通常用 队列 来做。访问根，访问子女，再访问子女的子女（越往后的层次越低）（两个子女的级别相同），这里不做分析讨论

二叉树存储和实现代码

1.创建二叉树结点结构体，以及创建节点函数。

2.插入节点，因为做的无规律二叉树，故手动连接。

3.递归法遍历二叉树。

每个结点都需要按照相应的规则去做遍历，故递归实现 ，代码很简单，原理自我回味下。

4.非递归法

主要采用栈的方式去记录走过的节点，然后出栈回退去实现，具体原理不多说，详细讲解可参见数据结构视频专栏。

先序遍历非递归法

中序遍历非递归法

后序遍历非递归法

测试代码

尾言

本栏目作业:写出一下二叉树的三种遍历结果。

有些人在激烈竞争的汹涛骇浪中被卷走，从此一蹶不振;有些人却迎着风口、踏上浪尖，上了岸，他们成功了。因为他们多了一份坚持。风口浪尖对于他们来说不是绊脚石，而是垫高自己的基石。