二叉树的基本操作请看：http://blog.csdn.net/sysu_arui/article/details/7865876

前面简答介绍了二叉树的基本操作，包括二叉树的建立，销毁，递归遍历，以及其他一些常见的递归算法，现在集中讨论一下二叉树的层次遍历和非递归遍历。

二叉树的层次遍历要用到队列，前序、中序和后序非递归遍历要用到栈，这里我就不自己写队列和栈了，直接使用C++标准库中的容器适配器queue和stack。

1、 二叉树的层次遍历

二叉树的层次遍历类似图的广度优先遍历，都用到了队列。

基本思路：

(1)根结点非空，则入队列

(2)队列非空，队首元素出队列，输出结点值，若结点有左孩子，左孩子入队列；若结点有右孩子，右孩子也入队列。

(3)重复步骤(2)直到队列为空

显然通过以上步骤，得到的是二叉树从上至下，从左到右的层次遍历序列。实现代码如下：

//二叉树的层次遍历，用到了队列 
void levelOrderTraverse(const BiTree& T)
{
	queue<BiTree> q;
	BiTree p = NULL;
	
	if(T)//若根结点非空，则入队列 
	{
		q.push(T);
	}
	while(!q.empty())//队列非空 
	{
		p = q.front();
		q.pop();
		cout<<p->data<<" ";
		if(p->lchild)//左孩子不空，入队列 
		{
			q.push(p->lchild);
		}
		if(p->rchild)//右孩子不空，入队列 
		{
			q.push(p->rchild);
		}
	} 
}

2、二叉树的先序非递归遍历

二叉树的先序非递归遍历比较简单，基本思路是先输出结点值，再入栈，然后遍历左子树。退栈时，遍历栈顶结点的右子树，看代码：

//二叉树的先序非递归遍历 
void iterativePreOrderTraverse(const BiTree& T)
{
	stack<BiTree> s;
	BiTree p = T;
	
	while(p || !s.empty())//p非空，或栈非空
	{
		if(p)
		{
			//输出根结点，根结点入栈，遍历左子树 
			cout<<p->data<<" ";
			s.push(p);
			p = p->lchild;
		}
		else
		{
			//根结点退栈，遍历右子树 
			p = s.top();
			s.pop();
			p = p->rchild;//转右孩子结点 
		}
	}
}

3、二叉树的中序非递归遍历

二叉树的中序非递归遍历也很简单，和先序不同的是，中序是先进栈，再遍历左子树；出栈时，才输出结点值，然后遍历右子树，代码如下：

//二叉树的中序非递归遍历 
void iterativeInOrderTraverse(const BiTree& T)
{
	stack<BiTree> s;
	BiTree p = T;
	
	while(p || !s.empty())//p非空，或栈非空
	{
		if(p)
		{
			//根指针进栈 ，遍历左子树 
			s.push(p);	
			p = p->lchild;
		}
		else
		{
			//根指针退栈，访问根结点，遍历右子树 
			p = s.top();
			s.pop();
			cout<<p->data<<" ";
			p = p->rchild;
		}
	}
}

4.二叉树的后序非递归遍历

二叉树的后序非递归遍历，比先序和中序非递归遍历，稍微复杂点。因为后序遍历的顺序是左子树->右子树->根结点，所以我们在遍历过程中得标记左右子树的状态。这里我们用一个bool变量标识结点p的右子树遍历状态，false表示右子树未遍历，true则表示右子树已遍历。代码如下：

(1)版本1

//二叉树的后序非递归遍历 
void iterativePostOrderTraverse(const BiTree& T)
{
	stack<pair<BiTree,bool> > s;
	BiTree p = T;
	
	while(p || !s.empty())
	{
		if(p)
		{
			s.push(make_pair(p,false));//false表示根结点p的右子树未访问 
			p = p->lchild;
		}
		else
		{
			if(s.top().second == false)//根结点的右子树未访问 
			{
				s.top().second = true;//标志右子树为已访问 
				p = s.top().first->rchild;//遍历右子树 
			}
			else//右子树已访问 
			{
				cout<<s.top().first->data<<" "; //输出根结点值 
				s.pop();//根结点出栈 
			}
		}	
	}
}
(2)版本2 
//后序非递归遍历的另一个版本 
void anotherIterativePostOrderTraverse(const BiTree& T)
{
	stack<pair<BiTree,bool> > s;
	BiTree p = T;
	
	do
	{
		while(p)
		{
			s.push(make_pair(p,false));
			p = p->lchild;
		}
		
		while(!s.empty() && s.top().second == true)
		{
			cout<<s.top().first->data<<" ";
			s.pop();
		}
		
		if(!s.empty())
		{
			s.top().second = true;
			p = s.top().first->rchild;
		}
	}while(!s.empty());
}

