编写一个程序，实现二叉树的各种运算

╰+攻爆jí腚メ 2022-05-19 05:15 44阅读 0赞

来源：[https://blog.csdn.net/u012651730/article/details/16830071][https_blog.csdn.net_u012651730_article_details_16830071]

（1）输出二叉树b；

（2）输出H节点的左右孩子节点值；

（3）输出二叉树b的深度；

（4）输出二叉树b的宽度；

（5）输出二叉树b的节点个数；

（6）输出二叉树b的叶子节点

#include"iostream"
    #include"queue"
    #define maxsize 50
    using namespace std;
    class node{
    private:
    	char data;
    	node* lchild;
    	node* rchild;
    	static int i;
    	static int m;
    public:
    	void createnode(node *&,char *);
    	bool childnode(node *,char);
    	int nodeheight(node *);
    	int nodewidth(node *);
    	void displeaf(node *);
    	void disnode(node *);
    	int geti(){ return i; }//二叉树叶子节点个数
    	int getm(){ return m; }//二叉树节点个数
    };
     
    int node::i=0;
    int node::m=0;
     
    //建立二叉树
    void node::createnode(node* &b,char* a){
    	node *st[maxsize],*p;
    	int top=-1,k,j=0;
    	char ch;
    	b=NULL;
    	ch=a[j];
    	while(ch!='\0')
    	{
    		switch(ch)
    		{
    		case '(':
    			top++;
    			st[top]=p;
    			k=1;
    			break;
    		case ')':
    			top--;
    			break;
    		case ',':
    			k=2;
    			break;
    		default:
    			p=new node;
    			p->data=ch;
    			m++;
    			p->lchild=p->rchild=NULL;
    			if(b==NULL){
    				b=p;
    			}
    			else{
    				switch(k)
    				{
    				case 1:
    					st[top]->lchild=p;
    					break;
    				case 2:
    					st[top]->rchild=p;
    					break;
    				}
    			}
    		}
    		j++;
    		ch=a[j];
    	}
    }
     
    //某节点的左右孩子节点值
    bool node::childnode(node* b,char x)
    {
    	if(b==NULL)
    		return false;
    	else if(b->data==x)
    	{
    		cout << x << "节点的左孩子节点值： " << b->lchild->data << endl ;
    		cout << x << "节点的右孩子节点值： " << b->rchild->data << endl ;
    		return true;
    	}
    	else
    	{
    		childnode(b->lchild,x);
    		childnode(b->rchild,x);
    	}
    	return true;
    }
     
    //二叉树的宽度
    int node::nodewidth(node* b)
    {
    	if(b==NULL)
    		return 0;
    	int lastwidth=0;
    	int tempwidth=0;
    	int nowwidth=0;
    	int width=0;
    	queue<node* > myqueue;
    	myqueue.push(b);
    	lastwidth=1;
    	node* a=NULL;
    	while(!myqueue.empty())
    	{
    		tempwidth=lastwidth;
    		while(tempwidth!=0)
    		{
    			a=myqueue.front();
    			myqueue.pop();
    			if(a->lchild!=NULL)
    			{
    				myqueue.push(a->lchild);
     
    			}
    			if(a->rchild!=NULL)
    			{
    				myqueue.push(a->rchild);
    			}
    			tempwidth--;
    		}
    		nowwidth=myqueue.size();
    		width=nowwidth>width?nowwidth:width;
    		lastwidth=nowwidth;
    	}
    	return width;
    }
     
    //二叉树的高度
    int node::nodeheight(node* b)
    {
    	int lchildh=0,rchildh=0;
    	if(b==NULL)
    		return 0;
    	else
    	{
    		lchildh=nodeheight(b->lchild);
    		rchildh=nodeheight(b->rchild);
    		return (lchildh>rchildh?(lchildh+1):(rchildh+1));
    	}
    }
     
    //二叉树叶子节点个数
    void node::displeaf(node* b)
    {
    	if(b!=NULL)
    	{
    		if(b->lchild==NULL&&b->rchild==NULL)
    			i++;
    		displeaf(b->lchild);
    		displeaf(b->rchild);
    	}
    }
     
    //输出二叉树
    void node::disnode(node* b)
    {
    	if(b!=NULL)
    	{
    		cout << b->data ;
    		if(b->lchild!=NULL||b->rchild!=NULL)
    		{
    			cout << "(" ;
    			disnode(b->lchild);
    			if(b->rchild!=NULL)
    				cout << "," ;
    			disnode(b->rchild);
    			cout << ")" ;
    		}
    	}
    }
     
    void main()
    {
    	node *b;
    	char a[]="A(B(D,E(H(J,K(L,M(,N))),)),C(F,G(,I)))";
    	b->createnode(b,a);
    	b->childnode(b,'H');
    	cout << "二叉树b的深度：" << b->nodeheight(b) << endl ;
    	cout << "二叉树b的宽度：" << b->nodewidth(b) << endl ;
    	b->displeaf(b);
    	cout << "树的节点个数：  " << b->getm() << endl;
    	cout << "树的叶子节点个数：  " << b->geti() << endl ;
    	b->disnode(b);
    	cout << endl ;
    }

个数。

代码

[https_blog.csdn.net_u012651730_article_details_16830071]: https://blog.csdn.net/u012651730/article/details/16830071