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

       # 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