二叉树层次建树+遍历

//二叉树层次建树+画图 2024-02-12
#include <iostream>
#include <cstdio>

using namespace std;

//树结点的数据结构
typedef char ElemType;
typedef struct TNode{
   ElemType c; //即data
   struct TNode *lchild, *rchild; //左右孩子指针
}TNode,*Tree;

//需要一个用于辅助的链式队列
typedef struct LinkNode{
   TNode * data; //用于存储树结点的地址，藏宝图
   struct LinkNode *pnext;
}LinkNode;

typedef struct {
   LinkNode *phead, *ptail;
}LinkQueue;

//链队列部分
//下次应该把TNode * 取个别名，这样代码更容易移植通用
bool IsEmpty(LinkQueue Q)
{
   return Q.phead == NULL && Q.ptail == NULL;
}
//获取队头元素值
bool GetTop(LinkQueue Q, TNode *&x)
{
   if(IsEmpty(Q))
   {
       return false;
   }
   x = Q.phead->data;
   return true;
}
//入队
bool EnQueue(LinkQueue &Q, TNode *x)
{
   LinkNode *pnew = (LinkNode*)calloc(1, sizeof(LinkNode));
   pnew->data = x;//因为是calloc就不用pnew->pnext = NULL; 
   Q.ptail->pnext = pnew;
   Q.ptail = pnew; //队尾指针指向新插入的最后一个结点
   return true;
}
//出队,队头出队
bool DeQueue(LinkQueue &Q, TNode *&x)
{
   if(IsEmpty(Q))
   {
       return false;
   }
   x = Q.phead->data;
   LinkNode *q = Q.phead;
   Q.phead = Q.phead->pnext;
   if(Q.phead == NULL)//如果删除的是最后一个结点
   {
       Q.ptail = Q.phead;
   }
   free(q);
   return true;
} 

//二叉树递归遍历
//先序遍历
void preOrder(Tree T)
{
   if(T != NULL)
   {
       printf("%c", T->c);
       preOrder(T->lchild);
       preOrder(T->rchild);
   }
}

//abcdefghij
int main()
{
   ElemType c;
   Tree T = NULL;
   LinkQueue Q;//定义一个用于辅助层次建树的链队列
   Q.phead = Q.ptail = NULL;
   LinkNode *pcur;
   while(scanf("%c", &c) != EOF)
   {
       if(c == '\n')
           break;
       if(NULL == T) //如果是第一个结点，就作为根结点
       {
           T = (Tree)calloc(1, sizeof(TNode)); //用calloc把整个结点数据置0，即NULL
           T->c = c;
           LinkNode *p = (LinkNode *)calloc(1, sizeof(LinkNode));
           p->data = T;
           Q.phead = Q.ptail = p;
           pcur = p;
           continue;
       }
       //不是第一个输入的结点
       TNode *tnew = (TNode *)calloc(1, sizeof(TNode));
       tnew->c = c;
       EnQueue(Q, tnew); //入队，入链队列
       if(pcur->data->lchild == NULL)//建树
       {
           pcur->data->lchild = tnew;
       }
       else if(pcur->data->rchild == NULL)
       {
           pcur->data->rchild = tnew;
           pcur = pcur->pnext;//左右孩子都满了指向链队列的下一个结点
       }
   }
   preOrder(T);
   printf("\n");
   return 0;
}

//中序遍历递归
void InOrder(BiTree t)
{
	if (t)//要设置递归出口
	{
		InOrder(t->lchild);
		putchar(t->c);
		InOrder(t->rchild);
	}
}
//中序遍历非递归，需要构思
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 LevelOrder(BiTree t)
{
	LinkQueue Q;
	InitQueue(Q);
	BiTNode* p = t;
	EnQueue(Q, p);//树根入队
	while (!IsEmpty(Q))
	{
		DeQueue(Q, p);//出队当前结点并打印
		putchar(p->c);
		if (p->lchild)
		{
			EnQueue(Q, p->lchild);
		}
		if (p->rchild)
		{
			EnQueue(Q, p->rchild);
		}
	}
	printf("\n");
}