数据结构实验报告第四个二叉树相关操作

柔光的暖阳◎ 2022-08-06 04:27 153阅读 0赞

#include<iostream>
    #define M 5//定义一个M，用来判断栈大小的
    using namespace std;
    int sum=0;//sum这个变量用来统计叶子结点个数
    
    typedef struct BTtree//定义二叉树结构体
    {
    	char data;
    	struct BTtree * Lchild;
    	struct BTtree * Rchild;
    }BT,*pBT;
    
    pBT createTree()//链式手动创建结点
    {
    	pBT head = new BT;   
    	pBT bNode = new BT;
    	pBT cNode = new BT;
    	pBT dNode = new BT;
    	pBT eNode = new BT;
    
    	head->Lchild = bNode;
    	head->Rchild = cNode;
    	head->data ='A';
    	bNode->Lchild = bNode->Rchild = NULL;
    	bNode->data = 'B';
    	cNode->Rchild = dNode;
    	cNode->Lchild = NULL;
    	cNode->data = 'C';
    	dNode->Rchild = NULL;
    	dNode->Lchild = eNode;
    	dNode->data = 'D';
    	eNode->Lchild = eNode->Rchild = NULL;
    	eNode->data = 'E';
    	return head;
    }
    
    void preOrder(pBT root)//前序遍历
    {
    	pBT s[M];
    	int top =0;
    	pBT p = root;
    	
    	do{
    			
    			while(p!=NULL)
    			{
    				if(top>M) 
    					return;
    				top++;
    				s[top]=p;
    				cout<<p->data<<endl;
    				p=p->Lchild;
    			}
    			
    			if(top!=0)
    			{
    				p=s[top];
    				top--;
    				if(p->Lchild==NULL && p->Rchild==NULL)//如果结点左右子树都为空，则这个结点为叶子结点
    					sum++;//用来统计叶子结点的sum变量加1
    				p=p->Rchild;
    			}
    	
    	}while(p!=NULL || top!=0);
    
    }
    
    void inOrder(pBT root)//非递归中序遍历
    {
    	pBT s[M];
    	int top =0;
    	pBT p = root;
    	
    	do{
    			while(p!=NULL)
    			{
    				if(top>M) 
    					return;
    				top++;
    				s[top]=p;
    				p=p->Lchild;
    			}
    			
    			if(top!=0)
    			{
    				p=s[top];
    				top--;
    				cout<<p->data<<endl; 
    				p=p->Rchild;
    			}
    		
    	
    	}while(p!=NULL || top!=0);
    
    }
    
    void postOrder(pBT root)//递归后序遍历
    {
    	if(NULL!=root)
    	{
    		postOrder(root->Lchild);
    		
    		if(NULL != root->Rchild)
    			postOrder(root->Rchild);
    		cout<<root->data<<endl;
    	}
    }
    void changefun(pBT root)//左右子树交换
    {
    	pBT s[M];
    	pBT t;
    	int top =0;
    	pBT p = root;
    	
    	do{
    			if(p!=NULL)
    			{
    				if(top>M) 
    					return;
    				top++;
    				s[top]=p;
    				p=p->Lchild;
    			}
    			else
    			{
    				p=s[top];
    				top--;
    				t=p->Rchild;
    				p->Rchild=p->Lchild;
    				p->Lchild=t;
    				p = p->Lchild;
    			}
    		
    	
    	}while(p!=NULL || top!=0);
    
    }
    
    void main()
    {
    	pBT Root = createTree();m
    	cout<<"------preOrder--------------"<<endl;
    	preOrder(Root);
    	cout<<"------inOrder---------------"<<endl;
    	inOrder(Root);
    	cout<<"------postOrder----------------"<<endl;
    	postOrder(Root);
    
    	cout<<"-------------change-------"<<endl;
    	changefun(Root);//调用左右子树交换函数
    	cout<<"----countleaf--"<<endl;
    	cout<<"count: "<<sum<<endl;//输出叶子结点个数
    }