数据结构之二叉树的非递归实现

系统管理员 2022-07-16 01:40 176阅读 0赞

# 非递归实现二叉树的前序，中序以及后序遍历. #

在非递归实现二叉树的前序，中序以及后序遍历时用到了栈这种数据结构.

## 一.非递归实现前序遍历. ##

我们知道二叉树的前序遍历是先访问根结点，然后访问左子树，最后再访问右子树.那仫如何非递归去前序遍历一颗树呢？

![Center][]

## 二 .非递归实现中序遍历. ##

非递归的中序遍历类似前序遍历只不过将访问当前结点的位置切换到访问左子树对应到代码中就是在入栈之后再访问当前结点.

void PrevOrderNoR()
    	{
    		stack<Node *> s;
    		Node *cur=_root;
    		while (cur || !s.empty())
    		{
    			while (cur)    //一直向左遍历直到左为空时跳出
    			{
    				cout<<cur->_data<<" ";   //访问根结点
    				s.push(cur);
    				cur=cur->_left;
    			}
    			//此时已经访问过当前结点且当前结点的左子树为空
    			Node *top=s.top();
    			s.pop();
    			//访问当前结点的右子树
    			cur=top->_right;
    		}
    		cout<<endl;
    	}
    	void InOrderNoR()
    	{
    		//类似非递归的先序遍历，不过要在访问过当前结点的左子树之后再访问根结点
    		stack<Node *> s;
    		Node *cur=_root;
    		while (cur || !s.empty())
    		{
    			while (cur)
    			{
    				s.push(cur);
    				cur=cur->_left;
    			}
    			Node *top=s.top();
    			cout<<top->_data<<" ";
    			s.pop();
    			cur=top->_right;
    		}
    		cout<<endl;
    	}

## 三.非递归实现后序遍历. ##

如何使用非递归的方式遍历一颗树呢？我们知道后序遍历一棵树的原则是:先遍历左子树，再遍历右子树，最后再遍历根结点.而问题就出在根结点是在遍历了左子树和右子树之后才遍历的,如何在保证遍历了左右子树之后还能找到当前的根结点呢？

刚开始的想法类似前序遍历和中序遍历.一直遍历该树的左子树直到为空时不再压栈，只要停止压栈那仫栈顶结点的左子树已经访问过了而且一定为空，此时另当前元素为栈顶元素，如果判断当前结点的右子树为空或者右子树已经访问过了直接访问当前结点，如果右子树不为空或者右子树未被访问过则访问右子树.在实现中用到了一个prev指针过来记录当前结点的前一个结点.

void PostOrderNoR()
    	{
    		stack<Node *> s;
    		Node *cur=_root;
    		Node *prev=NULL;
    		while (cur || !s.empty())
    		{
    			while (cur)    //一直向左遍历直到左为空时跳出
    			{
    				s.push(cur);
    				cur=cur->_left;
    			}
    			cur=s.top();
    			//当前节点的右孩子为空或者已经访问过当前结点的右孩子则访问当前结点
    			if (cur->_right == NULL || cur->_right == prev)
    			{ 
    				cout<<cur->_data<<" ";
    				prev=cur;
    				s.pop();
    				cur=NULL;
    			}
    			else
    			{
    				//否则访问右孩子
    				cur=cur->_right;
    			}
    		}
    		cout<<endl;
    	}

## 完整代码实现> ##

BinaryTree.h

