C语言督学营 ，学习笔记，龙哥永远的神

第七次直播

队列的链式存储

队列的链式表示称为链队列，它实际上是一个同时带有队头指针和队尾指针的单链表。头指针指向队头结点，尾指针指向队尾结点，即单链表的最后一个结点。

链表队列的定义

二叉树

树的定义：树是n（n≥0）个节点的有限集。当n=0时，称为空树。在仼意一棵非空树中应满足：1）有且仅有一个特定的称为根的结点。2）当n>1时，其余节点可分为m（m>0）个互不相交的有限集T1，T2…，Tm，其中每个集合本身又是一棵树，并且称为根的子树。 二叉树的定义 ：

满二叉树与完全二叉树

二叉树的存储

顺序存储 链式存储

二叉树的建立

定义

二叉树的建树（层次建树，思考为什么借助队列建树），前序、中序、后序遍历、中序非递归遍历、层次遍历

calloc

calloc申请空间并对空间进行初始化，赋值为0（填的是二进制的零）, 好处在于省的 malloc 之后需要赋值为 null

BiTree pnew;
	int i,j,pos;
	char c;
	BiTree tree=NULL;//树根
	ptag_t phead=NULL,ptail=NULL,listpnew,pcur;//phead就是队列头，ptail就是队列尾
	//abcdefghij
	while(scanf("%c",&c)!=EOF)
	{
          
   
		if(c==
)
		{
          
   
			break;
		}
		pnew=(BiTree)calloc(1,sizeof(BiTNode));//calloc申请空间并对空间进行初始化，赋值为0
		pnew->c=c;//数据放进去
		listpnew=(ptag_t)calloc(1,sizeof(tag_t));//给队列结点申请空间
		listpnew->p=pnew;
		if(NULL==tree)
		{
          
   
			tree=pnew;//树的根
			phead=listpnew;//队列头
			ptail=listpnew;//队列尾
			pcur=listpnew;
			continue;
		}else{
          
   
			ptail->pnext=listpnew;//新结点放入链表，通过尾插法
			ptail=listpnew;//ptail指向队列尾部
		}//pcur始终指向要插入的结点的位置
		if(NULL==pcur->p->lchild)//如何把新结点放入树
		{
          
   
			pcur->p->lchild=pnew;//把新结点放到要插入结点的左边
		}else if(NULL==pcur->p->rchild)
		{
          
   
			pcur->p->rchild=pnew;//把新结点放到要插入结点的右边
			pcur=pcur->pnext;//左右都放了结点后，pcur指向队列的下一个
		}

层序遍历建树的过程：(注意这队列不带头节点)

注意： pcur=pcur->pnext; 代表指向下一层

可以通过监视窗口理解层序遍历的建树过程如下

前序遍历递归打印相对于（非递归）比较简单

龙哥的前序遍历的后方法

第八次直播

二叉树中序-后序-层序遍历

中序遍历

后序遍历同理

中序遍历非递归写法 （非重点)

主体思路为不断压栈的过程找到了最左边的左孩子

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);
	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);
	}
}

线索二叉树

一般出小题不可能出大题 以中序线索二叉树的建立为例。附设指针pre指向刚刚访问过的结点，指针p指向正在访问的结点，即pre指向p的前驱。在中序遍历的过程中，检查p的左指针是否为空，若为空就将它指向pre;检查pre的右指针是否为空，若为空就将它指向p

线索二叉树的建立代码

层序遍历的分析过程