教育改变生活
标题:
【数据结构】二叉树先序遍历（递归与非递归）
[打印本页]
作者:
wander
时间:
2023-9-5 15:56
标题:
【数据结构】二叉树先序遍历（递归与非递归）
本帖最后由 wander 于 2023-9-5 16:03 编辑
二叉树先序遍历的实现思想是：
访问根节点；
访问当前节点的左子树；
若当前节点无左子树，则访问当前节点的右子树；
图 1 二叉树
以图 1 为例，采用先序遍历的思想遍历该二叉树的过程为：
访问该二叉树的根节点，找到 1；
访问节点 1 的左子树，找到节点 2；
访问节点 2 的左子树，找到节点 4；
由于访问节点 4 左子树失败，且也没有右子树，因此以节点 4 为根节点的子树遍历完成。但节点 2 还没有遍历其右子树，因此现在开始遍历，即访问节点 5；
由于节点 5 无左右子树，因此节点 5 遍历完成，并且由此以节点 2 为根节点的子树也遍历完成。现在回到节点 1 ，并开始遍历该节点的右子树，即访问节点 3；
访问节点 3 左子树，找到节点 6；
由于节点 6 无左右子树，因此节点 6 遍历完成，回到节点 3 并遍历其右子树，找到节点 7；
节点 7 无左右子树，因此以节点 3 为根节点的子树遍历完成，同时回归节点 1。由于节点 1 的左右子树全部遍历完成，因此整个二叉树遍历完成；
因此，图 1 中二叉树采用先序遍历得到的序列为：
1 2 4 5 3 6 7
欢迎光临 教育改变生活 (http://bbs.goldoar.com/)
Powered by Discuz! X3.2
