C++-二叉树递归遍历与非递归遍历实现_随笔

C++-二叉树递归遍历与非递归遍历实现

-二叉树递归遍历与非递归遍历实现

引言
0 有关线性表结点定义-linkNode
1 栈的链式存储结构实现-linkedStack
2 队列的链式存储结构实现-linkedQueue
3 二叉树的链式存储结构实现
- 3.1 树的结点定义-TreeNode
- 3.2 二叉树定义
- 3.3 前中后序遍历-递归算法实现
- 3.4 前中后序遍历-非递归算法实现
- 3.5 层序遍历算法实现
4 代码测试
5 测试结果

引言

    二叉树的遍历方法有：前序遍历、中序遍历、后序遍历、层序遍历，其中前中后序遍历又有递归遍历和非递归遍历之分。
    由于递归遍历算法本质上是借助系统栈实现的，因此，其非递归遍历算法的实现，也需要借助栈来实现。
    对于层序遍历，因为是从根节点开始向下逐层、从左向右遍历的，要求最先遍历到的结点先被访问，即“先进先出”的一种特性，就可以借助一个队列完成层序遍历。
    下面，先分别准备栈和队列两种数据结构的链式存储实现类（ PS：此次使用C++语言编写代码，这样整体代码结构比较清晰，方法调用时候引用传值比较nice，有关一些基本 *** 作的函数/方法管理起来也更加方便些，以下代码复制粘贴过去即可用）。

0 有关线性表结点定义-linkNode

linkNode结点定义本来是放置在一个单独的头文件#include "linkNode.h"里面的，采用类模板方式定义，是可以线性表通用的，被但是后来考虑到在树的一些 *** 作过程中，需要同时在一个头文件里面引入栈和队列，为了偷懒，就直接将结点类作为栈和队列的内部类进行管理了。
结点定义代码如下，

//结点定义
template 
class linkNode{
public:
	//setter
	void setData(T data){
		this->data=data;
	}
	void setNext(linkNode* next){
		this->next=next;
	}
	//getter
	T getData(){
		return this->data;
	}
	linkNode* getNext(){
		return this->next;
	}
	//constructor
	linkNode(){
		this->setData(0);
		this->setNext(NULL);
	}
	linkNode(T data,linkNode* next){
		this->setData(0);
		this->setNext(NULL);
	}

protected:

private:
	T data;//数据域
	linkNode* next;//指针域
};

1 栈的链式存储结构实现-linkedStack

直接上代码，不解释原理。

//#include "linkNode.h"

template 
class linkedStack{
public:
	//inner class
	template 
	class linkNode{
	public:
		//setter
		void setData(T data){
			this->data=data;
		}
		void setNext(linkNode* next){
			this->next=next;
		}
		//getter
		T getData(){
			return this->data;
		}

		linkNode* getNext(){
			return this->next;
		}
		//constructor
		linkNode(){
			this->setData(0);
			this->setNext(NULL);
		}
		linkNode(T data,linkNode* next){
			this->setData(0);
			this->setNext(NULL);
		}

	protected:

	private:
		T data;//数据域
		linkNode* next;//指针域
	};

	//setter
	void setHeader(linkNode* header){
		if (this->header!=NULL)
		{
			this->header=header;
			return;
		}
		std::cout<<"do setHeader Failed!"<* getHeader(){
		return this->header;
	}
	//constructor
	linkedStack(){
		this->header=new linkNode;
	}

	//methods
	
	bool isEmpty(){
		return this->header->getNext()==NULL?true:false;
	}

	
	linkNode* getTop(){
		return this->header->getNext();
	}

	
	bool PushlinkedStack(T e){
		//创建新的结点
		linkNode* newNode=NULL;
		newNode=new linkNode;
		newNode->setData(e);
		//入栈 *** 作
		newNode->setNext(this->header->getNext());
		this->header->setNext(newNode);
		return true;
	}

	
	bool PoplinkedStack(T& e){
		linkNode* p=NULL;//辅助指针
		//获取被删除的结点
		p=this->header->getNext();
		//出栈
		this->header->setNext(p->getNext());
		//销毁结点
		if (p!=NULL)
		{
			e=p->getData();
			delete p;
		}
		return true;
	}

protected:

private:
	linkNode* header;//头结点
};

2 队列的链式存储结构实现-linkedQueue

直接上代码，不解释原理。

//#include "linkNode.h"


template 
class linkedQueue{
public:
	//inner class
	template 
	class linkNode{
	public:
		//setter
		void setData(T data){
			this->data=data;
		}
		void setNext(linkNode* next){
			this->next=next;
		}
		//getter
		T getData(){
			return this->data;
		}
		linkNode* getNext(){
			return this->next;
		}
		//constructor
		linkNode(){
			this->setData(0);
			this->setNext(NULL);
		}
		linkNode(T data,linkNode* next){
			this->setData(0);
			this->setNext(NULL);
		}