注：我们来分析一下，后序非递归遍历的执行过程。举一个简单的例子吧，使用根结点为A，其左右子树分别为B、C的树来讲解版本(1)的执行过程。

(1)初始时，p =T，接着执行循环，若根结点非空，则<p,false>入栈，表示根结点p的右子树还未遍历，同时置p为其左指针，遍历左子树。若根结点为空(此时栈也为空)，循环条件不满足，直接结束。

(2)在接下来的循环中，若p为空则看栈顶结点状态。若其右子树未遍历，则遍历其右子树(p值发生改变)，否则直接输出结点值，并弹出栈顶结点(p值未改变)。

(3)p=A，<A,false>入栈，p=A->lchild=B;

p=B，<B,false>入栈，p=NULL;

p=NULL，栈非空，且栈顶结点B的右子树未访问，置true，然后访问B的右子树，p=B->rchild=NULL;

p=NULL，栈非空，且栈顶结点B的右子树已访问，输出结点B，弹出栈顶结点B，注意此时p==NULL，因为这个过程p的值未改变。

p=NULL，栈非空，且此时栈顶结点A的右子树未访问，置true，然后访问A的右子树，p=A->rchild=C;

p=C，非空，<C,false>入栈，p = C->lchild=NULL;

p=NULL，栈非空，栈顶元素C的右子树为访问，置true，然后访问C的右子树，p=C->rchild=NULL;

p=NULL，栈非空，栈顶元素C的右子树已访问，输出结点C，弹出栈顶元素C。

p=NULL，栈非空，栈顶元素A的右子树已访问，输出结点A，弹出栈顶元素A。

p=NULL，此时栈已为空。

(4)注意到在上述的分析过程中，我们发现当p的值为NULL，出栈，p的值未改变，此时我们不用判断p的值，可以直接判断栈顶元素的右子树的访问状态，于是调整循环结构就得到了版本(2)。但是它们原理都是一样的。

5、完整测试代码

#include <cstdlib>
#include <iostream>
#include <stack>
#include <queue>

using namespace std;

//二叉树定义 
typedef char ElementType;

typedef struct BiTreeNode
{
	ElementType data;
    struct BiTreeNode* lchild;
    struct BiTreeNode* rchild;
}BiTreeNode, *BiTree;

//递归的建立一棵二叉树 
//输入为二叉树的先序序列 
void createBiTree(BiTree &T)
{
	char data;
	data = getchar();
	if(data == '#')
	{
		T = NULL;
	}
	else
	{
		T = new BiTreeNode;
		T->data = data;
		createBiTree(T->lchild);
		createBiTree(T->rchild);
	}
}

//递归销毁一棵二叉树
void destroyBiTree(BiTree &T)
{
	if(T)
	{
		destroyBiTree(T->lchild);
		destroyBiTree(T->rchild);
		delete T;
		T = NULL;
	}
}

//二叉树的层次遍历，用到了队列 
void levelOrderTraverse(const BiTree& T)
{
	queue<BiTree> q;
	BiTree p = NULL;
	
	if(T)//若根结点非空，则入队列 
	{
		q.push(T);
	}
	while(!q.empty())//队列非空 
	{
		p = q.front();
		q.pop();
		cout<<p->data<<" ";
		if(p->lchild)//左孩子不空，入队列 
		{
			q.push(p->lchild);
		}
		if(p->rchild)//右孩子不空，入队列 
		{
			q.push(p->rchild);
		}
	} 
}

//二叉树的先序非递归遍历 
void iterativePreOrderTraverse(const BiTree& T)
{
	stack<BiTree> s;
	BiTree p = T;
	
	while(p || !s.empty())//p非空，或栈非空
	{
		if(p)
		{
			//输出根结点，根结点入栈，遍历左子树 
			cout<<p->data<<" ";
			s.push(p);
			p = p->lchild;
		}
		else
		{
			//根结点退栈，遍历右子树 
			p = s.top();
			s.pop();
			p = p->rchild;//转右孩子结点 
		}
	}
}

