//后序线索，这种方法不容易想到
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<algorithm> 5 6 using namespace std; 7 8 struct TREE{ 9 int val; 10 TREE *ch[2]; 11 TREE *thread;//该节点的线索的下一个节点 12 TREE(){} 13 TREE(int val){ 14 this->val = val; 15 ch[0] = ch[1] = NULL; 16 thread = NULL; 17 } 18 }; 19 20 void buildT(TREE * &T){ 21 int x; 22 scanf("%d", &x); 23 if(x == -1) return ; 24 25 T = new TREE(x); 26 buildT(T->ch[0]); 27 buildT(T->ch[1]); 28 } 29 30 31 void postThread(TREE *T, TREE *pre){ 32 if(!T) return; 33 postThread(T->ch[0], T); 34 postThread(T->ch[1], T); 35 if(pre){ 36 if(pre->ch[0] == T && pre->ch[1])//T是左子树 37 T->thread = pre->ch[1]; //T的下一个节点就是它的兄弟节点 38 else //T是右子树 39 T->thread = pre;//T的下一个节点就是它 的父亲节点 40 } 41 } 42 43 void printT_pre(TREE *T){//前序打印 44 if(!T) return ; 45 printf("%d ", T->val); 46 printT_pre(T->ch[0]); 47 printT_pre(T->ch[1]); 48 } 49 50 void printT_Thread(TREE *T){//后序线索打印 51 TREE *root = T; 52 bool flag = true;//表明T所在的字数没有访问过 53 while(1){ 54 while(flag && T->ch[0]) T = T->ch[0]; 55 printf("%d ", T->val); 56 if(T->thread->ch[0] == T || T->thread->ch[1] == T) 57 flag = false;//如果 T没有兄弟节点了，就一直沿着它的父节点向上走 58 else flag = true; 59 T = T->thread; 60 if(T == root){//再次回到最顶端父节点时， 结束！ 61 printf("%d ", T->val); 62 break; 63 } 64 } 65 } 66 67 int main(){ 68 TREE *T = NULL; 69 buildT(T); 70 printT_pre(T); 71 printf("\n"); 72 postThread(T, NULL); 73 printT_Thread(T); 74 printf("\n"); 75 return 0; 76 }
下面是基本按照同样的套路实现二叉树的先序，中序，后序的线索
//先序线索
#include<stdio.h> #include<stdlib.h> #define Thread 1 #define Tlink 0 typedef struct tree { int d; struct tree* lchild; struct tree* rchild; int Ltag, Rtag; }*TREE; void build_tree(TREE &T) { int d; scanf("%d", &d); if(d!=-1) { T=(TREE)malloc(sizeof(tree)); T->d=d; T->lchild=T->rchild=NULL; T->Ltag=T->Rtag=Tlink; build_tree(T->lchild); build_tree(T->rchild); } } TREE pre; void preThread_tree(TREE p) { if(p) { if(!p->lchild) { p->lchild=pre; p->Ltag=Thread; } if(!pre->rchild) { pre->rchild=p; pre->Rtag=Thread; } pre=p; if(p->Ltag==Tlink)//考虑到只有一个结点或两个节点情况， preThread_tree(p->lchild);//如果没有 if语句可能出现死循环 if(p->Rtag==Tlink) preThread_tree(p->rchild); } } void print_preThr_tree(TREE T) { TREE p=T; while(1) { while(p->Ltag==Tlink) { printf("%d ", p->d); p=p->lchild; } printf("%d ", p->d); p=p->rchild; if(p==T) break; while(p->Rtag==Thread) { printf("%d ", p->d); p=p->rchild; } } } void print_tree(TREE T) { if(T) { printf("%d ", T->d); print_tree(T->lchild); print_tree(T->rchild); } } int main() { TREE T=NULL; build_tree(T); print_tree(T);//递归先序遍历 printf("\n"); pre=T; preThread_tree(T);//非递归先序遍历 pre->rchild=T; print_preThr_tree(T); return 0; }
//中序线索
#include<stdio.h> #include<stdlib.h> #define Thread 1 #define Tlink 0 typedef struct tree { int d; struct tree* lchild; struct tree* rchild; int Ltag, Rtag; }*TREE; void build_tree(TREE &T) { int d; scanf("%d", &d); if(d!=-1) { T=(TREE)malloc(sizeof(tree)); T->d=d; T->lchild=T->rchild=NULL; T->Ltag=T->Rtag=Tlink; build_tree(T->lchild); build_tree(T->rchild); } } TREE pre; void inorThread_tree(TREE p) { if(p) { if(p->Ltag==Tlink)//当只有一个结点的时候，要加上这句话 inorThread_tree(p->lchild); if(!p->lchild) { p->lchild=pre; p->Ltag=Thread; } if(!pre->rchild) { pre->rchild=p; pre->Rtag=Thread; } pre=p; if(p->Rtag==Tlink) inorThread_tree(p->rchild); } }
/*
上述代码可以简化如下，pre的初值为NULL就好
void inorThread_tree(TREE p)
{
if(p)
{
inorThread_tree(p->lchild);
if(!p->lchild)
{
p->lchild=pre;
p->Ltag=Thread; } if(pre && !pre->rchild) { pre->rchild=p; pre->Rtag=Thread; } pre=p; inorThread_tree(p->rchild); } }
*/ void print_tree(TREE T){ if(T) { print_tree(T->lchild); printf("%d ", T->d); print_tree(T->rchild); } } void print_inorThr_tree(TREE T) { TREE p=T; while(1) { while(p->Ltag==Tlink) p=p->lchild; printf("%d ", p->d); while(p->Rtag==Thread) { p=p->rchild; printf("%d ", p->d); } p=p->rchild; if(p==T) break; } } int main() { TREE T=NULL; build_tree(T); print_tree(T);//递归中序遍历 printf("\n"); pre=T; inorThread_tree(T);//非递归中序遍历 pre->rchild=T; pre->Rtag=0;//保证只有一个结点的情况 print_inorThr_tree(T); return 0; }
//后序线索
#include<stdio.h> #include<stdlib.h> #define Thread 1 #define Tlink 0 typedef struct tree { int d; struct tree* lchild; struct tree* rchild; struct tree* rrchild; int Ltag, Rtag; }*TREE; void build_tree(TREE &T) { int d; scanf("%d", &d); if(d!=-1) { T=(TREE)malloc(sizeof(tree)); T->d=d; T->lchild=T->rchild=NULL; T->Ltag=T->Rtag=Tlink; build_tree(T->lchild); build_tree(T->rchild); } } TREE pre; void postThread_tree(TREE p) { if(p) { if(p->Ltag==Tlink) postThread_tree(p->lchild); if(p->Rtag==Tlink) postThread_tree(p->rchild); if(!p->lchild) { p->lchild=pre; p->Ltag=Thread; } if(!pre->rchild ) { pre->rchild=p; pre->Rtag=Thread; } else { pre->rrchild=p; } pre=p; } } void print_postThr_tree(TREE T) { TREE p=T; while(p->Ltag==Tlink) p=p->lchild; while(1) { printf("%d ", p->d); if(p==T) break; if(p->Rtag == Thread) p=p->rchild; else p=p->rrchild; } } void print_tree(TREE T) { if(T) { print_tree(T->lchild); print_tree(T->rchild); printf("%d ", T->d); } } int main() { TREE T=NULL; build_tree(T); print_tree(T);//递归后序遍历 printf("\n"); pre=T; postThread_tree(T);//非递归后序遍历 pre->rchild=T; pre->Rtag = Thread; print_postThr_tree(T); return 0; }
本文转自 小眼儿 博客园博客，原文链接：http://www.cnblogs.com/hujunzheng/p/3983037.html，如需转载请自行联系原作者
