二叉树的先序、中序、后序三种遍历

原文地址:https://blog.csdn.net/eebaicai/article/details/89788098?utm_medium=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromMachineLearnPai2-1.channel_param&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromMachineLearnPai2-1.channel_param

先来官方的概念:

树的遍历:是指对树中所有结点信息的访问,即依次对树中每个结点的访问一次且仅访问一次。
分为:先序遍历,后序遍历,层次遍历。(普通的树是没有中序遍历的)

这里我们说一下二叉树的遍历:

二叉树的遍历分成三种,按照根节点的访问先后分为:
先序遍历(先根遍历):先访问根节点,然后访问左子树, 最后访问右子树。
中序遍历(中根遍历):先访问左子树,然后访问根节点, 最后访问右子树。
后续遍历(后根遍历):先访问左子树,然后访问右子树, 最后访问根节点

如:
在这里插入图片描述

先序遍历的顺序:ABC (先根节点A,在左子树B,然后右子树C);
中序遍历的顺序:BAC (先左子树B,在根节点A,然后右子树C);
后序遍历的顺序:BCA (先左子树B,在右子树C,然后根节点A)。

在这里插入图片描述
上图二叉树遍历结果:

先序遍历:ABDFCEGHI
中序遍历:BFDACHGIE
后序遍历:FDBHIGECA
  • 1
  • 2
  • 3

第一种分析方法:(此处分析先序遍历)

①:从A根节点开始,根据先序遍历的原则:首先访问根节点A,然后访问它的左子树B, 在访问右子树C,遍历顺序就是A->B->C
②:左子树B 也按照先序遍历的原则来处理, 遍历顺序就是B->D。B的右子树也按照先序遍历的原则,顺序是D->F
,就可以得到A->B->D->F->C
③:右子树C按照先序遍历的原则处理,顺序是C->E,同理C的子树得遍历顺序E->G->H->I
那么, 这棵树先序遍历的结果就是,A->B->D->F->C->E->G->H->I

这是递归思路,根据原则遍历子树,子树没了子节点遍历完,则遍历同深度。

第二种分析方法:(此处分析中序遍历)

在这里插入图片描述

推导计算,两种遍历序列算出第三种序列。
在这里插入图片描述
记住两点:
先序,后序遍历可以确定根节点。
中序遍历可以确定左子树和右子树。

做这种题就是,反复来回这两点
题目分析:

由前序遍历知道,A是根节点。
则根据中序遍历 知道HBDF是左子树 EKCG是右子树的
然后在根据前序遍历 BHFD 知道B是左子树的根节点 ,再根据中序遍历知道H是左子树,DF是右子树,同理F是根,D是左子树。
由此也可推出A的右子树的结构
所有整个树的结构是:
在这里插入图片描述
因此后序遍历是:
HDFBKGCEA
答案是B