//二叉树的中序非递归遍历 
void iterativeInOrderTraverse(const BiTree& T)
{
	stack<BiTree> s;
	BiTree p = T;
	
	while(p || !s.empty())//p非空，或栈非空
	{
		if(p)
		{
			//根指针进栈 ，遍历左子树 
			s.push(p);	
			p = p->lchild;
		}
		else
		{
			//根指针退栈，访问根结点，遍历右子树 
			p = s.top();
			s.pop();
			cout<<p->data<<" ";
			p = p->rchild;
		}
	}
}

//二叉树的后序非递归遍历 
void iterativePostOrderTraverse(const BiTree& T)
{
	stack<pair<BiTree,bool> > s;
	BiTree p = T;
	
	while(p || !s.empty())
	{
		if(p)
		{
			s.push(make_pair(p,false));//false表示根结点p的右子树未访问 
			p = p->lchild;
		}
		else
		{
			if(s.top().second == false)//根结点的右子树未访问 
			{
				s.top().second = true;//标志右子树为已访问 
				p = s.top().first->rchild;//遍历右子树 
			}
			else//右子树已访问 
			{
				cout<<s.top().first->data<<" "; //输出根结点值 
				s.pop();//根结点出栈 
			}
		}	
	}
}

//后序非递归遍历的另一个版本 
void anotherIterativePostOrderTraverse(const BiTree& T)
{
	stack<pair<BiTree,bool> > s;
	BiTree p = T;
	
	do
	{
		while(p)
		{
			s.push(make_pair(p,false));
			p = p->lchild;
		}
		
		while(!s.empty() && s.top().second == true)
		{
			cout<<s.top().first->data<<" ";
			s.pop();
		}
		
		if(!s.empty())
		{
			s.top().second = true;
			p = s.top().first->rchild;
		}
	}while(!s.empty());
}

int main(int argc, char *argv[])
{
	BiTree T = NULL;
	
	createBiTree(T);//建立二叉树 如输入AB#D##CE### 
//	createBiTreeWithGenList(T);//如输入A(B(,D),C(E))#

	cout<<"levelOrder: ";
	levelOrderTraverse(T);
	cout<<endl;
	
	cout<<"preOrder: "; //先序遍历 
//	preOrderTraverse(T);
	iterativePreOrderTraverse(T);
	cout<<endl;
	
	cout<<"inOrder: ";//中序遍历 
//	inOrderTraverse(T);
	iterativeInOrderTraverse(T);
	cout<<endl;
	
	cout<<"postOrder: ";//后序遍历 
//	postOrderTraverse(T);
//	iterativePostOrderTraverse(T);
	anotherIterativePostOrderTraverse(T);
	cout<<endl;
	
	destroyBiTree(T);//销毁二叉树，释放空间 
	
    system("PAUSE");
    return EXIT_SUCCESS;
}

注：测试代码中的一些其他函数请看二叉树的基本操作： http://blog.csdn.net/sysu_arui/article/details/7865876





Logo
向您推荐>>Eolink开发者社区

权威｜前沿｜技术｜干货｜国内首个API全生命周期开发者社区

更多推荐

ELK实现containerd的容器日志采集展示【基于logging的全栈监测】

企业级ELK Stack构建介绍

avatar 云原生

深入理解 Mocha 测试框架：从零实现一个 Mocha

前言什么是自动化测试自动化测试在很多团队中都是Devops环节中很难执行起来的一个环节，主要原因在于测试代码的编写工作很难抽象，99%的场景都需要和业务强绑定，而且写测试代码的编写工作量往往比编写实际业务代码的工作量更多。在一些很多业务场景中投入产出比很低，适合写自动化测试的应该是那些中长期业务以及一些诸如组件一样的基础库。自动化测试是个比较大的概念，其中分类也比较多，比如单元测试，端对端测试，集

avatar 云原生

(20200916 Solved)docker-compose up创建容器自动退出

问题描述如题，创建容器后自动退出了。并且docker start container无效解决方案原因是缺失了控制终端的配置，需要在docker-compose.yml中增加tty:true ，有时候这样也不行，需要再增加一个command:/bin/bash，命令不一定是这个，需要是一个不会退出的命令，然后用-d后台启动容器。Referencesdocker-compose启动容器后自动退出...

avatar 云原生