二叉树的遍历和线索二叉树

二叉树遍历

二叉树结点的定义

typedef struct BiNode{Elemtype data;struct BiNode* lchild, *rchild; 
}BiNode, *BiTree; 

先序

递归算法

void PreOrder1(BiTree T){if(T!=NULL){visit(T);PreOrder(T->lchild);PreOrder(T->rchild);}
}

非递归算法（栈实现）

SqStack S;
void PreOrder2(BiTree T){BiNode *p=T;SqStack S;InitStack(S);while(p||!IsEmpty(S)){if(P){visit(p);Push(S, p);p=p->lchild;}else{Pop(S, p);p=p->rchild;}}return ;
}

中序

递归算法

void InOrder1(BiTree T){if(T!=NULL){PreOrder(T->lchild);visit(T);PreOrder(T->rchild);}
}

非递归算法

void InOrder2(BiTree T){BiNode *p=L;SqStack S;InitStack(S);while(p||!IsEmpty(S)){if(P){Push(S, p);p=p->lchild;}else{Pop(S, p);visit(p);p=p->rchild;}}return ;
}

后序

递归算法

void PostOrder1(BiTree T){if(T!=NULL){PreOrder(T->lchild);PreOrder(T->rchild);visit(T);}
}

非递归算法

void PostOrder2(BiTree T){BiNode *p=L;//将要进栈的结点 //需要设置一个指向上一个输出点的指针，用来实现中间结点最后输出； BiNode *pre=NULL; SqStack S;InitStack(S);while(p||!IsEmpty(S)){if(P){Push(S, p);p=p->lchild;}else{ GetTop(S, p);//取栈顶元素//若右孩子被访问过，一定是上一次访问的 if(p->rchild!=NULL&&p->rchild!=pre){p=p->rchild; }else{Pop(S, p);//出栈访问 visit(p); pre=p;//因为根据后序遍历某个点出栈，说明以这个点为根的//子树一定已经访问完了，无继续进栈结点，只能下一步从栈中找到后续进栈结点 p=NULL;}}}return ;
}

二叉树线索化

代码实质就是二叉树遍历过程！！！

结点定义

typedef struct ThreadNode{Elemtype data;struct ThreadNode* lchild, *rchild; int ltag, rtag;//线索标记 
}ThreaNode, *ThreadTree ; 

先序

递归算法

void PreThread1(ThreadTree T, ThreadNode *&pre){if(T!=NULL){//当前结点左孩子空，设置左线索，前驱节点 if(T->lchild==NULL){T->lchild=pre;T->ltag=1;//标记 }//上一个结点右孩子空，后驱结点指向当前结点 if(pre!=NULL&&pre->rchild==NULL){pre->rchild=p;pre->rtag=1;} pre=T;if(T->ltag==0){//先序是先修改，如不判断将死循环 PreThread1(T->lchild, pre);}PretThread1(T->rchild, pre);}
}

中序*

递归算法

void InThread1(ThreadTree T, ThreadNode *&pre){if(T!=NULL){InThread1(T->lchild, pre);//类似于中序visit //当前结点左孩子空，设置左线索，前驱节点 if(T->lchild==NULL){T->lchild=pre;T->ltag=1;//标记 }//上一个结点右孩子空，后驱结点指向当前结点 if(pre!=NULL&&pre->rchild==NULL){pre->rchild=p;pre->rtag=1;} pre=T;InThread1(T->rchild, pre);}
}
void CreateInThread(ThreadTree T){ThreadNode* pre=NULL;if(T!=NULL){InThread(T,pre);//想要pre指针改变，InThread1里pre设置引用 pre->rchild=NULL;pre->rtag=1;} 
}

后序

递归算法

//visit部分与中序几乎不变
void PostThread1(ThreadTree T, ThreadNode *&pre){if(T!=NULL){PostThread1(T->lchild, pre);PostThread1(T->rchild, pre);//当前结点左孩子空，设置左线索，前驱节点 if(T->lchild==NULL){T->lchild=pre;T->ltag=1;//标记 }//上一个结点右孩子空，后驱结点指向当前结点 if(pre!=NULL&&pre->rchild==NULL){pre->rchild=p;pre->rtag=1;} pre=T;}
}