一:要遍历的二叉树模型
例子是博主随意创建的二叉树,可自己更改
二:手动构建二叉树模型
1:单个节点结构体的定义
解释:
一个节点应该有值val,还有两个指针指向它的左右孩子。
2:创建节点函数
解释:
此函数创建了一个节点,并且进行了初始化。
3:手动构建二叉树模型
解:
a:根据模型已知:
共六个节点
值为1的节点左孩子为2,右孩子为4
值为2的节点左孩子为3,无右孩子
值为3的节点无孩子
值为4的节点左孩子为5,右孩子为6
值为5 ,6 的节点,无孩子
b:所以BuyNode函数创建了6个节点,再根据a的信息进行left和right的连接,无孩子即为NULL。在BuyNode函数内部已经初始化为NULL,不需要在这里再额外的置空。
三:前序遍历
模型:
前序遍历效果:
解释:
二叉树的前序遍历(Pre-order Traversal)是一种遍历二叉树节点的算法。在前序遍历中,访问节点的顺序是:
简单来说,前序遍历的顺序是:根节点 -> 左子树 -> 右子树。
所以前序遍历的结果是:1 ->2 -> 3 -> 4 -> 5 -> 6
这个过程可以这样理解:
- 访问节点1(根节点)。(1)
- 递归地遍历左子树:访问节点 2,(1 2)然后递归地遍历 2的左子树(访问节点 3)(1 2 3),接着遍历2的右子树(NULL,所以跳过)。
- 递归地遍历右子树:访问节点 4(1 2 3 4),然后递归地遍历 4 的左子树(访问节点 5)(1 2 3 4 5),接着遍历 4 的右子树(访问节点 6)(1 2 3 4 5 6)。
递归实现前序遍历函数:
递归的路线:
(红色代表递,蓝色代表归)
不太清晰,分左右发
左:
右:
可以看出,打印这个步骤是最先的 ,都是在左右子树遍历前。
四:中序遍历
中序遍历效果:
解释:
二叉树的中序遍历(In-order Traversal)是另一种遍历二叉树节点的算法。在中序遍历中,访问节点的顺序是:
简单来说,中序遍历的顺序是:左子树 -> 根节点 -> 右子树。
中序遍历的结果是:3-> 2 ->1 -> 5 -> 4 -> 6
这个过程可以这样理解:
- 递归地遍历左子树:访问节点 2 的左子树,即节点 3。(3)
- 访问节点 2。(3 2)
- 继续递归地遍历 2 的右子树,(这里为空,所以跳过)。
- 回到根节点 1,访问节点1。(3 2 1)
- 递归地遍历右子树:访问节点 4 的左子树,即节点 5(3 2 1 5)
- 访问节点4(3 2 1 5 4)
- 访问节点 4 的右子树,即节点 6(3 2 1 5 4 6)
递归实现中序遍历函数:
递归的路线:
左:
右:
可以看出,打印这个步骤是次先的 ,都是在左子树走完之后
五:后序遍历
模型:
后序遍历效果:
二叉树的后序遍历(Post-order Traversal)是遍历二叉树节点的另一种算法。在后序遍历中,访问节点的顺序是:
简单来说,后序遍历的顺序是:左子树 -> 右子树 -> 根节点。
后序遍历的结果是:3 -> 2-> 5 -> 6 ->4 -> 1
这个过程可以这样理解:
- 递归地遍历左子树:首先访问节点 2 的左子树,即节点 3。(3)
- 继续递归地遍历 2 的右子树,(这里为空,所以跳过)。
- 访问节点 2。(3 2)
- 递归地遍历右子树:首先访问节点 4 的左子树,即节点 5,然后递归地遍历,4 的右子树,即节点 6。(3 2 5 6)
- 访问节点 4。(3 2 5 6 4)
- 最后访问根节点 1。(3 2 5 6 4 1)
递归实现后序遍历函数:
递归的路线:
左:
右:
可以看出,打印这个步骤是最后的 ,都是在左右子树走完之后
总结:
三种遍历二叉树的方法——前序遍历、中序遍历和后序遍历——的主要区别在于访问根节点的时机不同。