二叉树操作设计和实现

Question

采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数。

Answer 1

【相关推荐】

• 这有个类似的问题, 你可以参考下: https://ask.csdn.net/questions/7559801
• 这篇博客你也可以参考下：二叉树的创建以及先序，中序，后序递归法遍历，普通循环遍历
• 您还可以看一下 张子良老师的元宇宙体系结构、关键技术和实践探索课程中的 课程体系和预期收益小节, 巩固相关知识点
  
• 除此之外, 这篇博客: 【数据结构】A．输入根据用户的输入信息，建立二叉树的二叉链表。 B．利用递归和非递归实现二叉树的先序、中序、后序遍历，利用队列实现二叉树的层次遍历。 C．求所有叶子结点总数及深度。中的 程序代码 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

  #include<stdio.h>
  #include<stdlib.h>
  #include<string.h>
  #define MaxSize 100
  
  //二叉树 
  typedef struct BTN {
  	char data;
  	struct BTN *lchild,*rchild;
  }BTN,*BiTNode;
  
  //二叉树非递归遍历栈 
  typedef struct {
  	BiTNode *base;
  	int top;
  	int stacksize;
  }SqStack;
  
  //二叉树层遍历队列
  typedef struct{
  	int front,rear;
  	BiTNode *base; 
  }SqQueue;
   
  //初始化栈
  void InitStack(SqStack &S){
  	S.base = (BiTNode*)malloc(MaxSize*sizeof(BiTNode));
  	if(!S.base) return ;
  	S.top = 0;
  	S.stacksize = MaxSize;
  }
  
  //判断栈是否空
  int StackEmpty(SqStack &S){
  	if(S.top == 0)
  	return 1;
  	return 0;
  } 
  
  //入栈
  void Push (SqStack &S,BiTNode e){
  	if(S.top >=S.stacksize){
  		S.base = (BiTNode*)realloc(S.base,(S.stacksize+10)*sizeof(BiTNode));
  	    if(!S.base) exit(0);
  	    S.stacksize += 10;
  	}
  	S.base[S.top++] = e; 	
  } 
  
  // 出栈
  void Pop(SqStack &S,BiTNode &e){
  	if(S.top == 0)
  	exit(0);
  	else 
  	e = S.base[--S.top];
  } 
  
  //访问栈顶元素
  int GetTop(SqStack &S,BiTNode &e){
  	if(S.top == 0)
  	return 0;
  	e = S.base[S.top-1];
  	return 1;	
  } 
  
  //初始化队列
  void InitQueue(SqQueue *fq){
  	fq->front = fq->rear = 0;
  	fq->base = (BiTNode *)malloc(MaxSize*sizeof(BiTNode));
  } 
  
  //入队列
  void EnQueue(SqQueue *fq,BiTNode e){
      fq->base[fq->rear] = e;
  	fq->rear = (fq->rear +1)%MaxSize;
  } 
  
  //出队列
  void DeQueue(SqQueue *fq,BiTNode &p){
  	if(fq->front == fq->rear)
  	return ;
  	p = fq->base[fq->front];
  	fq->front = (fq->front +1)%MaxSize;
  } 
  
  //判断队列是否为空
  int QueueEmpty(SqQueue *fq){
  	if(fq->front == fq->rear)
  	return 1;
  	else
  	return 0;
  }
  //访问data值 
  void visit(BiTNode bt){
  	printf("%3c",bt->data);
  }
  
  //根据用户输入建二叉树 
  void CreatBiTree(BiTNode &bt){
  	char e;
  	scanf("%c",&e);
  	if(e == '#'){
  	bt = NULL;
  	} 	
  	else{	
  	    bt = (BiTNode)malloc(sizeof(BiTNode));	
  		if(!bt) return ;
  		bt->data = e;
  		CreatBiTree(bt->lchild);
  		CreatBiTree(bt->rchild);
  	}
  }
  
  
  
  //递归先序遍历 
  void PreOrderTraverse(BiTNode bt){
  	if(bt){
  		visit(bt);
  		PreOrderTraverse(bt->lchild);
  		PreOrderTraverse(bt->rchild);
  	}
  }
  
  //递归中序遍历 
  void InOrderTraverse(BiTNode bt){
  	if(bt){
  	   InOrderTraverse(bt->lchild);
         visit(bt);
  	   InOrderTraverse(bt->rchild);	
  	}
  }
  
  //递归后序遍历 
  void PostOrderTraverse(BiTNode bt){
  	if(bt){
  	   PostOrderTraverse(bt->lchild);
  	   PostOrderTraverse(bt->rchild);
  	   visit(bt);	
  	}
  }
  
  //非递归先序遍历
  void fPreOrderTraverse(BiTNode bt){
  	if(bt){
  		BiTNode p;
  		SqStack S;
  		InitStack(S);
  		Push(S,bt);
  		while(!StackEmpty(S)){
  			while(GetTop(S,p)&&p){
  				visit(p);
  				Push(S,p->lchild);
  			}
  			Pop(S,p);
  			if(!StackEmpty(S)){
  				Pop(S,p);
  				Push(S,p->rchild);
  			}
  		}
  	}
  } 
  
  //非递归中序遍历
  void fInOrderTraverse(BiTNode bt){
  	if(bt){
  		BiTNode p;
  		SqStack S;
  		InitStack(S);
  		Push(S,bt);
  		while(!StackEmpty(S)){
  			while(GetTop(S,p)&&p){
  				Push(S,p->lchild);
  			}
  			Pop(S,p);
  			if(!StackEmpty(S)){
  				Pop(S,p);
  				visit(p);
  				Push(S,p->rchild);
  			}
  		}
  	}
  }
  
  //非递归后序遍历
  void fPostOrderTraverse(BiTNode bt){
  	SqStack S;
  	BiTNode p,q;
  	if(bt){
  		InitStack(S);
  		Push(S,bt);
  		while(!StackEmpty(S)){
  			while(GetTop(S,p) && p)
  				Push(S,p->lchild);
  			Pop(S,p);
  			if(!StackEmpty(S)){
  				GetTop(S,p);
  				if(p->rchild)
  					Push(S,p->rchild);
  				else{
  					Pop(S,p);
  					visit(p);
  					while(!StackEmpty(S) && GetTop(S,q) && q->rchild==p){
  						Pop(S,p);
  						visit(p);
  					}
  					if(!StackEmpty(S)){
  						GetTop(S,p);
  						Push(S,p->rchild);
  					}
  				}
  			}
  		}		
  	}
  }
  //层次遍历
  void LevelOrderTraverse(BiTNode bt){
  	if(bt){
  		SqQueue fq;
  		BiTNode p;
  		InitQueue(&fq);
  		EnQueue(&fq,bt);
  		while(!QueueEmpty(&fq)){
  			DeQueue(&fq,p);
  			visit(p);
  			if(p->lchild) EnQueue(&fq,bt->lchild);
  			if(p->rchild) EnQueue(&fq,bt->rchild);
  		}
  	}
  } 
  //定义静态变量
  static int count = 0;
   
  //求叶子节点数
  void LeafNode(BiTNode bt){
  	if(bt){
  		LeafNode(bt->lchild);
  		if(!bt->lchild && !bt->rchild)
  		count++;
  		LeafNode(bt->rchild);
  	}
  } 
  //二叉树的深度
  int BiTreeDepth(BiTNode bt){
  	int depthL,depthR; 
  	if(bt==NULL)
  		return 0;
  	else{
  		depthL=BiTreeDepth(bt->lchild);
  		depthR=BiTreeDepth(bt->rchild);
  		if(depthL>=depthR)
  			return depthL+1;
  		else return depthR+1;
  	}
  }
  int main(){
  	BiTNode bt;
  	printf("请输入想要遍历的二叉树（空节点用'#’代替）：\n"); 
  	CreatBiTree(bt);
  	printf("递归先序遍历结果：\n");
  	PreOrderTraverse(bt); 
  	printf("\n递归中遍历结果：\n");
  	InOrderTraverse(bt);
  	printf("\n递归后序遍历结果：\n");
  	PostOrderTraverse(bt);
  	printf("\n非递归先序遍历结果：\n");
  	fPreOrderTraverse(bt);
  	printf("\n非递归中序遍历结果：\n");
  	fInOrderTraverse(bt);
  	printf("\n非递归后序遍历结果：\n");
  	fPostOrderTraverse(bt);
  	LeafNode(bt);
  	printf("\n该二叉树叶子节点数为：%d",count);
  	printf("\n二叉树的深度：%d",BiTreeDepth(bt));
  	return 0;
  	
  }
  
  

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^