二叉树层次建树，前序（递归与非递归）遍历--中序遍历（递归与非递归）-后序遍历-层次遍历

忘是亡心i 2023-09-29 11:26 69阅读 0赞

## 创建一个二叉树 ##

创建项目为创建C++项目

### 1.导包 ###

开始前需要写一些导包

#define _CRT_SECURE_NO_WARNINGS
    #include<stdio.h>
    #include<stdlib.h>

\_CRT\_SECURE\_NO\_WARNINGS这一串写或者不写跟你使用的编译器有关，此处是为了解决scanf（）的正常run----此处我用的是visual Studio 2022

### 2.类型别名设定 ###

#define MaxSize 50
    typedef  int ElemType;
    typedef char BiElemType;

### 3.结构引入 ###

二叉树的结构

typedef struct BiTNode {
          //二叉树的树节点
    	BiElemType c;//c就是书籍上的data
    	struct BiTNode* lchild;
    	struct BiTNode* rchild;
    }BiTNode,*BiTree;

储存树节点的队列节点

typedef struct tag {
         //储存树节点的队列节点
    	BiTree p;//树
    	struct tag* pnext;
    }tag_t,*ptag_t;

#### 递归实现 前序遍历（先序遍历） ####

（先打印当前节点，再打印左孩子，再打印右孩子）

//递归实现 前序遍历（先序遍历）（先打印当前节点，再打印左孩子，再打印右孩子）
    void preOrder(BiTree p) {
        
    	if (p != NULL) {
        
    		putchar(p->c);//等价于visit函数
    		preOrder(p->lchild);
    		preOrder(p->rchild);
    	}
    }

#### 中序遍历 ####

//中序遍历
    void InOrder(BiTree p) {
        
    	if (p!=NULL) {
        
    		InOrder(p->lchild);
    		putchar(p->c);
    		InOrder(p->rchild);
    	}
    }

#### 后序遍历 ####

void PostOrder(BiTree p) {
        
    	if (p != NULL) {
        
    		PostOrder(p->lchild);
    		PostOrder(p->rchild);
    		putchar(p->c);
    	}
    }

#### 中序遍历非递归， ####

非递归执行效率更高，需要借助**栈**来进行  
因此先创建栈的结构

//typedef BiTree ElemType  
    //上行代码 当与写在一个页面的时候感觉会与之前设定的产生不必要的混淆
    //因此，将所有的原本的 ElemType 修改为  BiTree 
    //如果你单独使用 上行代码时，也可以将BiTree 修改为ElemType 
    typedef struct {
           //栈
    	
    	BiTree data[MaxSize];
    	int top;
    }SqStack;
    
    //初始化栈
    void InitStack(SqStack& S) {
        
    	S.top = -1;
    }
    
    bool StackEmpty(SqStack& S) {
        
    	if (S.top==-1) {
        
    		return true;
    	}
    	else {
        
    		return false;
    	}
    }
    //入栈
    bool Push(SqStack& S, BiTree x) {
        
    
    	if (S.top==MaxSize-1) {
        
    		return false;
    	}
    	S.data[++S.top] = x;
    	return true;
    }
    //出栈
    bool Pop(SqStack& S, BiTree&x) {
        
    	if (-1==S.top) {
        
    		return false;
    	}
    	x = S.data[S.top--];
    	return true;
    }
    //获取栈顶元素
    bool GetTop(SqStack& S, BiTree& x) {
        
    	if (-1 == S.top) {
        
    		return false;
    	}
    	x = S.data[S.top];
    	return true;
    }
    
    //中序遍历非递归，非递归执行效率更高，
    //中序遍历非递归
    void InOrder2(BiTree T) {
        
    	SqStack S;
    	InitStack(S);//初始化栈
    	BiTree p = T;
    
    	while (p || !StackEmpty(S)) {
          //逻辑 或者 ||
    	
    		if (p) {
        
    			Push(S,p);
    			p = p->lchild;
    		}
    		else {
        
    			Pop(S, p);
    			putchar(p->c);
    			p = p->rchild;
    		}
    	}
    }

#### 层次遍历（广度优先遍历） ####

//初始化队列  带头节点的队列
    void InitQueue(LinkQueue& Q) {
        
    	Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
    	Q.front->next = NULL;
    }
    bool IsEmpty(LinkQueue Q) {
        
    	if (Q.front==Q.rear)
    	{
        
    		return true;
    	}
    	else {
        
    		return false;
    	}
    }
    
    //入队
    void EnQueue(LinkQueue& Q, BiTree x){
        
    	LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));
    	s->data = x;
    	s->next = NULL;
    	Q.rear->next = s;
    	Q.rear = s;
    }
    //出队
    bool DeQueue(LinkQueue &Q,BiTree &x) {
        
    	if (Q.front == Q.rear) {
        
    		return false;
    	}
    	LinkNode* p = Q.front->next;//头结点什么都没存，所以头结点的下一个结点才有数据
    	x = p->data;
    	Q.front->next = p->next;
    	if (Q.rear == p) {
        
    		Q.rear = Q.front;
    	}
    	free(p);
    	return true;
    
    }
    
    //层次遍历 （广度优先遍历） 运用到辅助队列
    void LevelOrder(BiTree T) {
        
    	LinkQueue Q;//辅助队列
    	InitQueue (Q);//初始化队列
    	BiTree p;
    	EnQueue(Q,T);//树根入队
    	while (!IsEmpty(Q)) {
        
    		DeQueue(Q,p);
    		putchar(p->c);
    		if (p->lchild!=NULL)
    		{
        
    			EnQueue(Q, p->lchild);
    
    		};
    		if (p->rchild!=NULL)
    		{
        
    			EnQueue(Q, p->rchild);
    
    		}
    	}
    
    }