	protected:

	private:
		T data;//数据域
		linkNode* next;//指针域
	};

	//setter
	//getter
	//constructor
	linkedQueue(){
		this->front=new linkNode;
		this->rear=this->front;
	}

	
	bool isEmpty(){
		return this->front==this->rear?true:false;
	}

	
	void enQueue(T e){
		linkNode* newNode=new linkNode;//创建新节点
		newNode->setData(e);
		//入队-尾插法
		this->rear->setNext(newNode);
		this->rear=newNode;
	}

	
	void deQueue(T& e){
		linkNode* node=NULL;//辅助指针-记录出队结点
		//判断是否队空
		if (this->isEmpty()) return;
		//获取出队结点
		node=this->front->getNext();
		e=node->getData();
		//出队
		this->front->setNext(node->getNext());
		if (this->rear==node)
		{
			this->front=this->rear;
		}
		//释放结点
		delete node;
	}


protected:

private:
	linkNode* front;//队头
	linkNode* rear;//队尾
};

3 二叉树的链式存储结构实现

这部分也是直接上代码，不解释原理。

3.1 树的结点定义-TreeNode

//定义节点
template 
class TreeNode{
public:
	//setter
	void setData(T data){
		if (typeid(data)==typeid(char))
		{
			this->data=data;
			return;
		}
		std::cout<<"The Type is Wrong!"<lchild=lchild;
			return;
		}
		this->lchild=NULL;
	}
	void setRchild(TreeNode* rchild){
		if (rchild!=NULL)
		{
			this->rchild=rchild;
			return;
		}
		this->rchild=NULL;
	}
	//getter
	T getData(){
		return this->data;
	}
	TreeNode* getLchild(){
		return this->lchild;
	}
	TreeNode* getRchild(){
		return this->rchild;
	}
	//constructor
	TreeNode(){
		this->setData(0);
		this->lchild=NULL;
		this->rchild=NULL;
	}
	TreeNode(T data){
		this->setData(data);
		this->lchild=NULL;
		this->rchild=NULL;
	}
	//methods
 	virtual void visit(){
		std::cout<<" "<data<<" "<visit();
		if (this->lchild!=NULL)
		{
			this->lchild->preOrder();
		}
		if (this->rchild!=NULL)
		{
			this->rchild->preOrder();
		}
	}

	//中序遍历
	void inOrder(){
		if (this->lchild!=NULL)
		{
			this->lchild->inOrder();
		}
		this->visit();
		if (this->rchild!=NULL)
		{
			this->rchild->inOrder();
		}
	}

	//后序遍历
	void postOrder(){
		if (this->lchild!=NULL)
		{
			this->lchild->postOrder();
		}
		if (this->rchild!=NULL)
		{
			this->rchild->postOrder();
		}
		this->visit();
	}
protected:

private:
	T data;//数据域
	TreeNode* lchild;//左孩子结点
	TreeNode* rchild;//右孩子结点
};

3.2 二叉树定义

#include "TreeNode.h"
#include "linkedStack.h"
#include "linkedQueue.h"

//定义二叉树
template 
class BinaryTree{
public:
	//setter
	void setRoot(TreeNode* root){
		if (root!=NULL)
		{
			this->root=root;
			return;
		}
		this->root=NULL;
	}
	//getter
	TreeNode* getRoot(){
		return this->root;
	}
	
protected:

private:
	TreeNode* root;//根结点
};

3.3 前中后序遍历-递归算法实现

直接放在binaryTree.h头文件中，作为BinaryTree类的成员方法即可。

//前序遍历
	void preOrder(){
		if (this->root!=NULL)
		{
			this->root->preOrder();
		}
	}
	//中序遍历
	void inOrder(){
		if (this->root!=NULL)
		{
			this->root->inOrder();
		}
	}
	//后序遍历
	void postOrder(){
		if (this->root!=NULL)
		{
			this->root->postOrder();
		}
	}

3.4 前中后序遍历-非递归算法实现

