数据结构之二叉树的遍历汇总

「爱情、让人受尽委屈。」 2022-08-06 01:11 163阅读 0赞

声明：小弟写博客不久，主要是边上班边学习边写博客，如果错误，望各位包涵并指导。

二叉树是一种常用的非线性数据结构，二叉树是由一个根节点和称为根的左、右子树的两颗互不相交的二叉树构成。二叉树具有一些特殊的性质，如第i层上最多有2^(i-1)个结点。二叉树的链式存储结构如下：

typedef struct BTNode
    {
    	char data;                        //字符型数据;
    	struct BTNode* lChild,*rChild;    //左右子结点的指针;
    
    }BTNode,*BiTree;

data为二叉树中存储的数据，该结构中存储的是字符型数据，lChild和rChild分别指向二叉树中结点的左右子节点。二叉树的遍历是二叉树中最基础的一部分，二叉树的遍历根据遍历根节点的顺序可以分为先（根）序遍历、中（根）序遍历和后（根）遍历。在遍历二叉树之前，先看看如何创建一颗二叉树。

**1、创建二叉树**

可以根据一串字符来创建二叉树，按先序序列来创建一颗二叉树：

BiTree& CreateBiTree(BiTree &biTree)
    {
            //输入一串字符，'?'为结束符;
            char ch;
    	scanf("%c",&ch);
    
    	if(ch=='?')
    	{
    		biTree=NULL;
    		return biTree; 
    	}
    	else
    	{
    		biTree=(BTNode*)malloc(sizeof(BTNode));
    
    		biTree->data=ch;
    
    		CreateBiTree(biTree->lChild);
    		CreateBiTree(biTree->rChild);
    
    		return biTree;
    	}
    }

**2、二叉树的遍历**

二叉树的遍历是二叉树最基本的运算，遍历是指如何通过算法来实现对二叉树的一个个节点的访问。二叉树的遍历又可以分为递归的方式遍历和非递归的方式遍历。首先我们看一下递归遍历二叉树。

/**************************************
    * 结点数据的打印输出;
    **************************************/
    void Vistor(BTNode* pNode)
    {
    	if(pNode==NULL)
    	{
    		return;
    	}
    
    	if(pNode->data!=NULLKEY)
    	{
    		printf("%c",pNode->data);
    	}
    }
    
    
    /****************************************
    *二叉树的先序遍历递归;
    ****************************************/
    void PreOrder(BiTree root)
    {
            //注意临界条件的判断;
            if(root!=NULL)
    	{
    		Vistor(root);
    		PreOrder(root->lChild);
    		PreOrder(root->rChild);
    	}
    }
    
    /****************************************
    *二叉树的中序遍历递归;
    ****************************************/
    void InOrder(BiTree root)
    {
    	if(root!=NULL)
    	{
    		InOrder(root->lChild);
    		Vistor(root);
    		InOrder(root->rChild);
    	}
    }
    
    /****************************************
    *二叉树的后序遍历递归;
    ****************************************/
    void PostOrder(BiTree root)
    {
    	if(root!=NULL)
    	{
    		PostOrder(root->lChild);
    		PostOrder(root->rChild);
    		Vistor(root);
    	}
    }

**3、二叉树的非递归遍历**

实际上一个递归算法在执行调用过程中，实质上隐式的使用了一个递归工作栈，其作用是在不同层次递归调用时进行信息的保护和恢复。如果在算法中显式的使用一个栈，则可以设计出容易理解的非递归算法。

(1) 先序遍历

思路：直接先访问节点数据，再遍历左子树，将左子树结点压栈，当左子树为空时，在弹出栈顶结点，再遍历右子树。

void PreOrder2(BiTree root)
 {
     BTNode* pNode=root;
 
     //定义一个栈来存放结点;
     std::stack<BTNode*> stackNode;
 
     while(pNode!=NULL||!stackNode.empty())
     {
         if(pNode!=NULL)
         {
             //加入到栈中;
             stackNode.push(pNode);
 
             //由于是前序遍历，故直接先访问结点;
             Vistor(pNode);
 
             //指向左节点;
             pNode=pNode->lChild;
         }
         else
         {
             //取栈顶结点;
             pNode=stackNode.top();
             
             //栈顶指针减一;
             stackNode.pop();
             
             //指向栈顶节点的右结点;
             pNode=pNode->rChild;
         }
     }
 }

