二叉树遍历及代码

痛定思痛。 2022-12-30 08:29 188阅读 0赞

二叉树是最基本的树形结构，也是我们编程过程中经常碰到的数据结构，在二叉树上所有可用的操作中，遍历是最常用的操作，所谓二叉树遍历（Binary Tree Traversal）,就是遵从某种次序，遍访二叉树中的所有结点，使得每个结点被访问一次，而且只访问一次。这里，“访问”的意思就是对结点施行某些操作，例如查找具有某种属性值的结点，输出结点信息，修改结点的数据值等，但要求这种访问不破坏它原来的数据结构。

对线性结构而言，遍历是一种基本的操作，但二叉树是一种非线性结构，每个结点可能有不止一个直接后继，这样必须规定遍历的规则，按此规则遍历二叉树，最后得到二叉树结点的一个线性序列。

下面分别介绍二叉树遍历的递归算法和非递归算法的相关技术与实现代码。

## 二叉树遍历的递归算法 ##

令L, R, V 分别代表遍历一个结点的左子树、右子树和访问该结点的操作，则遍历二叉树有6种规则：VLR, LVR, LRV, VRL, RVL, RLV。若规定先左后右，则仅剩下前面三种规则，即VLR（前序遍历）、LVR（中序遍历）、LRV（后序遍历）。另三种是它们的镜像。

图1给出了一棵二叉树的三种遍历过程。从图中可以看到，这三种遍历过程具有相同的遍历路线，但遍历的结果各不相同。对于每种遍历，树中每个结点都要经过三次（对于叶结点，其左、右子树视为空子树），但前序遍历在第一次遇到结点时立即访问，而中序遍历是在第二次遇到结点时才访问，后序遍历要到第三次（最后一次）遇到结点才访问。

![SouthEast][]

前序遍历：- + a \* b - c d / e f

中序遍历：a + b \* c - d - e / f

后序遍历：a b c d - \* + e f / -

下面三个程序分别给出了前序、中序、后序遍历二叉树的递归实现。它们的差别在于语句void visit(BinTreeNode<T> \* p)所处的位置不同。

二叉树的中序遍历算法
    template <class T>
    void BinaryTree<T>:: InOrder(BinTreeNode<T> *subTree, void (* visit)(BinTreeNode<T> *p)){
    //递归函数：此算法按照中序次序遍历以subTree为根的子树。
     if(subTree != NULL){
         InOrder(subTree->leftChild, visit);
         visit(subTree);
         InOrder(subTree->rightChild, visit);
        }
    };

二叉树的前序遍历算法
    template <class T>
    void BinaryTree<T>:: PreOrder(BinTreeNode<T> *subTree, void (* visit)(BinTreeNode<T> *p)){
    //递归函数：此算法按照前序次序遍历以subTree为根的子树。
     if(subTree != NULL){
         visit(subTree);
         PreOrder(subTree->leftChild, visit);
         PreOrder(subTree->rightChild, visit);
        }
    };

二叉树的后序遍历算法
    template <class T>
    void BinaryTree<T>:: PostOrder(BinTreeNode<T> *subTree, void (* visit)(BinTreeNode<T> *p)){
    //递归函数：此算法按照后序次序遍历以subTree为根的子树。
     if(subTree != NULL){
         PostOrder(subTree->leftChild, visit);
         PostOrder(subTree->rightChild, visit);
         visit(subTree);
        }
    };

理解了上述的遍历方法后，我们再来看一个二叉树后序遍历的应用：**计算二叉树的结点个数**

为了计算二叉树的结点个数，可以遍历根结点的左子树和右子树，分别计算出左子树和右子树的结点个数，然后把访问根结点的语句改为相加语句：二叉树根结点的左子树结点个数加上右子树结点个数，再加上根结点个数，得到整个二叉树的结点个数。

template <class T>
    int BinaryTree<T>::Size(BinTreeNode<T> *subTree)const{
      //私有函数：计算以*subTree为根的二叉树的结点个数
      if (subTree == NULL) return 0;//递归结束： 空树结点个数为0
      else return 1+Size(subTree->leftChild)+Size(subTree->rightChild);
    };

## 二叉树遍历的非递归算法 ##

三种不同次序的遍历二叉树的递归算法的结构相似，只是访问根结点及遍历左子树、遍历右子树的先后次序不同而已。如果暂时把visit(subTree)（访问根结点）这个不涉及递归的语句抛开，则三个算法递归走过的路线是一样的。在递归执行过程中，前序遍历的情形是每进入一层递归调用时访问根结点，再依次向它的左子树、右子树递归调用。中序遍历的情形是在左子树递归调用退出时访问根结点，然后向它的右子树递归调用。

为了把一个递归过程改为非递归过程，一般需要利用一个工作栈，记录遍历时的回退路径。

**1. 利用栈的前序遍历非递归算法**

下图显示了利用栈实现前序遍历a给出的二叉树过程。每次访问一个结点后，在向左子树遍历下去之前，利用这个栈记录该结点的右子女（如果有的话）结点的地址，以便在左子树退回时可以直接从栈顶取得右子树的根结点，继续其右子树的前序遍历。

![SouthEast 1][] ![SouthEast 2][]

#include "stack.h"
    template <class T>
    void BinaryTree<T> :: PreOrder(void( *visit)(BinTreeNode<T> *p)){
    	stack<BinTreeNode<T>*> S;
    	BinTreeNode<T> *p=root;
    	S.Push(NULL);
    	while(p!= NULL){
    		visit(p);
    		if(p->rightChild != NULL) S.Push(p->rightChild);
    		if(p->leftChild != NULL) p=p->leftChild;
    		else S.Pop(p);
    	}
    };

## 2. 利用栈的中序遍历非递归算法 ##

中序遍历二叉树的非递归算法也要使用一个栈，以记录遍历过程中回退的路径。在一棵树中首先访问的是中序下的第一个结点，它位于从根开始沿leftChild链走到最左下角的结点，该结点的leftChild指针为NULL。访问它的数据之后，再遍历该结点的右子树。此右子树又是二叉树，重复执行上面的过程，直到该子树遍历完。

如果某结点的右子树遍历完或右子树为空，说明以这个结点为根的二叉树遍历完，此时从栈中退出更上层的结点并访问它，再向它的右子树遍历下去。

#include "stack.h"
    template <class T>
    void BinaryTree<T> :: InOrder(void( *visit)(BinTreeNode<T> *p)){
    	stack<BinTreeNode<T>*> S;
    	BinTreeNode<T> *p=root;
    	do{
    		while (p!=NULL){
    				S.Push(p);
    				p=p->leftChild;
    		}
    		if(! S.IsEmpty()){
    			S.Pop(p);visit(p);
    			p=p->rightChild;
    		}
    	}while(p!= NULL || ! S.IsEmpty());
    };

[SouthEast]: /images/20221120/1f4b3bff74d24561a766ef6c5f40d222.png
[SouthEast 1]: https://img-blog.csdn.net/20130906175130171?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvbGlual9t/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 2]: https://img-blog.csdn.net/20130906180036562?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvbGlual9t/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast