二叉树的非递归中序遍历（二叉线索存储结构）

   

    

     

      

     
     

      

       # include <stdio.h>
      
     
    

     

      

     
     

      

       # include <malloc.h>
      
     
    

     

      

     
     

      

       # include <stdlib.h>
      
     
    

     

      

     
     

      

       # include <iostream.h>
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       # define OK 1
      
     
    

     

      

     
     

      

       # define ERROR 0
      
     
    

     

      

     
     

      

       # define OVERFLOW -1
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       typedef char TElemType;
      
     
    

     

      

     
     

      

       typedef enum PointerTag { Link, Thread };
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       typedef struct BiThrNode 
      
     
    

     

      

     
     

      

       {
      
     
    

     

      

     
     

      

        TElemType data;
      
     
    

     

      

     
     

      
 struct BiThrNode *lchild, *rchild;
      
     
    

     

      

     
     

      

        PointerTag  LTag, RTag;
      
     
    

     

      

     
     

      

       }BiThrNode,*BiThrTree;
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       BiThrTree pre;
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       void InThreading(BiThrTree p)
      
     
    

     

      

     
     

      

       {
      
     
    

     

      

     
     

      
 if (p)
      
     
    

     

      

     
     

      

        {
      
     
    

     

      

     
     

      

         InThreading(p->lchild);
      
     
    

     

      

     
     

      
  
      
     
    

     

      

     
     

      
  if (!p->lchild)
      
     
    

     

      

     
     

      

         {
      
     
    

     

      

     
     

      

          p->LTag = Thread;
      
     
    

     

      

     
     

      

          p->lchild = pre;
      
     
    

     

      

     
     

      

         }
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
  if (! pre->rchild)
      
     
    

     

      

     
     

      

         {
      
     
    

     

      

     
     

      

          pre->RTag = Thread;
      
     
    

     

      

     
     

      

          pre->rchild = p;
      
     
    

     

      

     
     

      

         }
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

         pre = p;
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

         InThreading(p->rchild);
      
     
    

     

      

     
     

      

        }
      
     
    

     

      

     
     

      

       }
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       int InOrderThreading(BiThrTree &Thrt, BiThrTree T)
      
     
    

     

      

     
     

      

       {
      
     
    

     

      

     
     

      

        Thrt = (BiThrTree) malloc (sizeof (BiThrNode));
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
 if (!Thrt)
      
     
    

     

      

     
     

      
  exit (OVERFLOW);
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

        Thrt->LTag = Link;
      
     
    

     

      

     
     

      

        Thrt->RTag = Thread;
      
     
    

     

      

     
     

      

        Thrt->rchild = Thrt;
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
 if (!T)
      
     
    

     

      

     
     

      

         Thrt->lchild = Thrt;
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
 else
      
     
    

     

      

     
     

      

        {
      
     
    

     

      

     
     

      

         Thrt->lchild = T;
      
     
    

     

      

     
     

      

         pre = Thrt;
      
     
    

     

      

     
     

      

         InThreading(T);
      
     
    

     

      

     
     

      

         pre->rchild = Thrt;
      
     
    

     

      

     
     

      

         pre->RTag = Thread;
      
     
    

     

      

     
     

      

         Thrt->rchild = pre;
      
     
    

     

      

     
     

      

        }
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
 return OK;
      
     
    

     

      

     
     

      

       }
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       int CreateBiThrTree(BiThrTree &T)
      
     
    

     

      

     
     

      

       {
      
     
    

     

      

     
     

      

        TElemType ch;
      
     
    

     

      

     
     

      
 cin>>ch;
      
     
    

     

      

     
     

      
 if (ch == '#')
      
     
    

     

      

     
     

      

         T = NULL;
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
 else
      
     
    

     

      

     
     

      

        {
      
     
    

     

      

     
     

      

         T= (BiThrTree) malloc (sizeof (BiThrNode));
      
     
    

     

      

     
     

      

         T->data = ch;
      
     
    

     

      

     
     

      

         CreateBiThrTree(T->lchild);
      
     
    

     

      

     
     

      
  if (T->lchild)
      
     
    

     

      

     
     

      

          T->LTag = Link;
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

         CreateBiThrTree(T->rchild);
      
     
    

     

      

     
     

      
  if (T->rchild)
      
     
    

     

      

     
     

      

          T->RTag = Link;
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

        }
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
 return OK;
      
     
    

     

      

     
     

      

       }
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       int InOrderTraverse_Thr(BiThrTree T,int (*Visit)(TElemType e))
      
     
    

     

      

     
     

      

       {
      
     
    

     

      

     
     

      

        BiThrTree p;
      
     
    

     

      

     
     

      

        p = T->lchild ;
      
     
    

     

      

     
     

      
 while (p != T)
      
     
    

     

      

     
     

      

        {
      
     
    

     

      

     
     

      
  while (p->LTag == Link)
      
     
    

     

      

     
     

      

          p = p->lchild ;
      
     
    

     

      

     
     

      
  if (! Visit(p->data))
      
     
    

     

      

     
     

      
   return ERROR;
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
  while (p->RTag == Thread && p->rchild != T)
      
     
    

     

      

     
     

      

         {
      
     
    

     

      

     
     

      

          p = p->rchild ;
      
     
    

     

      

     
     

      

          Visit(p->data);
      
     
    

     

      

     
     

      

         }
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

         p = p->rchild ;
      
     
    

     

      

     
     

      

        }
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
 return OK;
      
     
    

     

      

     
     

      

       }
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       int Print(TElemType e)
      
     
    

     

      

     
     

      

       {
      
     
    

     

      

     
     

      
 cout<<e;
      
     
    

     

      

     
     

      
 return OK;
      
     
    

     

      

     
     

      

       }
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       int main(void)
      
     
    

     

      

     
     

      

       {
      
     
    

     

      

     
     

      

        BiThrTree T,H;
      
     
    

     

      

     
     

      
 cout<<"请按先序建立一棵二叉树,#代表空树!"<<endl;
      
     
    

     

      

     
     

      

        CreateBiThrTree(T);
      
     
    

     

      

     
     

      

        InOrderThreading(H,T);
      
     
    

     

      

     
     

      
 cout<<"它的中序遍历是:";
      
     
    

     

      

     
     

      

        InOrderTraverse_Thr(H,Print);
      
     
    

     

      

     
     

      
 cout<<endl;
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
 return 0;
      
     
    

     

      

     
     

      

       }
      
     
   





结果图：


 

文章来源: blog.csdn.net，作者：悦来客栈的老板，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/qq523176585/article/details/6772400