网络知识 娱乐 二叉树 (前序遍历、中序遍历、后序遍历)及常见题目解析

二叉树 (前序遍历、中序遍历、后序遍历)及常见题目解析

一、遍历顺序

(1)先(根)序遍历(根左右)

(2)中(根)序遍历(左根右)

(3)后(根)序遍历(左右根)

二、详细步骤

以下图所示二叉树为例进行,先、中、后序遍历;

(1)先序的遍历(根、左、右)。

        由遍历的先后顺序可知,所以先根结点A,然后左子树根结点B,接下来左D,接下来H;接着B节点的右E,接下来I;然后根结点A的右子树根结点C,接着根结点C的左节点F,F的左子树J,接着右节点K,接着根节点C的右子树G;

结果:A,B,D,H,E,I,C,F,J,K,G

(2)中序的遍历(左,根,右)。

        因为遍历先左,所以根节点先不考虑;直接看左子树D,H然后根节点B;然后右子树E,I,左子树完了之后再根节点A,接着右子树J,K,F,G,C;

结果:D,H,B,E,I,A,J,F,K,C,G

(3)后序的遍历(左,右,根)。

        因为遍历先左右孩子,然后再根;因此从二叉树的叶子向根遍历(从下往上);同理:

结果:H,D,I,E,B,J,K,F,G,C,A

三、相关题目

 

 由题目可做二叉树如下图:

因此后序遍历结果:g,d,b,e,h,f,c,a;故结果选B

         由题目选项可知本题考点是:先、中、后序的遍历结果;又因进一步考的是遍历顺序的最后一个节点;因此我们参照先、中、序的顺序,a.先序遍历(根左右)b.中序遍历(左根右)c.后序遍历(左右根);

         因此我们从遍历的顺序知:先序和中序的末尾都为右节点;因此选C