树2，用递归实现树的三种遍历

2018-07-12  本文已影响0人  小碧小琳

面试时提到的树，大部分是二叉树。每个结点最多只能有两个子结点。
在二叉树中，最重要的操作就是遍历，即按照某一顺序访问树中的所有结点。通常树有如下几种遍历方式：

前序遍历就是根节点在前面，中序遍历就是根节点在中间，后序遍历就是根节点在后面。

要很好地理解上面三种遍历方式，一定要深刻的理解这句话：我们能够把一个二叉树的任何子节点当成二叉树本身，一个子节点不单单只是一个节点，这是一个二叉树类实例，我们对一个节点进行操作，就是在对一个树进行操作。

理解这句话以后，就容易理解三种遍历是如何进行的了。
前序遍历访问一个节点，就是对这个节点为根的树，进行前序遍历。

如图2.5

一、三种遍历方法

1.1、前序遍历：

先访问根节点，再访问左子节点，最后访问右子节点
步骤1：
先访问以10为根节点的树，此时先访问根节点，于是会输出10。

步骤2：
再访问“大树”的左子节点6，一个节点就是一个树，访问左子节点6，就相当于用前序遍历访问左子树。于是对于左子树，先访问根节点6，于是会输出6。

步骤3：再访问左子树的左子节点4，此时是对以4为根节点的树，进行前序遍历。先访问根节点4，于是输出4。

步骤4：最左边的以4为根节点的树没有左右子节点，于是此树的前序遍历完毕。于是返回上一个树的前序遍历过程。上一个前序遍历已经访问了根节点6，左子节点4，于是接着访问右子节点8。而8是左子树的右子树，对这个树的根节点进行访问，于是会输出8。

步骤5：访问根节点8以后，发现没有左右子节点，于是返回上一个左子树的前序遍历，发现已经遍历完了 。于是再返回上一级“大树”的前序遍历。发现大树的前序遍历过程，该访问右子节点了。于是对右子节点14进行访问，也就相当于对右子树进行前序遍历访问，于是会先输出根节点14

步骤6：步骤就是再访问别的子节点，然后对子节点为根的树进行前序遍历。一直遍历完这个树。

到这里，我们会发现，对一个节点进行访问，那就是对以该节点为根节点的树进行访问，到底以后逐级返回就行。

1.2、中序遍历：

先访问左子节点，再访问根节点，再访问右子节点。
根节点在中间
步骤1：对大树进行访问，先访问左子节点6。
每个节点都是一个树.
对以6为根节点的左子树进行访问，先访问左子树的左子节点4.
对以4为根的树进行访问，发现左节点为空，访问完毕，于是再访问根节点4，输出4，再访问右子节点，发现为空。此时对以4为根的树访问完毕，返回上一级。
步骤2：此时左子树的左子节点4已经访问完毕，于是访问左子树的根节点，于是输出6.
...
步骤i：返回大树的根节点10以后，此时会对大树的右子节点14进行中序遍历访问。就是对右子树进行中序遍历访问。于是会先对右子树的左子节点12进行访问，访问完毕输出12以后，才会访问右子树的根节点14.
...

按照这个思想，中序遍历，从以10为根节点的树不断地访问下面的树，最终会返回
4,6,8,10,12,14,16

1.3、后序遍历：

先访问左子节点，再访问右子节点，最后 再访问根节点。
根节点在后面
按照上述逻辑，不断地递归访问，把每一个节点当成一个树，进行访问，然后再逐级返回。最终的输出结果就是4/8/6/12/16/14/10.

因为这 三种遍历都有递归和循环两种不同的实现方法。应该对这三种遍历的六种实现方法都了如指掌。

二、用代码实现这三种遍历

2.1、递归实现：

2.1.1、前序遍历

先用递归，递归比较简单：

def preorder(tree):
    if tree:
        print(tree.getRootVal())
        preorder(tree.getLeftChild())
        preorder(tree.getRightChild())

2.1.2、中序遍历

先访问左子节点==>先把左子节点（左子树）作为参数传入函数中
再访问根节点 ==> 返回根节点的值
再访问右子节点==>再把右子节点（右子树）作为参数传入函数中

代码实现：

def inorder(tree):
  if tree != None:
      inorder(tree.getLeftChild())
      print(tree.getRootVal())
      inorder(tree.getRightChild())

2.1.2、后序遍历

先访问左子节点==>先把左子节点（左子树）作为参数传入函数中
再访问右子节点==>再把右子节点（右子树）作为参数传入函数中
再访问根节点 ==> 返回根节点的值

代码实现：

def postorder(tree):
    if tree != None:
        postorder(tree.getLeftChild())
        postorder(tree.getRightChild())
        print(tree.getRootVal())
上一篇下一篇

猜你喜欢

热点阅读