数据结构C语言版（作业）之二叉树的创建，遍历（递归、非递归）

迈不过友情╰ 2022-04-15 03:26 58阅读 0赞

## 1）二叉树的创建，递归遍历，深度，结点数，叶子数 ##

#include<iostream>
    using namespace std;
    typedef struct bitnode{
    	char data;
    	struct bitnode *lchild,*rchild;
    }bitnode,*bitree; 
    void createbitree(bitree &T){//创建二叉树 前序输入 
        char ch;
        cin>>ch;
        if(ch=='#') T=NULL;
        else{
        	T= new bitnode;
        	T->data=ch;
        	createbitree(T->lchild);
        	createbitree(T->rchild);
    	} 
    }
    void roottraverse(bitree T){//前序递归遍历 
    	if(T){
    		cout<<T->data;
    		roottraverse(T->lchild);
    		roottraverse(T->rchild);
    	}
    }
    void  inordertraverse(bitree T){//中序递归遍历 
    	if(T){
    		inordertraverse(T->lchild);
    		cout<<T->data;
    		inordertraverse(T->rchild);
    	}
    }
    void postordertraverse(bitree T){//后续递归遍历 
    	if(T){
    		postordertraverse(T->lchild);
    		postordertraverse(T->rchild);
    		cout<<T->data;
    	}
    } 
    void copybitree(bitree T,bitree newT){//复制二叉树 
    	if(T==NULL){
    		newT=NULL;return ;
    	}
    	else{
    		newT= new bitnode;
    		newT->data=T->data;
    		copybitree(T->lchild,newT->lchild);
    		copybitree(T->rchild,newT->rchild);
    	}
    } 
    int depth(bitree T){  //二叉树的深度 
    	if(T==NULL) return 0;
    	else{
    		int m=depth(T->lchild);
    		int n=depth(T->rchild);
    		return m>n?m+1:n+1;
    	}
    } 
    int nodecount(bitree T){  //二叉树结点个数 
    	if(T==NULL) return 0;
    	else{
    		return nodecount(T->lchild)+nodecount(T->rchild)+1;
    	}
    } 
    int leavescount(bitree T){ //叶子结点个数 
    	if(T==NULL) return 0;
    	if(T->lchild==NULL&&T->rchild==NULL) return 1;
    
    	return leavescount(T->lchild)+leavescount(T->rchild);
    } 
    int node1count(bitree T){ //度为1结点个数 
        if(T==NULL) return 0;
    	if(T->lchild==NULL||T->rchild==NULL) return 1;
    
    	return leavescount(T->lchild)+leavescount(T->rchild);
    
    //	return  nodecount(T)-2*leavescount(T)+1; 
    }
    int node2count(bitree T){ //度为2结点个数 
    	if(T==NULL) return 0;
    	if(T->lchild!=NULL&&T->rchild!=NULL) return 1;
    	
    	return leavescount(T->lchild)+leavescount(T->rchild)+1;
    }
    int main(){
    	bitree T;
    	cout<<"创建二叉树: ";
    	createbitree(T);
    	cout<<endl<<"前序遍历: ";
    	roottraverse(T);
    	cout<<endl<<"中序遍历:";
    	inordertraverse(T);
    	cout<<endl<<"后序遍历: ";
    	postordertraverse(T);
    	cout<<endl<<"深度为："<<depth(T);
    	
    	cout<<endl<<"结点数为: "<<nodecount(T);
    	
    	cout<<endl<<"叶子结点数为："<<leavescount(T);
    	
    	cout<<endl<<"度为1结点数为："<<node1count(T);
    	
    	cout<<endl<<"度为2结点数为："<<node2count(T);
    	
    	return 0;
    }

### 输入：       ###

AB\#C\#\#DE\#\#\#\#

### 输出： ###

前序遍历：ABCDE  
中序遍历：BCAED  
后序遍历：CBEDA  
深度：3  
结点数：5  
叶子数：2  
度为1结点数：2  
度为2结点数：1

## 2）二叉树的层序遍历  （先建队） ##

