[C语言]实现层次建立二叉树 且用递归进行遍历

二叉树可以进行顺序存储，也可以用来链式存储，我们在此只用链式存储进行建立，并且使用链式存储进行二叉树的层次建立

1.建立二叉树、辅助链表、辅助队列结构体

typedef char CElemType;
//建立二叉树的对应的结构体
typedef struct BiTNode {
	CElemType data;
	struct BiTNode* lchild, * rchild;//创建二叉树的左右孩子
}BiTNode,*BiTree;

typedef BiTree ElemType;

//建立辅助链表进行辅助建树
typedef struct flag {
	BiTree p;
	struct flag* next;
}flag,*Tflag;

//建立队列实现层次遍历
typedef struct LinkNode {
	ElemType date;
	struct LinkNode* next;
}LinkNode;
typedef struct {
	LinkNode* front, * rear;
}LinkQueue;

2.辅助队列对应的相关函数，这里的ElemType是需要将二叉树传入，对二叉树中的元素进行入队与出队操作 

//辅助队列初始化
void LinkQuInit(LinkQueue& Q) {
	Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
	Q.front->next = NULL;
}

//辅助队列进行判空
bool judgeLQueue(LinkQueue Q) {
	if (Q.front == Q.rear)
		return true;
	else
		return false;
}

//辅助队列进行入队
bool EnterLQueue(LinkQueue& Q, ElemType x) {
	LinkNode* s = (LinkNode*)calloc(1, sizeof(LinkNode));
	s->date = x;
	s->next == NULL;
	Q.rear->next = s;
	Q.rear = s;
	return true;
}

//辅助队列进行出队
bool DeleteLQueue(LinkQueue& Q, ElemType& x) {
	if (Q.front == Q.rear)
		return false;
	LinkNode* p = Q.front->next;
	x = p->date;
	Q.front->next = p->next;
	if (Q.rear == p)
		Q.rear = Q.front;
	free(p);
	return true;
}

 3.二叉树的层次遍历、先序遍历、中序遍历、后序遍历

//层次建树
void LevelOrder(BiTree T) {
	LinkQueue Q;
	LinkQuInit(Q);
	BiTree p;
	EnterLQueue(Q, T);
	while (!judgeLQueue(Q)) {
		DeleteLQueue(Q, p);
		putchar(p->data);
		if (p->lchild != NULL)
			EnterLQueue(Q, p->lchild);
		if (p->rchild != NULL)
			EnterLQueue(Q, p->rchild);
	}
}

//先序遍历
void PreOrder(BiTree T) {
	if (T!=NULL){
		visit(T);
		PreOrder(T->lchild);
		PreOrder(T->rchild);
	}
}

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

//后序遍历
void PostOrder(BiTree T) {
	if(T != NULL) {
		PostOrder(T->lchild);
		PostOrder(T->rchild);
		visit(T);
	}
}

void visit(BiTree T) {
	printf("%c", T->data);
}

4.主函数进行层次建树 

1）首先建立二叉树树根T 并赋予NULL，其次建立TNew用来存储新节点

2）其次运用辅助链表，分别建立头Thead与尾Ttail，而当有节点加入的时候，Thead与Ttail是不移动的，在移动的是Ttemp，而listTNew代表链表中的新节点

3）给TNew申请空间，在此使用calloc是可以在申请空间的同时直接给lchild与rchild赋予空值，并将输入的值传给TNew的data

4）在给TNew申请的同时，还需要给listTNew申请空间，将TNew赋予p

5）判断是否为空树，如果为空树，则建立根节点，listTNew都赋给Thead与Ttail与Ttemp，continue结束；如果不为空树则将Ttail向后移动

6）之后判断左右子树是否为空，再赋值即可

int main() {
	BiTree T=NULL;
	BiTree TNew;
	char c = NULL;
	Tflag Thead = NULL, Ttail = NULL, listTNew, Ttemp;
	while (scanf("%c", &c) != EOF) {
		if (c == 'n')
			break;
		TNew = (BiTNode*)calloc(1, sizeof(BiTNode));
		TNew->data = c;
		listTNew = (flag*)calloc(1, sizeof(flag));
		listTNew->p = TNew;
		if (T == NULL) {
			T = TNew;
			Thead = listTNew;
			Ttail = listTNew;
			Ttemp = listTNew;
			continue;
		}
		else {
			Ttail->next = listTNew;
			Ttail = listTNew;
		}
		if (Ttemp->p->lchild == NULL) {
			Ttemp->p->lchild = TNew;
		}
		else if (Ttemp->p->rchild == NULL) {
			Ttemp->p->rchild = TNew;
			Ttemp = Ttemp->next;
		}
	}
	printf("n层次遍历n");
	LevelOrder(T);
	printf("n前序遍历：n");
	PreOrder(T);
	printf("n中序遍历：n");
	InOrder(T);
	printf("n后序遍历：n");
	PostOrder(T);
	return 0;
}

5.运行实际结果

6.闲话 

最初研究这个的时候，也不是特别的理解，到现在也不敢说100%的理解，所以如果有问题可以评论区留言，我会进行改进，如果这个对你有一定帮助，还请给我点个赞