template<typename T>
    struct BinaryTreeNode
    {
    	BinaryTreeNode(const T& data=T())
    		:_data(data)
    		,_left(NULL)
    		,_right(NULL)
    	{}
    	T _data;
    	BinaryTreeNode *_left;
    	BinaryTreeNode *_right;
    };
    
    template<typename T>
    class BinaryTree
    {
    	typedef BinaryTreeNode<T> Node;
    public:
    	BinaryTree()
    		:_root(NULL)
    	{}
    	BinaryTree(const T *array,size_t size,const T& invalid)
    	{
    		size_t index=0;
    		_root=_CreatTree(array,size,index,invalid);
    	}
    	BinaryTree(const BinaryTree<T>& bt)
    	{
    		_root=_Copy(bt._root);
    	}
    	//BinaryTree<T>& operator=(const BinaryTree<T>& bt)
    	//{
    	//	//传统的写法
    	//	if (this != &bt)
    	//	{
    	//		Node *root=_Copy(bt._root);
    	//		_Destroy(_root);
    	//		_root=root;
    	//	}
    	//	return *this;
    	//}
    	BinaryTree<T>& operator=(const BinaryTree<T>& bt)
    	{
    		//现代的写法
    		if (this != &bt)   //防止自赋值
    		{
    			BinaryTree<T> tmp(bt);
    			std::swap(_root,tmp._root);
    		}
    		return *this;
    	}
    	~BinaryTree()
    	{
    		_Destroy(_root);
    	}
    public:
    	//递归的先序遍历，中序遍历，后序遍历
    	void PrevOrder()
    	{
    		_PrevOrder(_root);
    		cout<<endl;
    	}
    	void InOrder()
    	{
    		_InOrder(_root);
    		cout<<endl;
    	}
    	void PostOrder()
    	{
    		_PostOrder(_root);
    		cout<<endl;
    	}
    	//非递归的先序遍历,中序遍历，后序遍历
    	void PrevOrderNoR()
    	{
    		stack<Node *> s;
    		Node *cur=_root;
    		while (cur || !s.empty())
    		{
    			while (cur)    //一直向左遍历直到左为空时跳出
    			{
    				cout<<cur->_data<<" ";   //访问根结点
    				s.push(cur);
    				cur=cur->_left;
    			}
    			//此时已经访问过当前结点且当前结点的左子树为空
    			Node *top=s.top();
    			s.pop();
    			//访问当前结点的右子树
    			cur=top->_right;
    		}
    		cout<<endl;
    	}
    	void InOrderNoR()
    	{
    		//类似非递归的先序遍历，不过要在访问过当前结点的左子树之后再访问根结点
    		stack<Node *> s;
    		Node *cur=_root;
    		while (cur || !s.empty())
    		{
    			while (cur)
    			{
    				s.push(cur);
    				cur=cur->_left;
    			}
    			Node *top=s.top();
    			cout<<top->_data<<" ";
    			s.pop();
    			cur=top->_right;
    		}
    		cout<<endl;
    	}
    	void PostOrderNoR()
    	{
    		stack<Node *> s;
    		Node *cur=_root;
    		Node *prev=NULL;
    		while (cur || !s.empty())
    		{
    			while (cur)    //一直向左遍历直到左为空时跳出
    			{
    				s.push(cur);
    				cur=cur->_left;
    			}
    			cur=s.top();
    			//当前节点的右孩子为空或者已经访问过当前结点的右孩子则访问当前结点
    			if (cur->_right == NULL || cur->_right == prev)
    			{ 
    				cout<<cur->_data<<" ";
    				prev=cur;
    				s.pop();
    				cur=NULL;
    			}
    			else
    			{
    				//否则访问右孩子
    				cur=cur->_right;
    			}
    		}
    		cout<<endl;
    	}
    	void LevelOrder()   //层序遍历
    	{
    		_LevelOrder(_root);
    		cout<<endl;
    	}
    	size_t Size()       //求该树的总结点数
    	{
    		size_t size=_Size(_root);
    		return size;
    	}
    	size_t Depth()     //求该树的深度
    	{
    		size_t depth=_Depth(_root);
    		return depth;
    	}
    	size_t LeafSize()   //求一个树叶子节点的总数
    	{
    		size_t leaf=_LeafSize(_root);
    		return leaf;
    	}
    	size_t GetKLevel(int level)   //level层的所有节点的个数
    	{
    		size_t count=_GetKLevel(_root,level);
    		return count;
    	}
    	Node *FindNode(const T& x=T())
    	{
    		return _FindNode(_root,x);
    	}
    protected:
    	Node *_CreatTree(const T *array,size_t size,size_t& index,const T& invalid)
    	{
    		assert(array);
    		Node *root=NULL;
    		if (index < size && array[index] != invalid)
    		{
    			root=new Node(array[index]);
    			root->_left=_CreatTree(array,size,++index,invalid);
    			root->_right=_CreatTree(array,size,++index,invalid);
    		}
    		return root;
    	}
    	Node *_Copy(Node *root)
    	{
    		//proot是拷贝的新树的根节点
    		Node *cur=root;
    		Node *proot=NULL;
    		if (cur)
    		{
    			proot=new Node(cur->_data);
    			proot->_left=_Copy(cur->_left);
    			proot->_right=_Copy(cur->_right);
    		}
    		return proot;
    	}
    	void _Destroy(Node *root)
    	{
    		Node *cur=root;
    		if (cur)
    		{
    			_Destroy(cur->_left);
    			_Destroy(cur->_right);
    			delete cur;
    			cur=NULL;
    		}
    	}
    protected:
    	void _PrevOrder(Node *root)
    	{
    		Node *cur=root;
    		if (cur)
    		{
    			cout<<cur->_data<<" ";
    			_PrevOrder(root->_left);
    			_PrevOrder(root->_right);
    		}
    	}
    	void _InOrder(Node *root)
    	{
    		Node *cur=root;
    		if (cur)
    		{
    			_InOrder(cur->_left);
    			cout<<cur->_data<<" ";
    			_InOrder(cur->_right);
    		}
    	}
    	void _PostOrder(Node *root)
    	{
    		Node *cur=root;
    		if (cur)
    		{
    			_PostOrder(cur->_left);
    			_PostOrder(cur->_right);
    			cout<<cur->_data<<" ";
    		}
    	}
    	void _LevelOrder(Node *root)
    	{
    		queue<Node *> q;
    		Node *cur=root;
    		q.push(cur);
    		while(!q.empty())
    		{
    			Node *front=q.front();
    			cout<<front->_data<<" ";
    			if (front->_left != NULL)
    				q.push(front->_left);
    			if (front->_right != NULL)
    				q.push(front->_right);
    			q.pop();
    		}
    	}
    	方法一.
    	//size_t _Size(Node *root)
    	//{
    	//	if (root == NULL)
    	//	{
    	//		return 0;     //空树
    	//	}
    	//	return 1+_Size(root->_left)+_Size(root->_right);
    	//}
    	//方法二.
    	size_t _Size(Node *root)
    	{
    		static size_t count=0;
    		if (root == NULL)
    			return 0;
    		count++;        //类似前序遍历.
    		_Size(root->_left);
    		_Size(root->_right);
    		return count;
    	}
    	size_t _Depth(Node *root)
    	{
    		Node *cur=root;
    		if (root == NULL)
    			return 0;
    		size_t depth1=_Depth(cur->_left)+1;
    		size_t depth2=_Depth(cur->_right)+1;
    		return depth1>depth2?depth1:depth2;
    	}
    	size_t _LeafSize(Node *root)
    	{
    		Node *cur=root;
    		if (cur == NULL)   //空树
    			return 0;
    		else if ((cur->_left == NULL) && (cur->_right == NULL))
    			//叶子结点--一个结点即没有左子树也没有右子树
    			return 1;
    		else
    			return _LeafSize(cur->_left)+_LeafSize(cur->_right);
    	}
    	size_t _GetKLevel(Node *root,int level)
    	{
    		size_t count=0;
    		if (root == NULL)
    			return 0;
    		if (level == 1)
    			count++;
    		else
    		{
    			count += _GetKLevel(root->_left,level-1);
    			count += _GetKLevel(root->_right,level-1);
    		}
    		return count;
    	}
    	Node *_FindNode(Node *root,const T& x)
    	{
    		if (root == NULL)
    			return NULL;
    		if(root->_data == x)
    			return root;
    		Node *ret=_FindNode(root->_left,x);
    		//当在当前结点的左子树中未找到该结点去右子树找
    		if (ret == NULL)
    		{
    			ret=_FindNode(root->_right,x);
    		}
    		return ret;
    	}
    protected:
    	Node *_root;
    };