### 主函数 ###

int main() {
        
    
    	// ①树根要置空  队列初始化
    	
    	BiTree pnew; //二叉树结构指针
    	//int i, j, pos;
    	char c;
    	BiTree tree = NULL;//树根（主）  
    	 
    	ptag_t phead = NULL, ptail = NULL, listpnew = NULL, pcur=NULL;
    	//phead队列头 ptail队列尾 不带头节点的队列  pcur始终指向要插入的节点的位置
    	
    //②数据开始进入  abcdefghij   ||一开始a进来 
    
    	while (scanf("%c",&c) != EOF) {
        
    		//结束循环
    		if (c == '\n') {
        //等于回车退出循环
    			break;
    		}
    		
    //③新建一个二叉树的节点空间 用于存储进来的a
    
    		//将数据放入空间   pnew二叉树结构指针内有 c  lchild  rchild 三个参数
    		//    ||当a刚进来时，new一个树的节点空间
    		pnew = (BiTree)calloc(1, sizeof(BiTNode));//pnew通过calloc申请一个空间并且对空间进行初始化，赋值0
    		pnew->c = c;//将数据放入pnew->c中 （放入树中）
    
    //④新建一个队列的节点空间 将整个二叉树节点存入队列
    
    		//listpnew 队列链表  内有 p  pnext 两个参数  
    		//p（树节点）中有 c  lchild  rchild      
    		//pnext中为p pnext
    		listpnew = (ptag_t)calloc(1,sizeof(tag_t));//给队列节点申请一个空间，
    		listpnew->p = pnew;  //将树节点作为数据存入队列   
    
    //⑤首次存a时，树还为空 需要走下边的判断 	
    			   
    		if (NULL == tree) {
        //当主树根若为空，构建辅助队列
    		//a放入树根
    			tree = pnew;//树的根  此时让a作为树根
    		//a放入队列
    			//此时 由于队列中只有一个a，因此a既做队列头也做队列尾
    			phead = listpnew;//队列头 队列头指针  
    			ptail = listpnew;//队列尾 队列尾指针   队列中储存的是树节点的地址	
    			pcur = listpnew; //pcur始终指向要插入的节点的位置
    //⑥ continue 此次循环结束
    			continue;
    		}
    		
    //⑦  ①-④步相同  不过此时进入的是b 放入队列，通过尾插法
    		else {
        //b当已经有主树的时候
    			ptail->pnext = listpnew;//   新结点B放入队列，通过尾插法
    			ptail = listpnew;//ptail队列尾指针 指向队列尾（新插入的b）
    		}
    		
    //⑧  队列判断结束后，开始判断b进入树
    		
    //⑨ a节点树的左孩子若为空  新节点b放在tree的lchild里
    
    		if (NULL == pcur->p->lchild) {
        //pcur为首次存放入a的时候给的定义
    			pcur->p->lchild = pnew;   //pcur始终指向要插入的节点的位置
    		}
    //⑩ 1-8相同 但9不同 a节点树的左孩子存在值  新节点c放在tree的rchild里
    		else if(NULL == pcur->p->rchild){
        
    			pcur->p->rchild = pnew;  //pcur始终指向要插入的节点的位置
    			pcur = pcur->pnext;//当左右孩子都放了后，就pcur指向下一个
    		}
    
    	}
    
    	printf("答案输出\n");
    	printf("------------前序遍历------------\n"); //（先打印当前节点，再打印左孩子，再打印右孩子）
    		preOrder(tree);//abc    a bde cfg    a b dhi ej c fg
    
    
    	printf("\n------------中序遍历------------\n");//（先打印打印左孩子，再打印当前节点,再打印右孩子）--------从上到下一脚踩扁
    		InOrder(tree);		//bac     dbe a fcg  hdibjeafcg
    
    	printf("\n------------后序遍历------------\n");//先打印打印左孩子，再打印右孩子,再打印当前节点
    		PostOrder(tree);//bca   deb fgc a      hid jeb fgc a     hidjebfgca
    
    	//printf("\n------------中序遍历非递归------\n");//难度比较大
    	//	InOrder2(tree);
    
    	//printf("\n------------层次遍历------------\n");
    
    }