精华内容
下载资源
问答
  • (验证性实验)实现二叉树的各种基本运算的算法 编写一个程序btree.cpp, 实现二叉树基本运算,并在此基础上设计一个程序exp5-1.cpp,完成如下功能。由图所示的二叉树创建对应的二叉链存储结构b,叉树的括号表示串为...

    (验证性实验)实现二叉树的各种基本运算的算法 编写一个程序btree.cpp, 实现二叉树基本运算,并在此基础上设计一个程序exp5-1.cpp,完成如下功能。由图所示的二叉树创建对应的二叉链存储结构b,叉树的括号表示串为“A(B(D,E(H(J,K(L,M(,N))))),C(,I)))”输出二叉树b输出‘H’结点的左、右孩子结点值输出二叉树b的高度释放二叉树b

    代码如下
    btree

    //二叉树的基本运算算法
    #include <stdio.h>
    #include <malloc.h>
    #define MaxSize 100
    typedef char ElemType;
    typedef struct node 
    {ElemType data;			//数据元素	
    struct node *lchild;	//指向左孩子节点	
    struct node *rchild;	//指向右孩子节点
    } BTNode;
    void CreateBTree(BTNode * &b,char *str)	
    //创建二叉树
    {	
    BTNode *St[MaxSize],*p=NULL;	
    int top=-1,k,j=0;  	char ch;	b=NULL;				//建立的二叉树初始时为空	
    ch=str[j];	while (ch!='\0')  	//str未扫描完时循环	
    {   	   	
    switch(ch) 		
    {		
    case '(':top++;St[top]=p;k=1; break;		//为左孩子节点		
    case ')':top--;break;		
    case ',':k=2; break;                      		//为孩子节点右节点		
    default:p=(BTNode *)malloc(sizeof(BTNode));				p->data=ch;p->lchild=p->rchild=NULL;				if (b==NULL)                    	 	//*p为二叉树的根节点					
    b=p;				else  								//已建立二叉树根节点				
    {						switch(k) 					{					case 1:St[top]->lchild=p;break;					case 2:St[top]->rchild=p;break;					}				}		}		j++;		ch=str[j];	}}void DestroyBTree(BTNode *&b){	if (b!=NULL)	{	DestroyBTree(b->lchild);		DestroyBTree(b->rchild);		free(b);	}}BTNode *FindNode(BTNode *b,ElemType x) {	BTNode *p;	if (b==NULL)		return NULL;	else if (b->data==x)		return b;	else  	{		p=FindNode(b->lchild,x);		if (p!=NULL) 			return p;		else 			return FindNode(b->rchild,x);	}}BTNode *LchildNode(BTNode *p){    return p->lchild;}BTNode *RchildNode(BTNode *p){    return p->rchild;}int BTHeight(BTNode *b) {   	int lchildh,rchildh;   	if (b==NULL) return(0); 				//空树的高度为0   	
    else  	{		lchildh=BTHeight(b->lchild);	//求左子树的高度为
    lchildh		rchildh=BTHeight(b->rchild);	//求右子树的高度为
    rchildh		return (lchildh>rchildh)? (lchildh+1):(rchildh+1);   	}}void DispBTree(BTNode *b) {	if (b!=NULL)	{	printf("%c",b->data);		if (b->lchild!=NULL || b->rchild!=NULL)		{	printf("(");						//有孩子节点时才输出
    (DispBTree(b->lchild);//递归处理左子树			
    if (b->rchild!=NULL) printf(",");//有右孩子节点时才输出,			
    DispBTree(b->rchild);//递归处理右子树			
    printf(")");//有孩子节点时才输出)		
    }	}}
    

    exp5-1.cpp

    #include "btree.cpp"
     main()
    {
    	BTNode *b;
    	int height;
    	printf("(1)二叉树创建\n");
    	CreateBTree(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I))");//二叉树创建
    	printf("(2)输出二叉树\n");
       DispBTree(b);
       	printf("\n");
    	printf("(3)H结点的左孩子结点值:%c\n",LchildNode(FindNode(b,'H'))->data);
    	printf("H结点的右孩子结点值:%c\n",RchildNode(FindNode(b,'H'))->data);
       height=BTHeight(b);
      printf("(4)二叉树b的高度 %d\n",height);
        printf("(5)释放二叉树b\n");
    	 DestroyBTree(b);
    }
    
    展开全文
  • 数据结构课程设计:二叉树的基本运算...编写一个程序实现二叉树的基本功能:            1、用户输入字符串创建二叉树:A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I))

    数据结构课程设计:二叉树的基本运算实现:
           编写一个程序实现二叉树的基本功能:
               1、用户输入字符串创建二叉树:A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))  并允许用户以括号表示法自行输入二叉树
                2、实现二叉树的先序遍历、中序遍历、后序遍历的递归和非递归算法、以及层次遍历。
                3、要求能查找任一结点在某种遍历序列中的前驱和后继。
                4、查找输出从根结点A出发到任意指定结点的路径。
                5、查找任意一个结点为根的子树所有结点。

    界面如图:
    初始界面
    功能菜单

    功能展示

    1.前期准备及结点、基本运算编写

    #include<iostream>
    #include<stdlib.h>
    #include<cstring>
    using namespace std;
    #define ElemType char
    #define MaxSize 100										//二叉树的最大长度 
    #define st_MaxSize 30									//栈的最大长度 
    #define qu_MaxSize 30									//队列的最大长度 
    
    
    						  /*关于结点的声明*/
    typedef struct node										//定义二叉树的结点类型BTNode 
    {									
    	ElemType data;
    	struct node* lchild;
    	struct node* rchild;
    	int ltag,rtag;										//用于标记左右结点是否为空,构建线索二叉树时用 
    		
    }BTNode;
    
    typedef struct											//定义顺序栈的结点类型 
    {
    	BTNode* data[st_MaxSize];							//存放栈中的二叉结点元素 
    	int top;											//栈顶指针 
    }SqStack; 
    
    typedef struct											//定义顺序队列的结点类型 
    {
    	BTNode* data[qu_MaxSize];							//定义一个结点数组 
    	int front,rear;										//队首队尾结点 
    } SqQueue;
    
    
    
    						/*关于顺序栈操作的声明*/
    void InitStack(SqStack* &s)								//初始化栈 
    {
    	s=(SqStack*)malloc(sizeof(SqStack));				//分配一个顺序栈空间,首地址存放在s中 
    	s->top=-1;											//栈顶指针置为-1 
    }
    
    void DestroyStack(SqStack* &s)							//销毁顺序栈 
    {
    	free(s);	
    } 
    
    bool StackEmpty(SqStack* s)								//判断栈是否为空
    {
    	return(s->top==-1);	
    }
    
    bool Push(SqStack* &s,BTNode* e)						//入栈 
    {
    	if(s->top==st_MaxSize-1)
    		return false;
    	s->data[++s->top]=e;
    	return true;
    }
    
    bool Pop(SqStack* &s,BTNode* &e)						//出栈 
    {
    	if(s->top==-1)
    		return false;
    	e=s->data[s->top--];
    	return true;
    }
    
    bool GetTop(SqStack* s,BTNode* &e)						//取栈顶元素 
    {
    	if(s->top==-1)
    		return false;
    	e=s->data[s->top];
    	return true;
    }
    
    
    						/*关于环形队列操作的声明*/
    void InitQueue(SqQueue* &q)										//初始化环形队列 
    {
    	q=(SqQueue*)malloc(sizeof(SqQueue));
    	q->front=q->rear=0;	
    } 
    
    void DestroyQueue(SqQueue* &q)									//销毁环形队列 
    {
    	free(q);	
    }
    
    bool QueueEmpty(SqQueue* q)										//判断环形队列是否为空 
    {
    	return (q->front==q->rear);									
    }
    
    bool enQueue(SqQueue* &q,BTNode* &e)							//入队操作 
    {
    	if((q->rear+1)%qu_MaxSize==q->front)
    		return false;
    	q->rear=(q->rear+1)%qu_MaxSize;
    	q->data[q->rear]=e;
    	return true;
    }
    				
    bool deQueue(SqQueue* &q,BTNode* &e)
    {
    	if(q->front==q->rear)
    		return false;
    	q->front=(q->front+1)%qu_MaxSize;
    	e=q->data[q->front];
    	return true;	
    }
    

    2. 二叉树的运算

    					/*关于二叉树操作的声明*/
    void CreateBTree(BTNode* &b,char* str)					//创建二叉树 
    {
    	BTNode* St[MaxSize];
    	BTNode* p;											//用于创建结点,然后接到树上 
    	int top=-1;											//初始化栈顶指针 
    	int k=0;											//用于标明操作左孩子结点还是右孩子结点的flag 
    	int j=0;											//用于遍历字符串 
    	char ch;											//用于遍历给定字符串的字符参数 
    	b=NULL;												//先将根结点初始化为空结点 
    	ch=str[j];											//指遍历参数指向开头,准备遍历
    	
    	while(ch!='\0')										//开始遍历字符串
    	{
    		switch(ch)
    		{
    			case '(':									//遍历到左括号 
    				top++;						
    				St[top]=p;								//结点入栈,作为子树的根结点 
    				k=1;									//k=1:准备创建左孩子结点 
    				break;
    			
    			case ')':									//遍历到右括号 
    				top--;									//元素出栈 
    				break;
    			
    			case ',':									//有逗号说明有右孩子结点不为空,准备创建右孩子结点 
    				k=2;
    				break;
    			
    			default:
    				p=(BTNode*)malloc(sizeof(BTNode));		//为p创建一个新的空结点 
    				p->data=ch; 							//在新结点中存入数据 
    				p->lchild=p->rchild=NULL;				//将左右结点首先设为空结点 
    				if(b==NULL)								//若操作的是树的根结点 
    					b=p;
    				else 									//若操作的不是树的根结点 
    				{
    					switch(k)							//判断标明操作左右孩子结点的flag 
    					{
    						case 1:							//k=1,新建的结点为0 
    							St[top]->lchild=p;
    							break;
    						
    						case 2:
    							St[top]->rchild=p;
    							break;
    					}
    				}	
    		} 
    		ch=str[++j];							 		//继续遍历str字符串 
    	} 
    }
    
    void RPreOrder(BTNode* b)								//先序遍历递归输出 
    {
    	if(b!=NULL)
    	{
    		cout<<b->data<<" ";									//输出根结点数据 
    		RPreOrder(b->lchild);							//递归遍历左树 
    		RPreOrder(b->rchild);							//递归遍历右树 
    	}
    }
    
    void RInOrder(BTNode* b)								//中序遍历递归输出 
    {
    	if(b!=NULL)
    	{
    		RInOrder(b->lchild);							//递归遍历左树 
    		cout<<b->data<<" ";									//输出根结点的数据 
    		RInOrder(b->rchild);							//递归遍历右树 
    	}
    }
    
    void RPostOrder(BTNode* b)								//后序遍历递归输出 
    {
    	if(b!=NULL)
    	{
    		RPostOrder(b->lchild);							//递归遍历左树 
    		RPostOrder(b->rchild);							//递归遍历右树 
    		cout<<b->data<<" ";								//输出根结点的数据 
    	}
    }
    
    void NPreOrder(BTNode* b)								//先序遍历非递归输出(第一种方法) 
    {
    	BTNode* p;
    	SqStack *st;										//声明一个顺序栈
    	InitStack(st);										//初始化栈st
    	p=b;
    	while(!StackEmpty(st)||p!=NULL)						//当栈不为空,且未输出完所有的叶子结点 
    	{
    		while(p!=NULL)									//一路向左,把所有左下结点入栈 
    		{
    			cout<<p->data<<" ";							//输出根结点 
    			Push(st,p);									//然后将根结点的左孩子结点入栈 
    			p=p->lchild; 
    		} 
    		
    		if(!StackEmpty(st))
    		{
    			Pop(st,p);									//出栈结点p, 
    			p=p->rchild;								//然后将右孩子结点入栈,进而循环遍历右子树 
    		}
    	}
    	DestroyStack(st);
    }
    
    void NPreOrder2(BTNode* b)								//先序遍历非递归输出(第二种方法)
    { 
    	BTNode* p;
    	SqStack *st;										//声明一个顺序栈
    	InitStack(st);										//初始化栈st
    	if(b!=NULL)
    	{
    		Push(st,b);										//根结点入栈
    		while(!StackEmpty(st))							//栈不空时循环 
    		{
    			Pop(st,p);									//出栈结点p并访问
    			cout<<p->data<<" ";
    			
    			/*先进后出,所以先入栈右孩子*/ 
    			if(p->rchild!=NULL)
    				Push(st,p->rchild);						//有右孩子时将其入栈	
    			if(p->lchild!=NULL)
    				Push(st,p->lchild);						//有左孩子时将其出栈  
    		}
    	}
    	DestroyStack(st);									//销毁栈 
    }
    
     
    void NInOrder(BTNode* b)								//中序遍历非递归输出 
    {
    	BTNode* p;
    	SqStack *st;										//声明一个顺序栈
    	InitStack(st);										//初始化栈st
    	p=b;
    	while(!StackEmpty(st)||p!=NULL)						//当栈不为空,且未输出完所有的叶子结点 
    	{
    		while(p!=NULL)									//一路向左,把所有左下结点入栈 
    		{
    			Push(st,p);
    			p=p->lchild;							
    		}
    		
    		if(!StackEmpty(st))								//当栈不为空时 
    		{
    			Pop(st,p);									//出栈结点p
    			cout<<p->data<<" ";								//输出p 
    		
    		/*至此,完成了最小子树的左孩子的输出和子根的输出,转而处理右子树*/
    			p=p->rchild;								//转而处右子树 
    		}
    	}
    	DestroyStack(st); 
    }
    
    void NPostOrder(BTNode* b)								//后序遍历非递归输出 
    {
    	BTNode* p;
    	BTNode* r;
    	bool flag;
    	SqStack* st;										//定义一个顺序栈指针st 
    	InitStack(st);										//初始化栈 
    	p=b;
    	do
    	{
    		while(p!=NULL)									//一路向左,把所有左下结点入栈 
    		{
    			Push(st,p);
    			p=p->lchild;	
    		}	
    		r=NULL;											//r指向刚访问的结点,初始时为空 
    		flag=true;										//flag为真表示正在处理栈顶结点 
    		while(!StackEmpty(st)&&flag)					//当栈不为空且即将处理栈顶结点 
    		{
    			GetTop(st,p);								//取出当前的栈顶结点p
    			if(p->rchild==r)							//若结点p的右孩子结点为空或为刚刚访问过的结点 
    			{
    				cout<<p->data<<" ";							//输出该根结点p
    				Pop(st,p);
    				r=p;									//r指向刚刚访问过的结点 
    			}
    			else
    			{
    				p=p->rchild;							//转向处理右子树
    				flag=false;								//表示现在不是在处理栈顶结点	
    			}		
    		}
    	}while(!StackEmpty(st));
    	DestroyStack(st);									//销毁栈 
    }
    
    void LevelOrder(BTNode* b)								//层次遍历算法
    {
    	BTNode* p;
    	SqQueue* qu;
    	InitQueue(qu);
    	enQueue(qu,b);
    	while(!QueueEmpty(qu))
    	{
    		deQueue(qu,p);
    		cout<<p->data<<" ";
    		if(p->lchild!=NULL)
    			enQueue(qu,p->lchild);
    		if(p->rchild!=NULL)
    			enQueue(qu,p->rchild);
    	}
    }
    
    BTNode* FindNode(BTNode* b,ElemType x)					//查找二叉树b中值为x的结点 
    {
    	BTNode* p;
    	if(b==NULL)
    		return NULL;									//若树或子树为空,直接返回NULL			
    	else if(b->data==x)
    		return b;										//若根结点或子根结点就是要找的结点,返回该(子)根结点 
    	else
    	{
    		p=FindNode(b->lchild,x);						//查找左树 
    		if(p!=NULL)
    			return p;									//若左树未搜索到,不一定没有,要转而搜索右树 
    		else 
    			return FindNode(b->rchild,x);				//若右树未搜索到,那就是真的没有了,所以不需要判断NULL的情况了 
    	}
    } 
    
    BTNode* pre;											//用于线索化二叉树的全局变量
    
    void Thread(BTNode* &p)									//将头结点为p的二叉树进行中序线索化 
    {
    	if(p!=NULL)
    	{
    		Thread(p->lchild);								//将左子树线索化
    		if(p->lchild==NULL)								//左孩子不存在时,进行前驱结点线索化 
    		{
    			p->lchild=pre;
    			p->ltag=1;	
    		}
    		else
    			p->ltag=0;
    		
    		if(pre->rchild==NULL)
    		{
    			pre->rchild=p;
    			pre->rtag=1;	
    		}
    		else
    			pre->rtag=0;	
    		pre=p;
    		Thread(p->rchild);								//右子树线索化 
    	}		
    } 
    
    BTNode* CreateThread(BTNode* b)							//将二叉树b进行中序线索化 
    {									 
    	BTNode* root;										//创建指向根结点b的指针root 
    	root=(BTNode*)malloc(sizeof(BTNode));
    	root->ltag=0;										//root有左孩子结点,ltag设为0 
    	root->rtag=1;										//root无右孩子结点,rtag设为1 
    	root->rchild=b;										//右孩子结点指向后继结点,即根结点b 
    	if(b==NULL)											//空二叉树时 
    		root->lchild=root;								//root的前驱结点就是自己
    	else
    	{
    		root->lchild=b;
    		pre=root;										//pre是p的前驱结点,供加线索用 
    		Thread(b);										//中序遍历线索化二叉树
    		pre->rchild=root;
    		pre->rtag=1;
    		root->rchild=pre;								//将头结点右线索化 
    	} 
    	return root; 
    	 
    }
    
    BTNode* InPrenode(BTNode* p)							//查找中序线索二叉树的前驱 
    {
    	BTNode* Pre;
    	Pre=p->lchild;
    	if(p->ltag!=1)
    		while(Pre->rtag==0)
    			Pre=Pre->rchild;
    	return (Pre); 
    } 
    
    BTNode* InPostnode(BTNode* p)							//查找中序线索二叉树的后继 
    {
    	BTNode* Post;
    	Post=p->rchild;
    	if(p->rtag!=1)
    		while(Post->ltag==0)
    			Post=Post->lchild;
    	
    	return(Post);
    }
    
    bool PathStack(BTNode* b,SqStack* &st,BTNode* x)			//将从根结点到某结点的路线入栈 
    {
    	if(b==NULL)
    		return false;
    	Push(st,b);											//将根结点入栈 
    	if(b==x)
    		return 	true;
    	bool temp=false;
    	if(b->lchild!=NULL)									//先查找左子树 
    		temp=PathStack(b->lchild,st,x);
    	if(!temp&&b->rchild!=NULL)							//左子树未找到且右子树不为空时,查找右子树 
    		temp=PathStack(b->rchild,st,x);
    	
    	if(!temp)												//左右都找不到,栈顶元素出栈 
    	{
    		BTNode* ab;										//用来舍弃的工具变量 
    		Pop(st,ab);
    	}
    	return temp;
    		
    }
    
    void SearchPath(BTNode* b,BTNode* x)
    {
    	SqStack* nst;											//创建并初始化第一个栈 
    	InitStack(nst);
    	PathStack(b,nst,x);										//将路径填写到第一个栈中,不过此时路径是反向的 
     	SqStack* pst;											//创建并初始化第二个栈 
    	InitStack(pst);				
    	BTNode* trans; 											//用于把路径从第一个栈搬到第二个栈的搬运变量 
    	while(!StackEmpty(nst))									//把第一个栈的路径搬到第二个栈里:此时路径从反向变成正向 
    	{														
    		Pop(nst,trans);
    		Push(pst,trans);
    	}	
    	BTNode* out;
    	while(!StackEmpty(pst))									//然后把第二个栈输出 
    	{
    		Pop(pst,out);
    		cout<<out->data<<" ";
    	}
    } 
    
    	BTNode* b;													//声明根结点 
    	char a[MaxSize]="A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))";			//默认的二叉树 
    	char se_le;													//用于后续的结点值输入 
    	BTNode* se;													//用于存放搜索到的结点 
    	BTNode* h;													//用于构建线索二叉树 
    
    

    3.菜单函数及主函数的编写

    bool Out()
    {		
    	cout<<	"\n\n\t功能菜单:\n" 
    			"\n\t\t1.实现二叉树的先序遍历(递归)\n"
    			"\n\t\t2.实现二叉树的先序遍历(非递归法1)\n"
    			"\n\t\t3.实现二叉树的先序遍历(非递归法2)\n"
    			"\n\t\t4.实现二叉树的中序遍历(递归)\n"
    			"\n\t\t5.实现二叉树的中序遍历(非递归)\n"
    			"\n\t\t6.实现二叉树的后序遍历(递归)\n"
    			"\n\t\t7.实现二叉树的后序遍历(非递归)\n"
    			"\n\t\t8.实现二叉树的层次遍历\n"
    			"\n\t\t9.查找任意结点在中序遍历中的前驱和后继\n"
    			"\n\t\t10.查找输出从根结点A出发到任意指定结点的路径\n" 
    			"\n\t\t11.查找任意一个结点为根的子树所有结点。\n"
    			"\n\t\t12.退出\n"
    			"\n\t 请输入功能编号:";
    	int choice;
    	cin>>choice;
    	switch(choice)
    	{
    		case 1:
    			cout<<"\n\n\t二叉树的递归先序遍历如下:\n\t\t";
    			RPreOrder(b);
    			cout<<endl;
    			system("pause"); 
    			cout<<endl<<endl;
    			Out();
    			cout<<endl<<endl;
    			break;
    		
    		case 2:
    			cout<<"\n\n\t二叉树的第一种非递归先序遍历如下:\n\t\t";
    			NPreOrder(b);
    			cout<<endl;
    			system("pause"); 
    			cout<<endl<<endl;
    			Out();
    			cout<<endl<<endl<<endl;
    			break;
    			
    		case 3:
    			cout<<"\n\n\t二叉树的第二种非递归先序遍历如下:\n\t\t";
    			NPreOrder2(b);
    			cout<<endl;
    			system("pause"); 
    			cout<<endl<<endl<<endl;
    			Out();
    			cout<<endl<<endl;
    			break;
    		
    		case 4:
    			cout<<"\n\t\t二叉树的递归中序遍历如下:\n\t\t";
    			RInOrder(b);
    			cout<<endl;
    			system("pause"); 
    			cout<<endl<<endl<<endl;
    			Out();
    			cout<<endl<<endl;
    			break;
    		
    		case 5:
    			cout<<"\n\t\t二叉树的非递归中序遍历如下:\n\t\t";
    			NInOrder(b);
    			cout<<endl;
    			system("pause"); 
    			cout<<endl<<endl<<endl;
    			Out();
    			cout<<endl<<endl;
    			break;
    			
    		case 6:
    			cout<<"\n\t\t二叉树的递归后序遍历如下:\n\t\t";
    			RPostOrder(b);
    			cout<<endl;
    			system("pause");
    			Out();
    			cout<<endl<<endl;
    			cout<<endl<<endl<<endl;
    			break;
    		
    		case 7:
    			cout<<"\n\t\t二叉树的非递归后序遍历如下:\n\t\t";
    			
    			NPostOrder(b);
    			cout<<endl;
    			system("pause"); 
    			cout<<endl<<endl<<endl;
    			Out();
    			cout<<endl<<endl;
    			break;
    	
    		case 8:
    			cout<<"\n\t\t二叉树的层次遍历如下:\n\t\t";
    			LevelOrder(b);
    			cout<<endl;
    			system("pause"); 
    			cout<<endl<<endl<<endl;
    			Out();
    			cout<<endl<<endl;
    			break;	
    			
    		case 9:
    			cout<<"\n\t\t请输入待查找的结点的值(大写字母):  ";
    			cin>>se_le; 
    			se=FindNode(b,se_le);
    			h=CreateThread(b);
    			
    			if(se==NULL)
    				cout<<"\n\t未找到值为"<<se_le<<"的结点!!\n";
    			else 
    			{
    				cout<<endl<<"\t"<<se_le<<"的中序遍历过程中的前驱结点是:  "<<InPrenode(se)->data<<endl; 
    				cout<<endl<<"\t"<<se_le<<"的中序遍历过程中的后继结点是:  "<<InPostnode(se)->data<<endl;
    			}
    			cout<<endl<<endl<<endl;
    			CreateBTree(b,a);										//由于前面构建了线索二叉树,导致所有结点的指针都不为空指针,所以这里需要重新构建 
    			system("pause"); 
    			Out();
    			cout<<endl<<endl;
    			break;
    			
    		case 10:
    			cout<<"\n\t\t请输入待查找路径的结点:";
    			
    			cin>>se_le;
    			se=FindNode(b,se_le);
    			if(se==NULL)
    				cout<<"\n\t未找到值为"<<se_le<<"的结点!!\n";
    			else
    			{
    				cout<<"\t\t";
    				SearchPath(b,se);
    			}
    			cout<<endl;
    			system("pause"); 
    			cout<<endl<<endl<<endl;
    			Out();
    			cout<<endl<<endl;
    			break;	
    				
    		case 11:
    			cout<<"\n\t\t请输入待查找的子树的根:\n";
    			cin>>se_le;
    			se=FindNode(b,se_le);
    			if(se==NULL)
    				cout<<"\n\t\t未找到值为"<<se_le<<"的结点!!\n";
    			else
    			{
    				cout<<"\t\t";
    				RPreOrder(se);
    			
    			}
    			cout<<endl<<endl<<endl;
    			system("pause"); 
    			Out();
    			cout<<endl<<endl;
    			break;
    			
    		case 12:
    			return 0;
    		
    		default:
    			cout<<"\n\t 功能编号输入错误!\n";
    			system("pause");
    			Out();	
    		
    		
    	} 
    } 
    
    int main()
    {
    		cout<<	"\n\t\t二叉树基本运算功能菜单:\n"
    			"\n\t默认二叉树为:A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))\n"
    			"\n\t是否修改?\n"
    			"\n\t若需修改:输入Y;\n"
    			"\n\t如使用默认:输入除Y的任意字符:";
    			char judge;
    			cin>>judge;
    			if(judge=='Y')
    			{
    				
    				cout<<"\n\t请输入括号表示的二叉树:(长度小于100)\t";
    				cin>>a;
    				a[strlen(a)]='\0';
    				cout<<"\n\n修改成功!!\n";
    				system("pause");
    			}
    			else
    			{
    				cout<<"\n\t将使用默认二叉树:A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))\n";
    				system("pause"); 
    			}
    	CreateBTree(b,a);
    	Out();
    	return 0;
    
    } 
    
    展开全文
  • 编写一个程序btree.cpp,实现二叉树的基本运算,在此基础上,编写exp7-1.cpp,完成如下功能: 1、由二叉树创建对应的二叉链存储结构b,该二叉树的括号表示串为"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(...

    实验题目:
         实现二叉树各种基本运算的算法
    实验目的:
         领会二叉链存储结构和掌握二叉树中各种基本运算算法设计
      实验内容:
            编写一个程序btree.cpp,实现二叉树的基本运算,在此基础上,编写exp7-1.cpp,完成如下功能:
     1、由二叉树创建对应的二叉链存储结构b,该二叉树的括号表示串为 "A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))"。
    2、输出二叉树b
    3、输出'H'结点的左、右孩子结点值
    4、输出二叉树b的高度
    5、释放二叉树b

    btree.cpp如下:

    //
    // Created by liushihao on 19-4-26.
    //
    #include "iostream"
    #define Maxsize 100
    using namespace std;
    typedef char ElemType;
    
    typedef struct node
    {
        ElemType data;
        struct node *lchild;
        struct node *rchild;
    }BTNode;
    
    
    
    void CreateBTree(BTNode * &b, char *str) //创造二叉树
    {
        BTNode *St[Maxsize], *p;
        int top=-1,k,j=0;
        char ch;
        b=NULL;
        ch=str[j];
        while(ch!='\0')
        {
            switch (ch)
            {
                case '(':top++;St[top]=p;k=1;break;
                case ')':top--;              break;
                case ',':k=2;                break;
                default:
                    p=(BTNode*)malloc(sizeof(BTNode));
                    p->data=ch;
                    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=str[j];
        }
    }
    
    void DestroyBtree(BTNode *&b)  //销毁二叉树
    {
        if(b!=NULL)
        {
            DestroyBtree(b->lchild);
            DestroyBtree(b->rchild);
            free(b);
        }
    }
    
    BTNode *FindNode(BTNode *b,ElemType x)
    {
        BTNode *p;
        if(b==NULL)
        {
            return NULL;
        }
        else if(b->data==x)
        {
            return b;
        }
        else
        {
            p=FindNode(b->lchild, x);
            if(p!=NULL)
            {
                return p;
            }
            else
            {
                return FindNode(b->rchild, x);
            }
        }
    }
    
    BTNode *LchildNode(BTNode *p)
    {
        return p->lchild;
    }
    
    BTNode *RchildNode(BTNode *p)
    {
        return p->rchild;
    }
    
    int BTHeight(BTNode *b)
    {
        int lchildh,rchildh;
        if(b==NULL) return 0;
        else
        {
            lchildh=BTHeight(b->lchild);
            rchildh=BTHeight(b->rchild);
            return (lchildh>rchildh)? (lchildh+1):(rchildh+1);
        }
    }
    
    void DispBTree(BTNode *b)
    {
        if(b!=NULL)
        {
            cout<<b->data;
            if(b->lchild!=NULL || b->rchild!=NULL)
            {
                cout<<"(";
                DispBTree(b->lchild);
                if(b->rchild!= NULL) cout<<",";
                DispBTree(b->rchild);
                cout<<")";
            }
        }
    }

    exp7-1.cpp如下:

    #include "btree.h"
    int main()
    {
        BTNode *b;
        char str[]="A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))";
        CreateBTree(b, str);
        cout<<"初始化二叉树为:"<<endl;
        DispBTree(b);
        cout<<endl;
        cout<<"H结点的左结点:"<<LchildNode(FindNode(b,'H'))->data<<"  右结点:"<<RchildNode(FindNode(b,'H'))->data<<endl;
        cout<<"二叉树的高度为:"<<endl;
        cout<<BTHeight(b)<<endl;
        DestroyBtree(b);
        return 0;
    }

     

    展开全文
  • 实验内容 1、假设二叉树中的每个结点值为单个字符,...3、编写一个程序实现二叉树的基本运算,并在此基础上完成以下功能: (1)由图7.33所示的二叉树创建对应的二叉链存储结构b,该二叉树的括号表示串为“A(B(...

    实验内容

    1、假设二叉树中的每个结点值为单个字符,采用二叉链存储结构存储。设计一个算法,计算一棵给定二叉树b中的所有单分支结点个数。
    2.假设二叉树中的每个结点值为单个字符,采用二叉链存储结构存储。设计一个算法,求二叉树b中最小值的结点值。
    3、编写一个程序,实现二叉树的基本运算,并在此基础上完成以下功能:
    (1)由图7.33所示的二叉树创建对应的二叉链存储结构b,该二叉树的括号表示串为“A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))”。
    (2)输出二叉树b。
    (3)输出‘H’结点的左右孩子结点值。
    (4)输出二叉树b的高度。
    (5)释放二叉树b。
    4、编写一个程序,实现二叉树的先序遍历、中序遍历和后序遍历的递归和非递归算法,以及层次遍历的算法,并对图7.33所示的二叉树b给出求解结果。
    5、编写一个程序,实现由先序序列和中序序列以及由中序序列和后序序列构造一颗二叉树的功能(二叉树中的每个结点值为单个字符),要求以括号表示和凹入表示法输出该二叉树,并用先序遍历序列“ABDEHJKLMNCFGI”和中序遍历序列“DBJHLKMNEAFCGI”以及由中序遍历序列“DBJHLKMNEAFCGI”和后序遍历序列“DJLNMKHEBFIGCA”进行验证。
    6、编写一个程序实现以下功能,并对图7.33所示的二叉树进行验证。
    (1)输出二叉树b的结点个数。
    (2)输出二叉树b的叶子节点个数。
    (3)求二叉树b中指定结点值(假设所有结点值不同)的结点的层次。
    (4)利用层次遍历求二叉树b的宽度。

    代码实现

    1、

    #include <iostream>
    #include <malloc.h>
    using namespace std;
    #define MaxSize 50
    
    typedef struct node  
    {  
    	char data;
        struct node *lchild;  
        struct node *rchild;  
    }BTNode; 
    
    //创建二叉树
    void CreateBTree(BTNode *&b,const char *str)
    {
    	BTNode *St[MaxSize],*p;
    	int top=-1,k,j=0;
    	char ch;
    	b=NULL;
    	ch=str[j];
    	while(ch!='\0')
    	{
    		switch(ch)
    		{
    			case '(':top++;St[top]=p;k=1;break;
    			case ')':top--;break;
    			case ',':k=2;break;
    			default:p=(BTNode *)malloc(sizeof(BTNode));
    			p->data=ch;
    			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=str[j];
    	}
     } 
     //输出二叉树
     void DispBTree(BTNode *b)
     {
     	if(b!=NULL)
     	{
     		printf("%c",b->data);
     		if(b->lchild!=NULL||b->rchild!=NULL)
     		{
     			printf("(");
     			DispBTree(b->lchild);
     			if(b->rchild!=NULL)
     				printf(",");
     			DispBTree(b->rchild);
     				printf(")");
    		 }
    	 }
      } 
     //销毁二叉树
     void DestroyBTree(BTNode *&b)
     {
     	if(b!=NULL)
     	{
     		DestroyBTree(b->lchild);
     		DestroyBTree(b->rchild);
     		free(b);
    	 }
      } 
    //求单节点个数(先序遍历)
    int SSonNodes(BTNode *b)
    {
    	int num1,num2,n;
    	if(b==NULL)
    		return 0;
    	else if((b->lchild==NULL&&b->rchild!=NULL)||(b->lchild!=NULL&&b->rchild==NULL))
    		n=1;//为单分支结点
    	else
    		n=0;//为其他结点
    	num1=SSonNodes(b->lchild);//递归求左子树中单分支结点数
    	num2=SSonNodes(b->rchild);//递归求右子树中单分支结点数
    	return (num1+num2+n); 
     } 
     int main()
     {
     	BTNode *b;
    	CreateBTree(b,"A(B(D(,G)),C(E,F))");
    	cout<<"二叉树为:"<<endl;
    	DispBTree(b);
    	cout<<endl;
    	cout<<"单分支结点个数为:";
    	cout<<SSonNodes(b);
    	DestroyBTree(b);
    	return 0;	
      } 
    

    结果截图:
    在这里插入图片描述
    2、

    #include <iostream>
    #include <malloc.h>
    using namespace std;
    #define MaxSize 50
    
    typedef struct node  
    {  
    	char data;
        struct node *lchild;  
        struct node *rchild;  
    }BTNode; 
    
    //创建二叉树
    void CreateBTree(BTNode *&b,const char *str)
    {
    	BTNode *St[MaxSize],*p;
    	int top=-1,k,j=0;
    	char ch;
    	b=NULL;
    	ch=str[j];
    	while(ch!='\0')
    	{
    		switch(ch)
    		{
    			case '(':top++;St[top]=p;k=1;break;
    			case ')':top--;break;
    			case ',':k=2;break;
    			default:p=(BTNode *)malloc(sizeof(BTNode));
    			p->data=ch;
    			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=str[j];
    	}
     } 
     //输出二叉树
     void DispBTree(BTNode *b)
     {
     	if(b!=NULL)
     	{
     		printf("%c",b->data);
     		if(b->lchild!=NULL||b->rchild!=NULL)
     		{
     			printf("(");
     			DispBTree(b->lchild);
     			if(b->rchild!=NULL)
     				printf(",");
     			DispBTree(b->rchild);
     				printf(")");
    		 }
    	 }
      } 
     //销毁二叉树
     void DestroyBTree(BTNode *&b)
     {
     	if(b!=NULL)
     	{
     		DestroyBTree(b->lchild);
     		DestroyBTree(b->rchild);
     		free(b);
    	 }
      } 
    //找最小值的结点值
    void FindMinNode(BTNode *b,char &min)
    {
    	if(b->data<min)
    		min=b->data;
    	FindMinNode(b->lchild,min);//在左子树中找最小结点值 
    	FindMinNode(b->rchild,min);//在右子树中找最小结点值 		
     } 
    //输出最小结点值
    void MinNode(BTNode *b)
    {
    	if(b!=NULL)
    	{
    		char min=b->data;
    		printf("Min=%c\n",min);
    	}		
    }
    
    int main()
    {
    	BTNode *b;
    	CreateBTree(b,"A(B(D(,G)),C(E,F))");
    	cout<<"二叉树为:"<<endl;
    	DispBTree(b);
    	cout<<endl; 
    	cout<<"最小结点值为:"; 
    	MinNode(b); 
    	DestroyBTree(b);
    	return 0;	
    }
    

    结果截图:
    在这里插入图片描述
    3、

    #include <iostream>
    #include <malloc.h>
    using namespace std;
    #define MaxSize 50
    typedef char ElemType;  
    typedef struct node  
    {  
    	char data;
        struct node *lchild;  
        struct node *rchild;  
    }BTNode; 
    
    //创建二叉树
    void CreateBTree(BTNode *&b,const char *str)
    {
    	BTNode *St[MaxSize],*p;
    	int top=-1,k,j=0;
    	char ch;
    	b=NULL;
    	ch=str[j];
    	while(ch!='\0')
    	{
    		switch(ch)
    		{
    			case '(':top++;St[top]=p;k=1;break;
    			case ')':top--;break;
    			case ',':k=2;break;
    			default:p=(BTNode *)malloc(sizeof(BTNode));
    			p->data=ch;
    			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=str[j];
    	}
     } 
     
     //销毁二叉树
     void DestroyBTree(BTNode *&b)
     {
     	if(b!=NULL)
     	{
     		DestroyBTree(b->lchild);
     		DestroyBTree(b->rchild);
     		free(b);
    	 }
      } 
      
     //查找结点
     BTNode *FindNode(BTNode *b,ElemType x)
     {
     	BTNode *p;
     	if(b==NULL)
     		return NULL;
     	else if(b->data==x)
     		return b;
     	else
     	{
     		p=FindNode(b->lchild,x);
     		if(p!=NULL)
     			return p;
     		else 
     			return FindNode(b->rchild,x);
    	 }
      } 
    
    //找孩子结点
    BTNode *LchildNode(BTNode *p)
    {
    	return p->lchild;
     } 
    BTNode *RchildNode(BTNode *p)
    {
    	return p->rchild;
     } 
    //求高度
    int BTHeight(BTNode *b)
    {
    	int lchild,rchild;
    	if(b==NULL) return (0);
    	else
    	{
    		lchild=BTHeight(b->lchild);
    		rchild=BTHeight(b->rchild);
    		return (lchild>rchild)?(lchild+1):(rchild+1);
    	}
     } 
     //输出二叉树
     void DispBTree(BTNode *b)
     {
     	if(b!=NULL)
     	{
     		printf("%c",b->data);
     		if(b->lchild!=NULL||b->rchild!=NULL)
     		{
     			printf("(");
     			DispBTree(b->lchild);
     			if(b->rchild!=NULL)
     				printf(",");
     			DispBTree(b->rchild);
     				printf(")");
    		 }
    	 }
      } 
    int main()
    {
    	BTNode *b,*p,*lp,*rp;;  
        printf("  (1)创建二叉树.");  
        CreateBTree(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))");  
        printf("\n");  
        printf("  (2)输出二叉树:");  
        DispBTree(b);  
        printf("\n");  
        printf("  (3)查找H节点:");  
        p=FindNode(b,'H');  
        if (p!=NULL)  
        {  
            lp=LchildNode(p);  
            if (lp!=NULL)  
                printf("左孩子为%c,",lp->data);  
            else  
                printf("无左孩子 ");  
            rp=RchildNode(p);  
            if (rp!=NULL)  
                printf("右孩子为%c",rp->data);  
            else  
                printf("无右孩子 ");  
        }  
        else  
            printf(" 未找到!");  
        printf("\n");  
        printf("  (4)二叉树b的高度为:%d\n",BTHeight(b));  
        printf("  (5)释放二叉树b\n");  
        DestroyBTree(b);  
        return 0;  
    }
    

    结果截图:

    4、

    #include <iostream>
    #include <malloc.h>
    using namespace std;
    #define MaxSize 50
    typedef char ElemType;
      
    //递归声明  
    typedef struct node  
    {  
    	char data;
        struct node *lchild;  
        struct node *rchild;  
    }BTNode;
    //非递归声明 
    typedef struct
    {
    	BTNode *data[MaxSize];
    	int top;
     }SqStack; 
     
    //层次遍历声明
    typedef struct
    {
    	BTNode *data[MaxSize];
    	int front,rear;
     }SqQueue;
    //递归算法 
    //创建二叉树
    void CreateBTree(BTNode *&b,const char *str)
    {
    	BTNode *St[MaxSize],*p;
    	int top=-1,k,j=0;
    	char ch;
    	b=NULL;
    	ch=str[j];
    	while(ch!='\0')
    	{
    		switch(ch)
    		{
    			case '(':top++;St[top]=p;k=1;break;
    			case ')':top--;break;
    			case ',':k=2;break;
    			default:p=(BTNode *)malloc(sizeof(BTNode));
    			p->data=ch;
    			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=str[j];
    	}
     } 
    //输出二叉树
     void DispBTree(BTNode *b)
     {
     	if(b!=NULL)
     	{
     		printf("%c",b->data);
     		if(b->lchild!=NULL||b->rchild!=NULL)
     		{
     			printf("(");
     			DispBTree(b->lchild);
     			if(b->rchild!=NULL)
     				printf(",");
     			DispBTree(b->rchild);
     				printf(")");
    		 }
    	 }
      } 
    //先序遍历
    void PreOrder(BTNode *b)
    {
    	if(b!=NULL)
    	{
    		printf("%c ",b->data);
    		PreOrder(b->lchild);
    		PreOrder(b->rchild);
    	}
     } 
    //中序遍历
    void InOrder(BTNode *b)
    {
    	if(b!=NULL)
    	{
    		InOrder(b->lchild);
    		printf("%c ",b->data);
    		InOrder(b->rchild);
    	}
     }
    //后序遍历
    void PostOrder(BTNode *b)
    {
    	if(b!=NULL)
    	{
    		PostOrder(b->lchild);
    		PostOrder(b->rchild);
    		printf("%c ",b->data);
    	}
     }
    //非递归算法 
    //先序遍历
    void PreOrder1(BTNode *b)
    {
    	BTNode *p;
    	SqStack *st;
    	InitStack(st);
    	if(b!=NULL)
    	{
    		Push(st,b);
    		while(!StackEmpty(st))
    		{
    			Pop(st,p);
    			printf("%c ",p->data);
    			if(p->rchild!=NULL)
    				Push(st,p->rchild);
    			if(p->lchild!=NULL)
    				Push(st,p->lchild);
    		}
    		printf("\n");
    	}
    	DestroyStack(st);	
     }
     //中序遍历
    void InOrder1(BTNode *b)
    {
    	BTNode *p;
    	SqStack *st;
    	InitStack(st);
    	p=b;
    	while(!StackEmpty(st)||p!=NULL)
    	{
    		while(p!=NULL)
    		{
    			Push(st,p);
    			p=p->lchild;
    		}
    		if(!StackEmpty(st))
    		{
    			Pop(st,p);
    			printf("%c ",p->data);
    			p=p->rchild;
    		}	
    	}
    	printf("\n");
    	DestroyStack(st);	
     }
    //后序遍历
    void PostOrder1(BTNode *b)
    {
    	BTNode *p,*r;
    	bool flag;
    	SqStack *st;
    	InitStack(st);
    	p=b;
    	do
    	{
    		while(p!=NULL)
    		{
    			Push(st,p);
    			p=p->lchild;
    		}
    		r=NULL;
    		flag=true;
    		while(!StackEmpty(st)&&flag)
    		{
    			GetTop(st,p);
    			if(p->rchild==r)
    			{
    				printf("%c ",p->data);
    				Pop(st,p);
    				r=p;
    			}
    			else
    			{
    				p=p->rchild;
    				flag=false;
    			}
    		}
    	}while(!StackEmpty(st));
    	printf("\n");
    	DestroyStack(st);
    } 
    //层次遍历
    void LevelOrder(BTNode *b)
    {
    	BTNode *b;
    	SqQueue *qu;
    	InitQueue(qu);
    	enQueue(qu,b);
    	while(!QueueEmpty(qu))
    	{
    		deQueue(qu,p);
    		printf("%c ",p->data);
    		if(p->lchild!=NULL)
    			enQueue(qu,p->lchild);
    		if(p->rchild!=NULL)
    			enQueue(qu,p->rchild);
    	}
     } 
    int main()
    {
    	BTNode *b;
    	CreateBTree(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))");
    cout<<"二叉树为:"<<endl;
    	DispBTree(b);
    	cout<<endl;
    	cout << "(1)递归算法:"<<endl;
    	cout << "先序遍历结果为:";  
        PreOrder(b);  
        cout << endl;  
        cout << "中序遍历结果为:";  
        InOrder(b);  
        cout << endl;  
        cout << "后序遍历结果为:";  
        PostOrder(b);  
        cout << endl;  
      
      	cout << "(2)非递归算法:"<<endl;
      	cout << "先序遍历结果为:";  
        PreOrder(b);  
        cout << endl;  
        cout << "中序遍历结果为:";  
        InOrder(b);  
        cout << endl;  
        cout << "后序遍历结果为:";  
        PostOrder(b);  
        cout << endl;  
        
      	cout << "(3)层次遍历结果为:";  
        LevelOrder(b);    
        return 0;  
    }
    

    结果截图:
    在这里插入图片描述
    5、

    #include<iomanip>
    #include<stdio.h>
    #include<malloc.h>
    #define MaxSize 100
    #define MaxWidth 40
    typedef char ElemType;
    typedef struct node
    {
    	ElemType data;//数据元素
    	struct node *lchild;//指向左孩子
    	struct node *rchild;//指向右孩子
    }BTNode;
    //输出二叉树
     void DispBTNode(BTNode *b)
     {
     	if(b!=NULL)
     	{
     		printf("%c",b->data);
     		if(b->lchild!=NULL||b->rchild!=NULL)
     		{
     			printf("(");
     			DispBTNode(b->lchild);
     			if(b->rchild!=NULL)
     				printf(",");
     			DispBTNode(b->rchild);
     				printf(")");
    		 }
    	 }
      } 
    //销毁二叉树
     void DestroyBTNode(BTNode *&b)
     {
     	if(b!=NULL)
     	{
     		DestroyBTNode(b->lchild);
     		DestroyBTNode(b->rchild);
     		free(b);
    	 }
      } 
    BTNode *CreateBT1(char *pre,char *in,int n) 
    {
    	BTNode *s; 
    	char *p;
    	int k;
    	if (n<=0) return NULL;
    	s=(BTNode *)malloc(sizeof(BTNode));//创建二叉树节点*s
    	s->data=*pre;
    	for (p=in;p<in+n;p++)//在中序序列中找等于*ppos的位置k
    	if (*p==*pre) break;
    	k=p-in;
    	s->lchild=CreateBT1(pre+1,in,k);
    	s->rchild=CreateBT1(pre+k+1,p+1,n-k-1);
    	return s; 
    }
    BTNode *CreateBT2(char *post,char *in,int n,int m)
    {
    	BTNode *s; 
    	char *p,*q,*maxp;
    	int maxpost,maxin,k;
    	if (n<=0) return NULL;
    	maxpost=-1;
    	for (p=in;p<in+n;p++)//求in中全部字符中在post中最右边的那个字符
    	for (q=post;q<post+m;q++)//在in中用maxp指向这个字符,用maxin标识它在in中的下标
    	if (*p==*q)
    	{
    		k=q-post;
    		if (k>maxpost)
    		{
    		maxpost=k;
    		maxp=p;
    		maxin=p-in;
    		}
    	}
    	s=(BTNode *)malloc(sizeof(BTNode));//创建二叉树节点*s
    	s->data=post[maxpost];
    	s->lchild=CreateBT2(post,in,maxin,m);
    	s->rchild=CreateBT2(post,maxp+1,n-maxin-1,m);
    	return s;
    }
    void DispBTNode1(BTNode *b)//以凹入表表示法输出一棵二叉树
    {
    	BTNode *St[MaxSize],*p;
    	int level[MaxSize][2],top=-1,n,i,width=4;
    	char type;
    	if (b!=NULL)
    	{
    		top++;
    		St[top]=b;//根节点入栈
    		level[top][0]=width;
    		level[top][1]=2;//2表示是根
    		while (top>-1)
    		{	
    			p=St[top];//退栈并凹入显示该节点值
    			n=level[top][0];
    			switch(level[top][1])
    			{
    				case 0:type='L';break;//左节点之后输出(L)
    				case 1:type='R';break;//右节点之后输出(R)
    				case 2:type='B';break;//根节点之后前输出(B)
    			}
    		for (i=1;i<=n;i++)//其中n为显示场宽,字符以右对齐显示
    			printf("");
    			
    		printf("%c(%c)",p->data,type);
    		for (i=n+1;i<=MaxWidth;i+=2)
    			printf("--");
    		printf("\n");
    		top--;
    		if (p->rchild!=NULL)
    		{//将右子树根节点入栈
    			top++;
    			St[top]=p->rchild;
    			level[top][0]=n+width;//显示场宽增width
    			level[top][1]=1;//1表示是右子树
    		}
    		if (p->lchild!=NULL)
    		{//将左子树根节点入栈
    			top++;
    			St[top]=p->lchild;
    			level[top][0]=n+width;//显示场宽增width
    			level[top][1]=0;//0表示是左子树
    		}
    		}
    	}
    }
    int main()
    {
    	BTNode *b;
    	ElemType pre[]="ABDEHJKLMNCFGI";
    	ElemType in[]="DBJHLKMNEAFCGI";
    	ElemType post[]="DJLNMKHEBFIGCA";
    	b=CreateBT1(pre,in,14);
    	printf("先序序列:%s\n",pre);
    	printf("中序序列:%s\n",in);
    	printf("构造一棵二叉树b:\n");
    	printf(" 括号表示法:");
    	DispBTNode(b);
    	printf("\n");
    	printf(" 凹入表示法:\n");
    	DispBTNode1(b);printf("\n\n");
    	printf("中序序列:%s\n",in);
    	printf("后序序列:%s\n",post);
    	b=CreateBT2(post,in,14,14);
    	printf("构造一棵二叉树b:\n");
    	printf(" 括号表示法:");
    	DispBTNode(b);
    	printf("\n");
    	printf(" 凹入表示法:\n");
    	DispBTNode1(b);
    	printf("\n");
    	DestroyBTNode(b); 
    }
    

    结果截图:
    在这里插入图片描述
    6、

    #include <iostream>
    #include <malloc.h>
    using namespace std;
    #define MaxSize 50
    typedef char ElemType;
      
    //递归声明  
    typedef struct node  
    {  
    	char data;
        struct node *lchild;  
        struct node *rchild;  
    }BTNode;
    //创建二叉树
    void CreateBTree(BTNode *&b,const char *str)
    {
    	BTNode *St[MaxSize],*p;
    	int top=-1,k,j=0;
    	char ch;
    	b=NULL;
    	ch=str[j];
    	while(ch!='\0')
    	{
    		switch(ch)
    		{
    			case '(':top++;St[top]=p;k=1;break;
    			case ')':top--;break;
    			case ',':k=2;break;
    			default:p=(BTNode *)malloc(sizeof(BTNode));
    			p->data=ch;
    			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=str[j];
    	}
     } 
     //输出二叉树
     void DispBTree(BTNode *b)
     {
     	if(b!=NULL)
     	{
     		printf("%c",b->data);
     		if(b->lchild!=NULL||b->rchild!=NULL)
     		{
     			printf("(");
     			DispBTree(b->lchild);
     			if(b->rchild!=NULL)
     				printf(",");
     			DispBTree(b->rchild);
     				printf(")");
    		 }
    	 }
      } 
    //先序遍历
    void PreOrder(BTNode *b)
    {
    	if(b!=NULL)
    	{
    		printf("%c ",b->data);
    		PreOrder(b->lchild);
    		PreOrder(b->rchild);
    	}
     } 
    //中序遍历
    void InOrder(BTNode *b)
    {
    	if(b!=NULL)
    	{
    		InOrder(b->lchild);
    		printf("%c ",b->data);
    		InOrder(b->rchild);
    	}
     }
    //后序遍历
    void PostOrder(BTNode *b)
    {
    	if(b!=NULL)
    	{
    		PostOrder(b->lchild);
    		PostOrder(b->rchild);
    		printf("%c ",b->data);
    	}
     }
    //结点个数
    int Nodes(BTNode *b)
    {
    	int num1,num2;
    	if(b==NULL)
    		return 0;
    	else
    		return Nodes(b->lchild)+Nodes(b->rchild)+1;
     }
    //叶子结点个数
    int LeafNodes(BTNode *b)
    {
      if(!b)       
       return 0;      //空树,无叶子 
      else if(!b->lchild && !b->rchild)
               return 1;
            else 
               return (LeafNodes(b->lchild) + LeafNodes(b->rchild));
    }
    //求指定结点值所在层次(假设二叉树结点互不相同) 
    int Level(BTNode *b,ElemType x,int h)   //h置初值1  
    {   int l;  
        if (b==NULL)  
            return(0);  
        else if (b->data==x)  
            return(h);  
        else  
        {   l=Level(b->lchild,x,h+1);    //在左子树中查找  
            if (l!=0)  
                return(l);  
            else                        //在左子树中未找到,再在右子树中查找  
                return(Level(b->rchild,x,h+1));  
        }  
    }  
    //利用层次遍历求二叉树的宽度
    void traverse(BTNode b)  
    {  
        queue<BTNode> q;  
        BTNode p=NULL;  
      
        if(b)  
            q.push(Tb);  
        while(!q.empty())  
        {  
              
            p=q.front();  
            q.pop();  
            cout<<p->data<<" ";  
            if(p->lchild)  
            {  
                q.push(p->lchild);  
            }  
            if(p->rchild)  
            {  
                q.push(p->rchild);  
            }  
        }  
    }  
      
    int Width(BTNode *b)  
    {  
        if(b!=NULL)  
        {  
            if(b->lchild==NULL&&b->rchild==NULL)  
            return 1;  
            else  
            return Width(b->lchild)+Width(b->rchild);  
        }  
    }  
     
     int main()
     {
     	BTNode *b;
     	int h;  
     	ElemType x; 
     	CreateBTree(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))");
     	cout<<"(1)结点个数:"<<Nodes(b)<<endl;
    	cout<<"(2)叶子结点个数:"<<LeafNodes(b)<<endl;	
    	printf("(3)结点值:");  
        scanf("%c",&x);  
        h=Level(b,x,1);  
        if (h==0)  
            printf("b中不存在%c节点\n",x);  
        else  
                printf(" 在b中%c节点的层次为:%d\n",x,h);  
        	cout<<"(4)二叉树b的宽 度为:"<<(b);
    

    结果截图:
    在这里插入图片描述

    展开全文
  • printf("实验题7.1: 编写一个程序algo7-1.cpp,实现二叉树的各种基本运算,并在此基础上设计一个程序Main.cpp完成如下功能(b为如下图所示的一棵二叉树)\n(1)输出二叉树b;\n(2)输出H节点的左、右孩子节点值;\n(3...
  • 二叉树的一些基本功能运算

    千次阅读 2016-05-26 12:24:50
     编写一个程序algo7-1.cpp,实现二叉树的各种运算,并在此基础上设计一个程序exp7-1.cpp完成如下功能(b为如图7.23所示的一棵二叉树):  (1)输出二叉树b;  (2)输出H节点的左,右孩子节点的值;  (3)...
  • 二叉树的基本操作

    2020-01-11 13:43:05
    数据结构(实验C语言版) 二叉树的基本操作 一、实验目的 掌握二叉树链表的结构和二叉树的建立过程 ...1、编写一个程序实现二叉树的各种运算,并完成如下功能: (1)输出二叉树b;(b为下图所示的二叉树) (2...
  • 编写一个程序实现二叉树的各种运算,并在此基础上设计一个程序完成如下功能: (1)创建一棵二叉树(用键盘按照先序遍历序列输入一个字符串生成二叉树); (2)输出前序、中序、后序遍历的遍历序列; (3)统计并...
  • 一、实验目的: 1、领会二叉链存储结构和掌握二叉树中的各种基本运算算法设计; 2、领会线索二叉树的构造过程以及构造二叉树的算法设计; 3、领会哈夫曼树的构造过程以及哈夫曼编码的生成过程;...编写一个程序btr
  • 编写一个程序btree.cpp,实现二叉树的基本运算,并在此基础上设计一个程序exp7-1.cpp,完成如下功能: (1) 由如图7.1所示的二叉树创建对应的二叉链 存储结构b,该二叉树的括号表示串为“A(B(D,E(H(J,K(L,M(,N)))))...
  • 二叉树的基本操作 、实验目的 1、掌握用指针类型描述、访问和处理二叉树的运算; 2、掌握二叉树的结构特征,以及各种存储结构的特点及适用范围; 3、熟练掌握递归程序设计方法、以及栈的应用 二、实验内容 以二叉...
  • 编写程序,实现二叉树的各种基本运算和遍历,并在此基础上设计一个程序,完成以下功能: 建立二叉树bt,该二叉树的括号表示串为 “A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))”; 输出二叉树bt; 输出二叉树的高度; ...
  • 以二叉链表作存储结构,编写程序实现如下的功能: 1、根据输入的数据建立一个二叉树; 2、分别采用前序、中序、后序的遍历方式显示输出二叉树的遍历结果 3、采用非递归的编程方法,分别统计二叉树的节点个数、度为...
  • 二叉排序树与平衡二叉树的实现

    热门讨论 2010-12-26 15:25:31
    而在二叉排序树上进行查找时的平均查找长度和二叉树的形态有关: ①在最坏情况下,二叉排序树是通过把一个有序表的n个结点依次插入而生成的,此时所得的二叉排序树蜕化为棵深度为n的单支树,它的平均查找长度和...
  • 二叉树的创建与遍历

    2019-01-23 14:46:58
    一、实验目的: 1、熟悉二叉树结点的结构和对二叉树的基本操作; 2、掌握对二叉树每一种操作的具体实现;...编写实现二叉树建立和遍历的基本算法的函数,并在此基础上设计一个程序完成如下功能: ...
  • 树 超基础二叉树知识

    2020-05-12 19:38:02
    编写一个程序实现二叉树的基本运算,具体要求如下: 括号表示法读入数据 括号表示法输出该树 输入一个结点的值,输出该结点的左,右孩子的值(要能测试错误数据) 输出该二叉树的高度 输出该二叉树结点的个数 ...
  • 编写一个程序btree.cpp,实现二叉树的基本运算,并在此基础上设计一个程序完成以下功能:(见教材P247,实验题1) (1)由图7.33所示的二叉树创建对应的二叉链存储结构b,该二叉树的括号表示串为“A(B(D,E(H(J,K(L,M(,N)...
  • 1.4 C++程序的编写实现 1.5 关于C++上机实践 习题 第2章 数据类型与表达式 2.1 C++数据类型 2.2 常量 2.2.1 什么是常量 2.2.2 数值常量 2.2.3 字符常量 2.2.4 符号常量 2.3 变量 2.3.1 什么是变量 2.3.2 ...
  • 1.4 C++程序的编写实现 1.5 关于C++上机实践 习题 第2章 数据类型与表达式 2.1 C++数据类型 2.2 常量 2.2.1 什么是常量 2.2.2 数值常量 2.2.3 字符常量 2.2.4 符号常量 2.3 变量 2.3.1 什么是变量 2.3.2 ...
  • 实验五 树

    2020-02-15 12:53:38
    实验题1:编写一个程序实现二叉树的基本运算,并在此基础上设计一个程序完成如下功能。 (1)由图所示的二叉树创建对应的二叉链存储结构b,该二叉树的括号表示串为“A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))”。 ...
  • 熟练掌握在两种存储结构上实现栈和队列的基本运算;学会利用栈和队列解决一些实际问题。 五:内容:1、若X和Y是用结点大小为1的单链表表示的串,设计算法找出X中第一个不在Y中出现的字符。 2、设计一算法,在顺序串...
  • 4.1 一个简单递归示例 128 4.2 阶乘函数 129 4.2.1 Fact递归公式 130 4.2.2 追踪递归过程 130 4.2.3 递归跳跃信任 134 4.3 费波那契函数 134 4.3.1 计算费波那契序列 135 4.3.2 增进实现递归信心 ...
  • 二叉树的基本操作 、实验目的 1、掌握用指针类型描述、访问和处理二叉树的运算; 2、掌握二叉树的结构特征,以及各种存储结构的特点及适用范围; 3、熟练掌握递归程序设计方法、以及栈的应用 二、实验内容 以二叉...
  • 8.5.2 从一个顶点到其余各顶点最短路径142 8.5.3 每对顶点之间最短路径145 8.5.4 上机体验148 8.6 图应用实例149 第9章 排序150 9.1 插入排序150 9.1.1 排序原理150 9.1.2 程序设计151 9.1.3 算法分析1539.2 ...
  • 数据结构入门

    2019-03-18 14:23:44
    2、编写程序实现顺序串的各种基本运算。 3、按照对二叉树的操作需要,在创建好二叉树后再通过遍历算法验证创建结果。 4、哈夫曼编码算法的实现 5、编制一个能够实现图的创建、深度遍历、广度遍历、最小生成树的...
  • 若干源程序资料12.rar

    热门讨论 2012-06-11 22:11:26
    2012-06-11 21:44 2,279 C语言编一个程序完成64位数据(无符号)加法,减法运算.txt 2012-06-11 21:43 1,480,155 Direct3D加载3d文件.rar 2012-06-11 21:29 22,102 DSP编程一周通.rar 2012-06-11 21:04 837,926 ...
  • 数据结构实验

    2012-04-13 09:55:47
    构造两个带有表头结点有序单链表La、Lb,编写程序实现将La、Lb合并成一个有序单链表Lc。 合并思想是:程序需要3个指针:pa、pb、pc,其中pa,pb分别指向La表与Lb表中当前待比较插入结点,pc 指向Lc表中当前最后...
  • 带你搭一个SpringBoot+SpringData JPADemo 【极简版】SpringBoot+SpringData JPA 管理系统 :jack_o_lantern:SSH项目 SSH【史上最详细整合】 【SSH测试整合Demo】企业人事管理系统 阅读SSH项目之ERP 纳税服务...
  • 因此需要引入一个翻转后头结点,以及一个指向当前结点指针,一个指向当前结点前一个结点指针,一个指向当前结点后一个结点指针,防止出现断裂。推广:递归实现反转链表 面试题17:合并两个排序链表:要...

空空如也

空空如也

1 2 3
收藏数 53
精华内容 21
关键字:

编写一个程序实现二叉树的基本运算