(2) 中序遍历

思路：先遍历左子树，将左子树结点压栈，当左子树为空时，在弹出栈顶结点，访问节点数据，再遍历右子树。

void InOrder2(BiTree root)
 {
     BTNode* pNode=root;
 
     std::stack<BTNode*> stackNode;
 
     while(pNode!=NULL||!stackNode.empty())
     {
         if(pNode!=NULL)
         {
             //由于先遍历左子树,故根节点直接入栈;
             stackNode.push(pNode);
             pNode=pNode->lChild;
         }
         else
         {
             //如果左子树为空则遍历根节点;
             pNode=stackNode.top();
             stackNode.pop();
 
             Vistor(pNode);
             
             //再遍历右子树;
             pNode=pNode->rChild;
 
         }
     }
 }

(3) 后序遍历

思路：二叉树的后序遍历的非递归算法比其先序、中序的非递归算法要复杂一些，后序遍历必须按”左—右—根“的次序进行。所以，遇到根节点不能先访问它，必须将根指针入栈保存，然后去后序遍历根的左子树。待左子树遍历完成后，从栈中取出根指针，这时候任不能访问根指针。还必须第二次讲根指针入栈保存，然后再去后序遍历根的右子树。待右子树遍历完毕后，再一次的从栈顶取出跟指针，才能访问根指针。

由于根结点两次出栈，所以需要用一个标识来区别是第几次出栈，因此需要改变一下结点的数据结构，添加一个tag变量，用来记录是第几次出栈，当第2次出栈时才进行访问。

typedef struct BTNodePost 
 { 
 	BiTree biTree; //记录树结点;
 	char tag;		 //记录结点出栈次数;
 
 }BTNodePost,*BiTreePost;
 
 void PostOrder2(BiTree root)
 {
 	stack<BTNodePost*> stackNodePost;
 
 	BTNode* pNode=root;
 
 	while(pNode!=NULL||!stackNodePost.empty())
 	{
 		if(pNode!=NULL)
 		{
 			//结点不为空,创建新的结构,并设置tag值为1;
 			BTNodePost* bTNodePost=(BTNodePost*)malloc(sizeof(BTNodePost));
 
 			bTNodePost->biTree=pNode;
 
 			bTNodePost->tag=1;
 
 			pNode=pNode->lChild;
 
 			stackNodePost.push(bTNodePost);
 		}
 		else
 		{
 			BTNodePost* btNodePost=stackNodePost.top();
 
 			stackNodePost.pop();
 
 			//如果tag值为1,则继续添加入栈,并设置tag为2;
 			if(btNodePost->tag==1)
 			{
 				stackNodePost.push(btNodePost);
 
 				pNode=btNodePost->biTree->rChild;
 
 				btNodePost->tag=2;
 			}
 			else
 			{
 				//当tag值为2,进行访问。
 				Vistor(btNodePost->biTree);
 				pNode=NULL;
 			}
 		}
 	}
 }

**4、二叉树的层次遍历**

层次遍历是规定从根结点开始遍历，依层次次序自上向下，自左向右地访问树中各结点。层次遍历采用一个工作队列，首先将根节点入队列，然后反复出队列，并把出队列的指针的左右子树结点依次入列，直到队列为空。

void LevelOrder(BTNode* root)
 {
 	if(NULL==root)
 	{
 		return;
 	}
 
 	queue<BTNode*> queueNode;
 
 	BTNode* pNode=root;
 
 	queueNode.push(root);
 
 	while(!queueNode.empty())
 	{
 		pNode=queueNode.front();
 		
 		queueNode.pop();
 
 		Vistor(pNode);
 
 		if(pNode->lChild!=NULL)
 		{
 			queueNode.push(pNode->lChild);
 		}
 		if(pNode->rChild!=NULL)
 		{
 			queueNode.push(pNode->rChild);
 		}
 	}
 }

**5、总结**

二叉树的遍历就总结到这里，后续会继续学习并总结关于二叉树的一些算法。上如代码经过测试用例测试过，如果有细节问题处理不对，望多多包涵并指正，谢谢！