二叉树的递归、非递归、线索化、层序遍历

遍历的思路

1. 递归遍历（先序、中序、后序）
2. 利用栈实现非递归（先序、中序、后序）
3. 二叉树的线索化（中序）
4. 层序遍历

递归遍历

递归代码简洁，下列出先序递归

void preorder(bitnode *t)
{
 if(t)
 {
  printf("%d ",t->ch);
  preorder(t->lchild);
  preorder(t->rchild);
 }
 else
 return ;
}
           

中序与后序类似，不再赘述

栈结构实现非递归遍历

三种遍历的遍历路径都相同，只是访问的顺序不同

（一）先序遍历

思路：

1.遍历输出左子结点，并入栈。（访问根，并遍历访问左子结点）

2.节点弹出栈，转向遍历每个弹出节点的右子结点（回溯遍历右子结点）

void preorder2(bitnode *t)
{
 seqstack s;
 s.top=0;//初始化栈
 while(s.top||t)
 {
  while(t) //输出根结点并遍历输出左子树
  {
   printf("%d ",t->ch);
   pushstack(&s,t);
   t=t->lchild;
  }
  if(s.top)//回溯访问右子树
  {
   t=popstack(&s);
   t=t->rchild;
  }
 }
}
           

（二）中序遍历

思路：

1.遍历左子结点，并入栈。（遍历左子结点）

2.节点弹出栈并访问，转向遍历每个弹出节点的右子结点（访问左结点，并回溯 遍历根和右子树）

void inorder2(bitnode *t)
 {
  seqstack s;
  s.top=0;
  while(s.top||t)
  {
   while(t)
   {
    pushstack(&s,t);
    t=t->lchild;
   }
   if(s.top)
   {
    t=popstack(&s);
    printf("%c ",t->data);  
    t=t->rchild;
   }
  }
 }
           

（三）后序遍历

注意要记录访问过的右节点。

思路：

1.遍历左子结点，并入栈。（遍历左子结点）

2.节点弹出栈并访问，转向遍历每个弹出节点的右子树（访问左结点，并回溯访问右子树）

细节：遍历右子树，若右子结点已访问，访问根结点，否则，递归访问右结点

void postorder2(bitnode *t)
{
 bitnode *q;  //标记已访问 
 seqstack s;
 s.top=0;
 while(s.top||t)
 {
  while(t)
  {
   pushstack(&s,t);
   t=t->lchild;
  }
  if(s.top)
  {
   t=popstack(&s);
   if(t->rchild==NULL || t->rchild==q) //如果是 无右节点节点 或  右子节点已经访问过 
   {
    q=t;
    printf("%d ",t->data);
    t=NULL;
   }
   else  //遍历到无右节点为止 
   t=t->rchild;
  }
 }
 } 
           

线索二叉树（中序）

二叉树复杂的非线性结构在遍历时难以确定前驱和后继结点。

n个结点的二叉树有n+1个空指针，将这些空指针域来存放前驱或后继结点来实现线索化，便于遍历。

typedef struct TREE
{
 int data;
 int ltag,rtag;
 struct TREE *lchild,*rchild;
}bitnode;
           

线索化的

1. 创建一个root节点（方便我们循环遍历）

   root 结构如下

root=(bitnode*)malloc(sizeof(bitnode));
 root->ltag=0; //左子结点为根节点
 root->rtag=1; 
 if(!t)
 root->lchild=root;
 else
 {
  root->lchild=t;
 }
 pre=root; 
 inthread(t); 
 pre->rchild = root;
 root->rtag=1;
 root->rchild=pre;
           

1. 在中序遍历的过程中线索化

   我们使用 pre 与 p 指针进行遍历，只能获取 前驱结点 和 当前结点 的信息。

   （1）前驱线索化：p->lchild = pre;

   （2）后继线索化：pre->rchild = p;(即后继线索要延迟到下一次线索化的过程)

   线索化代码如下

void inthread(bitnode *p)  //更新 *p 
{
 if(p)
 {
//在左子树遍历过程中线索化
  inthread(p->lchild);        //左子树线索化 
//根结点线索化
  if(p->lchild==NULL)         //前驱线索化 
  {
   p->ltag=1;
   p->lchild = pre; 
  }
  if(pre->rchild==NULL)      //后继线索化 
  {
   pre->rtag = 1;
   pre->rchild = p;
  }
  pre = p;                 //更新 *pre 
//在右子树遍历过程中线索化  
  inthread(p->rchild);    //右子树线索化 
 }
}
           

线索化过程的注意点

（1）. root结点的定义

（2）. pre为全局变量

（3）. 线索化过程类似于递归中序遍历二叉树，只是将访问的过程改为了线索化的过程

（4）.注意前驱化在当前迭代过程，而后继化在下一个迭代过程。（理解这个便于我们判断 p 和 pre 指针的位置）

线索化之后便于我们查找下一个结点和上一个结点

层序遍历

使用队列的数据结构来实现层序遍历

代码如下

void levelorder(bitnode *t)
{
 seqque q;
 bitnode *pre,*p;
 q.flag=0;
 q.front=q.rear=0;
 enqueue(&q,t);
 while(q.front!=q.rear||q.flag!=0)
//如果t有左右孩子节点，t出队，左右孩子节点入队列。否则，t出队 
 {
  t=dequeue(&q);
  printf("%d ",t->data);
  if(t->lchild)
  enqueue(&q,t->lchild);
  if(t->rchild)
  enqueue(&q,t->rchild);
 }
}