二叉树的遍历 (前序、中序、后序)

用户头像
申屠鹏会
关注
发布于: 2020 年 08 月 17 日

树的定义本身就是递归的,因此树的基本操作用递归是很容易实现,代码也很美观,下面总结了二叉树的三种遍历方式,并用Golang进行了实现。



定义



二叉树的遍历就是按照某条搜索路径访问二叉树的每一个节点,且每个节点只访问一次。





图1 二叉树如图1所示,如果限制先左后右遍历,则有三种遍历方案,按照根的访问顺序不同,有:

  • DLR:前序遍历

  • LDR:中序遍历

  • LRD:后序遍历



算法



图2 二叉树用例

节点定义统一为



type Node struct {
value string
left *Node
right *Node
}




前序遍历



访问根,然后遍历左子树,左子树为空或已遍历才可以遍历右子树。



结合图2所示



  1. 先访问根结点A,然后访问A的左子树BDE;

  2. 对于左子树BCD而言,先访问根B,然后再访问左子树D;

  3. 遍历D的左子树,发现为空,于是返回,遍历D的右子树,也为空,于是返回到B;

  4. 访问B的右子树E,同理,E的左右子树都为空,返回到最初的根结点A,开始访问A的右子树;

  5. 访问节点C,再访问C的左子树,节点为F;

  6. 再访问F的左右子树,结果为G,然后返回到C;

  7. 访问C的右子树,发现为空,至此,遍历结束。



最后的结果为:ABDECFG

用递归的写法为:



func preOrder(root *Node) {
if root == nil {
return
}
fmt.Println(root.value)
preOrder(root.left)
preOrder(root.right)
}




中序遍历



中序遍历左子树,左子树为空或已遍历才可以访问根,中序遍历右子树



结合图2所示



  1. 中序遍历A的左子树BDE,对于BDE来说,再遍历B的左子树D,D的左右子树为空,所以返回D;

  2. 访问B,接着访问B的右子树E,E的左右子树都为空,则返回E;

  3. 至此,A的左子树访问完毕,则访问根结点A,接着访问A的右子树CFG;

  4. 先访问C的左子树F,F的左子树为空,则访问根结点F,再访问F的右子树G;

  5. G的左右子树都为空,则返回G;

  6. C的左子树遍历完毕,返回C,再访问C的右子树,为空,则遍历结束。



最后返回结果为:DBEAFGC

用递归实现为:



func inOrder(root *Node) {
if root == nil{
return
}
inOrder(root.left)
fmt.Println(root.value)
inOrder(root.right)
}




###后序遍历



后序遍历左子树,后序遍历右子树,左右子树为空或已遍历才可以访问根



结合图2所示



  1. 先遍历A的左子树BDE,对于BDE而言先遍历B的左子树D;

  2. D的左右子树为空,返回D,再遍历B的右子树E;

  3. E的左右子树为空,返回E,再访问根结点B,至此,BDE遍历结束;

  4. 再遍历A的右子树;

  5. 先遍历C的左子树,F的左子树为空,则遍历F的右子树G,G的左右子树为空,则返回G;

  6. 再访问F,接着遍历C的右子树,为空,于是访问C;

  7. 最后访问根结点A,至此,遍历结束。



最后返回结果为:DEBGFCA

用递归实现为:



func posOrder(root *Node) {
if root == nil{
return
}
posOrder(root.left)
posOrder(root.right)
fmt.Println(root.value)
}



发布于: 2020 年 08 月 17 日 阅读数: 41
用户头像

申屠鹏会

关注

enjoy~ 2018.11.08 加入

https://xabc.site

评论

发布
暂无评论
二叉树的遍历(前序、中序、后序)