一:二叉树的遍历. 由于递归算法很简单，在这里就不例举了，主要看一下非递归算法(其实也就是用栈实现，因为递归本身就是一种栈) 1.先序遍历: 思想:(1)从根节点依次遍历当前节点的左子树，边遍历访问，并且压入栈 (2).再访问当前栈顶结点的右子树,然后再返回
一:二叉树的遍历.
由于递归算法很简单，在这里就不例举了，主要看一下非递归算法(其实也就是用栈实现，因为递归本身就是一种栈)
     1.先序遍历:
          思想:(1)从根节点依次遍历当前节点的左子树，边遍历访问，并且压入栈
                   (2).再访问当前栈顶结点的右子树,然后再返回到(1)执行,直至栈空        
#define maxsize 100typedef struct{ bitree elem[maxsize]; int base,top;}sqstack;void preorderunrec(bitree t){ sqstack s; stackinit(s); p=t; while (p!=null || !stackempty(s)) { while (p!=null) //遍历左子树 { visite(p->data); push(s,p); p=p->lchild; }//endwhile if (!stackempty(s)) //通过下一次循环中的内嵌while实现右子树遍历 { p=pop(s); p=p->rchild; }//endif }//endwhile }//preorderunrec
2.中序遍历:      思想:(1)从根节点遍历左子树，边遍历边入栈
               (2)弹出栈顶元素，并访问，然后访问当前栈顶的右子树,回到(1)
#define maxsize 100typedef struct{ bitree elem[maxsize]; int base,top;}sqstack;void inorderunrec(bitree t){ sqstack s; stackinit(s); p=t; while (p!=null || !stackempty(s)) { while (p!=null) //遍历左子树 { push(s,p); p=p->lchild; }//endwhile if (!stackempty(s)) { p=pop(s); visite(p->data); //访问根结点 p=p->rchild; //通过下一次循环实现右子树遍历 }//endif }//endwhile}//inorderunrec
3.后序遍历(其实还不是特清楚，代码来自百度):(需要设置一个标志量表示当前节点的右子树是否被访问)
#define maxsize 100typedef enum{l,r} tagtype;//标记的类型，为r时表示当前结点的typedef struct { bitree ptr; tagtype tag;}stacknode;typedef struct{ stacknode elem[maxsize]; int base,top;}sqstack;void postorderunrec(bitree t){ sqstack s; stacknode x; stackinit(s); p=t; do { while (p!=null) //遍历左子树 { x.ptr = p; x.tag = l; //标记为左子树 push(s,x); p=p->lchild; } while (!stackempty(s) && s.elem[s.top].tag==r)//如果 { x = pop(s); p = x.ptr; visite(p->data); //tag为r，表示右子树访问完毕，故访问根结点 } if (!stackempty(s)) { s.elem[s.top].tag =r; //遍历右子树 p=s.elem[s.top].ptr->rchild; } }while (!stackempty(s));}//postorderunrec
二.线索二叉树:
             含有n个结点的二叉树,一共有2n个指针域,有n+1个处于null状态，为了使空间不浪费，可以让这些空的指针域指向二叉树各种遍历的前驱或后继结点,这样又可以方便查找每一个元素，而不必采用遍历，节省了时间
1.存储结构:
typedef enum { link, thread } pointerthr; // link==0:指针，thread==1:线索typedef struct bithrnode{ telemtype data; struct bithrnode *lchild, *rchild; // 左右孩子指针 pointerthr ltag, rtag; // 左右标志,当ltag=thread时，表示线索,为link时表示指向下一结点} bithrnode, *bithrtree;
1）若结点有左子树，则lchild指向其左孩子；
       否则， lchild指向其直接前驱(即线索)；
2).若结点有右子树，则rchild指向其右孩子；
     否则，rchild指向其后继(即线索)；
例：
2.线索二叉树的中序遍历算法:
status iotraver_t( bithrtree t,status (*visit)(telemtype e) ){ //t指向头结点，头结点的左链lchild指向根结点，中序遍历 //二叉线索树t的非递归算法，对每个数据元素调用函数visit。 p = t->lchild; //p指向根结点 while (p != t) { //空树或遍历结束时，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; } // iotraver_t
3.线索二叉树的生成算法:
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; // 保持pre指向p的前驱  inthreading(p->rchild); //右子树线索化 } } // inthreading
status inorderthreading(bithrtree & thrt, bithrtree t){ //中序遍历二叉树t,并将其中序线索化, thrt 指向头结点. if ( ! (thrt = (bithrtree) malloc ( sizeof (bithrnode) ) ) exit ( overflow ) ; thrt ->ltag = link; thrt ->rtag = thead; // 建头结点 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; } // inorderthreading