• 线索二叉树的实现。
  // main.cpp
  // test
  //
  // Created by 梁亚宾 on 16/6/4.
  // Copyright © 2016年 liang. All rights reserved.
  //

        //#include <iostream>
        #include <stdio.h>
        #include <stdlib.h>
  
        typedef char ElemType;
  
        ///link 左右左孩子 thread前后继线索
        typedef enum {link, thread} PointerTag;
  
        typedef struct BiThrNode
        {
            char data;
            struct BiThrNode *lchild,*rchild;
            PointerTag lTag;
            PointerTag rTag;
        }BiThrNode, *BiThrTree ;
  
        ///全局变量,始终指向刚刚访问过的结点
        BiThrTree pre;
  
        /// 创建一个二叉树，约定用户遵照前序遍历的方式输入数据
        void CreateBithrTree(BiThrTree *T){
            
            char c;
            scanf("%c",&c);
            
            if (' ' == c){
                
                *T = NULL;
                
            }else{
                
                *T = (BiThrNode *)malloc(sizeof(BiThrNode));
                (*T)->data = c;
                (*T)->lTag = link;
                (*T)->rTag = link;
                
                CreateBithrTree(&(*T)->lchild);
                CreateBithrTree(&(*T)->rchild);
            }
            
        }
  
        ///中序遍历 线索化
        void InThreading(BiThrTree T){
  
            if (!T) {
                return ;
            }
            
            InThreading(T->lchild);//递归左孩子。线索化
            
            if(!T->lchild){
                
                T->lTag = thread;  //记录左边为线索
                T->lchild = pre;  // 记录指向上一个索引
            }
            
            if (!pre->rchild){//前一个指向下一个为索引
                
                pre->rTag = thread; //记录右边为索引
                pre->rchild = T;   //记录指向下一个
            }
            
            InThreading(T->rchild);//递归右孩子 线索化
            
        }
  
        void InOrderThreading(BiThrTree *p,BiThrTree T){
            
            *p = (BiThrTree)malloc(sizeof(BiThrNode));
            (*p)->lTag = link;
            (*p)->rTag = thread;
            if (!T){
                
                (*p)->lchild = *p;
                
            }else{
                
                (*p)->lchild = T;
                pre = *p;
                InThreading(T);
                
                pre->rchild = *p;
                pre->rTag = thread;
                (*p)->rchild = pre;
            }
            
        }
  
        int main(){
           
            BiThrTree P,T = NULL;
            
            CreateBithrTree(&T);
            
            InOrderThreading(&P, T);
            
            return 0;
        }
  

个人博客： www.liangtongzhuo.com