test.cpp

void test1()
    {
    	int array[]={1,2,3,'#','#',4,'#','#',5,6};
    	size_t size=sizeof(array)/sizeof(array[0]);
    	BinaryTree<int> bt(array,size,'#');
    	cout<<"前序遍历>";
    	bt.PrevOrderNoR();   //1  2  3  4  5  6
    	cout<<"中序遍历>";
    	bt.InOrderNoR();     //3  2  4  1  6  5
    	cout<<"后序遍历>";
    	bt.PostOrderNoR();   //3  4  2  6  5  1
    	cout<<"层序遍历>";
    	bt.LevelOrder();     //1  2  5  3  4  6
    	cout<<"Size>"<<bt.Size()<<endl;
    	cout<<"Depth:"<<bt.Depth()<<endl;
    	cout<<"LeafSize:"<<bt.LeafSize()<<endl;   //3  
    	cout<<"Level1:"<<bt.GetKLevel(1)<<endl;  //1
    	cout<<"Level2:"<<bt.GetKLevel(2)<<endl;  //2
    	cout<<"Level3:"<<bt.GetKLevel(3)<<endl; //3
    
    	BinaryTreeNode<int> *ret=bt.FindNode(6);
    	assert(ret);
    	cout<<"FindNode:6>"<<ret->_data<<endl;    //找到.
    	ret=bt.FindNode(10);
    	cout<<"FindeNode:10>"<<ret<<endl;         //没找到.
    }

## 结果展示> ##

![Center 1][]

[Center]: /images/20220716/18ca489006844827b7934d295cf9035a.png
[Center 1]: /images/20220716/ddbe075108b947899b9faff9a1f85b2c.png