二叉树的操作

待我称王封你为后i 2022-03-28 07:45 192阅读 0赞

问题：再一次验证自己功底的薄弱，对那些大侠只有仰慕的份。。。

简单说一下自己的感受，递归的实现是个栈，每次函数结束时，退回到上一层，函数结束默认为return。

二叉树的各种非递归实现用到的数据结构是栈。

这次用重温了STL中stack的用法。

代码：

#include <iostream>
    #include <cstdlib>
    #include <stack>
    using namespace std;
    
    typedef struct node
    {
    	char data;
    	struct node *left;
    	struct node *right;
    }*BinTree;
    
    void CreateBTree(BinTree &btree)            //建立二叉树
    {
    	char c;
    	btree=(BinTree)malloc(sizeof(struct node));
    	cin>>c;
    	if(!btree)
    	{
    		cout<<"allocated fail"<<endl;
    		exit(-1);
    	}
    	if(c!='#')
    	{
    		btree->data=c;
    		CreateBTree(btree->left);
    		CreateBTree(btree->right);
    	}
    	else
    	{
    		btree=NULL;
    	}
    
    }
    void showBTree(BinTree btree)   //递归前序遍历二叉树
    {
    	if(btree)
    	{
    		cout<<btree->data<<" ";
    		showBTree(btree->left);
    		showBTree(btree->right);
    	}
    }
    void inOrderBTree(BinTree btree)  //递归中序遍历二叉树
    {
    	if(btree)
    	{
    		inOrderBTree(btree->left);
    		cout<<btree->data<<" ";
    		inOrderBTree(btree->right);
    
    	}
    }
    
    void postOrderBTree(BinTree btree)  //递归后续遍历二叉树
    {
    	if(btree)
    	{
    		postOrderBTree(btree->left);
    		postOrderBTree(btree->right);
    		cout<<btree->data<<" ";
    	}
    }
    
    void displayBTree(BinTree btree)   //非递归前序遍历二叉树
    {
    	stack<BinTree> q;
    	if(btree)
    	{
    	BinTree bt;
    	q.push(btree);
    	while(!q.empty())
    	{
    		while(bt=q.top())
    		{
    			cout<<bt->data<<" ";
    			q.push(bt->left);
    		}
    		q.pop();
    		if(!q.empty())
    		{
    			bt=q.top();
    			q.pop();
    			q.push(bt->right);
    		}
    	}
    	}
        
    }
    
    void iOrder(BinTree btree)  //中序非递归遍历
    {
    	BinTree bt=NULL;
    	stack<BinTree> s;
    	s.push(btree);
    	while(!s.empty())
    	{
    		while(bt=s.top())
    		{
    			s.push(bt->left);
    		}
    		s.pop();
    		if(!s.empty())
    		{
    			bt=s.top();
    			cout<<bt->data<<" ";
    			s.pop();
    			s.push(bt->right);
    		}
    	}
    
    }
    
    void pOrder(BinTree btree)
    {
    	stack<BinTree> s;
    	BinTree cur=NULL;
    	BinTree pre=NULL;
    	s.push(btree);
    	while(!s.empty())
    	{
    		cur=s.top();
    		if((cur->left==NULL&&cur->right==NULL)||(pre!=NULL&&(pre==cur->left||pre==cur->right)))
    		{
    			cout<<cur->data<<" ";
    			s.pop();
    			pre=cur;
    		}
    		else
    		{
    			if(cur->right)
    				s.push(cur->right);
    			if(cur->left)
    				s.push(cur->left);		
    		}
    	}
    }
    
    int main()
    {
    	BinTree bt;
    	cout<<"create bintree:"<<endl;
    	CreateBTree(bt);
    
    	cout<<"前序遍历二叉树:"<<endl;
    	showBTree(bt);
    	cout<<endl;
    	cout<<"前序非递归遍历:"<<endl;
    	displayBTree(bt);
    	cout<<endl;
    
    	cout<<"中序遍历二叉树:"<<endl;
    	inOrderBTree(bt);
    	cout<<endl;
    	cout<<"中序非递归遍历二叉树："<<endl;
    	iOrder(bt);
    	cout<<endl;
    
    	cout<<"后序遍历二叉树："<<endl;
    	postOrderBTree(bt);
    	cout<<endl;
    	cout<<"后序非递归遍历:"<<endl;
    	pOrder(bt);
    	cout<<endl;
    	return 0;
    }

运行结果:

![30104144-b77a3662a3dc4becb77050cbc61c44a9.png][]

[30104144-b77a3662a3dc4becb77050cbc61c44a9.png]: /images/20220328/92b4040029cd4fa78ef3a562f8275ef7.png