二叉树的建立以及遍历

其实建立的方式和遍历是一个意思.也是利用了递归的原理.只不过在原来应该是输出结点的地方，改成了生成结点，然后给这个结点进行赋值操作。所以理解了遍历就很容易理解建立.
  1 #include "stdafx.h"
  2 #include <iostream>
  3 #include <exception>
  4 #include<string>
  5 using namespace std;
  6 
  7 
  8 typedef char TElemType;
  9 typedef int Status;
 10 const int ok = 1;
 11 const int error = 0;
 12 typedef struct BiTNode
 13 {
 14     TElemType data;
 15     struct BiTNode *left,*right;
 16 }BiTNode,*BiTree;
 17 
 18 //前序遍历
 19 void PreOrderTraverse(BiTree T)
 20 {
 21     if(T==NULL) return;
 22     cout<<T->data<<" ";//显示该结点的数据
 23     PreOrderTraverse(T->left);
 24     PreOrderTraverse(T->right);
 25 }
 26 //中序遍历
 27 void InOrderTraverse(BiTree T)
 28 {
 29     if(T==NULL) return ;
 30     InOrderTraverse(T->left);
 31     cout<<T->data<<" ";
 32     InOrderTraverse(T->right);
 33 }
 34 
 35 //后序遍历
 36 void PostOrderTraverse(BiTree T)
 37 {
 38     if(T==NULL) return ;
 39     InOrderTraverse(T->left);

 40     InOrderTraverse(T->right);
 41     cout<<T->data<<" ";
 42 }
 43 
 44 //建立二叉树
 45 void CreateBiTree(BiTree &T)
 46 {
 47     TElemType ch;
 48     cin>>ch;
 49     if(ch=='#')
 50     {
 51         T=NULL;
 52     }else
 53     {
 54         T=(BiTree)malloc(sizeof(BiTree));
 55         if(!T)
 56             exit(OVERFLOW);
 57         T->data = ch;
 58         CreateBiTree(T->left);
 59         CreateBiTree(T->right);
 60     }
 61 }
 62 
 63 
 64 //线索二叉树的线索存储结构定义代码如下
 65  enum PointerTag{Link,Thread};//默认Link为0,Thread为1
 66 
 67 
 68 typedef struct BiThrNode
 69 {
 70     TElemType data;//结点数据
 71     struct BiThrNode *lchild,*rchild;//左右孩子指针
 72     PointerTag LTag;
 73     PointerTag RTag;
 74 }BithrNode,*BiThrTree;
 75 
 76 //中序遍历线索化的递归函数
 77 BiThrTree pre;//全局变量,始终指向刚刚访问过的结点.
 78 void InThreading(BiThrTree p)
 79 {
 80     if(p)
 81     {
 82         InThreading(p->lchild);//递归左子树线索化
 83         if(!p->lchild)
 84         {
 85             p->LTag = Thread;
 86             p->lchild = pre;
 87         }
 88         if(!pre->rchild)
 89         {
 90             p->RTag = Thread;
 91             p->rchild=p;
 92         }
 93         pre = p;
 94         InThreading(p->rchild);
 95     }
 96 }
 97 
 98 Status InOrderTraverse_Thr(BiThrTree T)
 99 {
100     BiThrTree p;
101     p = T->lchild;//p指向根结点
102     while(p != T)//遍历结束时,p==T;
103     {
104         while (p->LTag==Link)//找到中序序列的第一个结点.一直找到最左边的左孩子
105             p = p->lchild;
106         cout<<p->data<<endl;//输出第一个元素.下面就不断输出后继
107         while(p->RTag==Thread&&p->rchild!=T)//只要一直是后继,且不是T的话
108         {
109             p = p->rchild;
110             cout<<p->data<<endl;
111         }
112         p = p->rchild;//p进至其右子树
113 
114     }
115     return ok;
116 
117 }
118 int _tmain(int argc, _TCHAR* argv[])
119 { 
120     
121 
122     return 0 ;
123 }
前序遍历输入:AB#D##C##就实现了.