直接放在binaryTree.h头文件中，作为BinaryTree类的成员方法即可。

	
	void preOrderWithStack(){
		linkedStack*> *S=new linkedStack*>;//初始化栈
		TreeNode* p=this->root;//辅助指针
		if (S==NULL) return;
		//循环-前序遍历实现
		while (p!=NULL||!S->isEmpty())
		{
			if (p!=NULL)
			{
				p->visit();//访问根节点
				S->PushlinkedStack(p);//入栈-[记录根节点]
				p=p->getLchild();//左子树
			}else
			{
				S->PoplinkedStack(p);//出栈-[获取根节点]
				p=p->getRchild();//右子树
			}
		}
		//释放栈
		if (S!=NULL)
		{
			delete S;
		}
	}

	
	void inOrderWithStack(){
		linkedStack*>* S=new linkedStack*>;//初始化栈
		TreeNode* p=this->root;//辅助指针
		if (S==NULL)
		{
			return;
		}
		//循环-中序遍历实现
		while (p!=NULL||!S->isEmpty())
		{
			if (p!=NULL)//p为根节点
			{
				S->PushlinkedStack(p);
				p=p->getLchild();
			}else
			{
				S->PoplinkedStack(p);
				p->visit();//访问当前节点
				p=p->getRchild();
			}
		}
		//释放栈
		if (S!=NULL)
		{
			delete S;
		}
		//TreeNode* A=new TreeNode;
		//A->setData('A');
		//S->PushlinkedStack(A);
		//linkNode*>* fNode=S->getHeader()->getNext();
		//std::cout<getHeader()->getNext()<<"data:"<getData()->getData()<*>* S=new linkedStack*>;//初始化栈
		TreeNode* p=this->root; //工作指针
		TreeNode* r=NULL;//记录当前节点是否被访问过
		if (S==NULL) return;
		//循环-后序遍历实现
		while (p!=NULL||!S->isEmpty())
		{
			if (p!=NULL)
			{
				S->PushlinkedStack(p);//子树根节点/左子树入栈
				p=p->getLchild();//继续查找左子树
			}else
			{
				p=S->getTop()->getData();//获取栈顶元素
				//如果右子树不为空
				if (p->getRchild()!=NULL&&r!=p->getRchild())
				{
					p=p->getRchild();//继续查找右子树
				}else
				{
					//右子树为空-访问左子树
					S->PoplinkedStack(p);//出栈-获取左子树/根节点
					p->visit();//访问左子树/根节点
					r=p;//记录当前被访问的结点
					p=NULL;//将工作指针置空
				}//if
			}//else
		}//while
		//释放栈
		if (S!=NULL) delete S;
	}

3.5 层序遍历算法实现

直接放在binaryTree.h头文件中，作为BinaryTree类的成员方法即可。

	
	void levelOrder(){
		if (this->root!=NULL)
		{
			linkedQueue*>* Q=new linkedQueue*>;//初始化队列
			TreeNode* p=this->root;//工作指针
			if (Q==NULL) return;
			Q->enQueue(p);//根节点入队
			//循环-层次遍历
			while (!Q->isEmpty())
			{
				Q->deQueue(p);//首个结点出队
				p->visit();//访问结点
				if (p->getLchild()!=NULL)//左子树不为空-左子树入队
					Q->enQueue(p->getLchild());
				if (p->getRchild()!=NULL)//右子树不为空-右子树入队
					Q->enQueue(p->getRchild());
			}//while
			//释放队列
			if (Q!=NULL) delete Q;
		}
	}

4 代码测试

此处手动创建二叉树结点，并设置树结点之间的关系，二叉树的结构如下图，

测试代码如下，

#include "BinaryTree.h"
void test_binaryTree(){
	//创建结点
	TreeNode* A=new TreeNode('A');
	TreeNode* B=new TreeNode('B');
	TreeNode* C=new TreeNode('C');
	TreeNode* D=new TreeNode('D');
	TreeNode* E=new TreeNode('E');
	TreeNode* F=new TreeNode('F');
	TreeNode* G=new TreeNode('G');
	TreeNode* H=new TreeNode('H');
	TreeNode* I=new TreeNode('I');
	//设置结点间的关系
	H->setRchild(I);
	C->setRchild(D);
	G->setLchild(H);
	B->setRchild(C);
	E->setLchild(F);
	E->setRchild(G);
	A->setLchild(B);
	A->setRchild(E);
	//创建二叉树
	BinaryTree* bTree=new BinaryTree;
	bTree->setRoot(A);
	//bTree->preOrder();//前序遍历
	//bTree->inOrder();//中序遍历
	//bTree->postOrder();//后序遍历
	bTree->levelOrder();//层序遍历
	//bTree->inOrderWithStack();//中序遍历非递归实现
	//bTree->preOrderWithStack();//前序遍历非递归实现
	//bTree->postOrderWithStack();//后序遍历非递归实现
}




int main(int argc,char** argv){
	test_binaryTree();
	return 0;
}

5 测试结果

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/zaji/4749787.html

C++-二叉树递归遍历与非递归遍历实现

发表评论

评论列表（0条）