#include<iostream>
    #define MAXSIZE 100
    #define OVERFLOW -2
    #define ERROR -1
    #define OK 0
    using namespace std;
    typedef struct bitnode{
    	char data;
    	struct bitnode *lchild,*rchild;
    }bitnode,*bitree;
    typedef struct queue{
    	bitree *base;
    	int front,rear;
    }queue; 
    void createbitree(bitree &T){//创建二叉树 前序输入 
        char ch;
        cin>>ch;
        if(ch=='#') T=NULL;
        else{
        	T= new bitnode;
        	T->data=ch;
        	createbitree(T->lchild);
        	createbitree(T->rchild);
    	} 
    }
    int initqueue(queue &q){//创建队 
        q.base=new bitree[MAXSIZE];
        if(!q.base) exit(OVERFLOW);
        q.front=q.rear=0;
    }
    int push(queue &q,bitree e){//入队 
    	if((q.rear+1)%MAXSIZE==q.front)  return ERROR;
    	q.base[q.rear]=e;
    	q.rear=(q.rear+1)%MAXSIZE;
    	return OK;
    }
    int pop(queue &q,bitree &e){//出队 
    	if((q.front==q.rear)) return ERROR;
    	e=q.base[q.front];
    	q.front=(q.front+1)%MAXSIZE;
    	return OK; 
    }
    int emptyqueue(queue q){//判空 
    	if(q.front==q.rear) return OK;
    }
    void traverse(bitree T) {//层序遍历
        queue Q;
    	initqueue(Q);//初始化队列
    	bitree p=T;
    	bitree q;
    	q= new bitnode;
    	if(p){  //存在根节点 
    		push(Q,p); //入队 
    	}
    	while(emptyqueue(Q)){ //队非空 
    	   	pop(Q,q);  //出队 
    		cout<<q->data; //输出 
    		p=q;
    		if(p->lchild)   //左孩子入队 
    		  push(Q,p->lchild);
    		if(p->rchild)   //右孩子入队 
    		  push(Q,p->rchild); 
    		   
    	  }
    }
    int main(){
    	bitree T;
    	cout<<"输入："; 
    	createbitree(T);
    	cout<<"层序遍历：";
    	traverse(T);
    	return 0;
    }

### 输入：       ###

AB\#C\#\#DE\#\#\#\#

### 输出： ###

ABDCE

## 3)二叉树的非递归算法（手动建栈） ##

#include<iostream>
    #define MAXSIZE 100
    #define OVERFLOW -2
    #define ERROR -1
    #define OK 0
    using namespace std;
    typedef struct bitnode{
    	char data;
    	struct bitnode *lchild,*rchild;
    }bitnode,*bitree; 
    typedef struct {
    	bitree *top,*base;
    }sqstack; 
    void createbitree(bitree &T){//创建二叉树 前序输入 
        char ch;
        cin>>ch;
        if(ch=='#') T=NULL;
        else{
        	T= new bitnode;
        	T->data=ch;
        	createbitree(T->lchild);
        	createbitree(T->rchild);
    	} 
    }
    int  createsqstack(sqstack &S){//创建栈 
        S.base= new bitree[MAXSIZE];
        if(!S.base) exit(ERROR); 
    	S.top=S.base; return OK;
    } 
    int push(sqstack &S,bitree e){//入栈 
    	if(S.top-S.base==MAXSIZE) return ERROR;
    	*S.top++=e;
    	return OK;
    }
    int pop(sqstack &S,bitree &e){//出栈 
    	if(S.top-S.base==0) return ERROR;
    	e=*--S.top;
    	return OK; 
    }
    int emptysqstack(sqstack S){//判空 
    	if(S.top-S.base==0)
    	 return OK;
    }
    void roottraverse(bitree T){//前序遍历 
        sqstack S;
        createsqstack(S);
        bitree p=T;
        bitree q;
        q=new bitnode;
    	while(p||emptysqstack(S)){
    		if(p){
    			cout<<p->data;
    			push(S,p);
    			p=p->lchild;
    		}
    		else{
    			pop(S,q);
    			p=q->rchild;
    		}
    	} 
    } 
    void inordertraverse(bitree T){//中序遍历 
        sqstack S;
        createsqstack(S);
        bitree p=T;
        bitree q;
        q=new bitnode;
    	while(p||emptysqstack(S)){
    		if(p){
    			push(S,p);
    			p=p->lchild;
    		}
    		else{
    			pop(S,q);
    			cout<<q->data;
    			p=q->rchild;
    		}
    	} 
    }
    int main(){
    	bitree T;
    	cout<<"创建二叉树: ";
    	createbitree(T);
    	cout<<endl<<"前序遍历: ";
    	roottraverse(T);
    	cout<<endl<<"中序遍历: ";
    	inordertraverse(T);
         return 0;
    	
    }