二叉排序树 先序遍历 中序遍历 后序遍历(非递归).doc

#include #include typedef struct Tree int data; struct Tree *left; struct Tree *right;*tree;void InsertTree(tree p,int num) tree T; T = p; int i; int sign; /sign标记“现在要插入的”结点是父结点的“左还是右结点”i=0; tree q,tmp;q =(tree ) malloc( sizeof(struct Tree) );q-data = num; q-left =NULL; q-right =NULL; while(T)if(num T-data ) tmp = T; T= T-right;sign =1; /是父结点的右结点，则标记为1else tmp = T; T= T-left; sign =0;if(T =NULL & sign = 1) tmp -right = q;if(T =NULL & sign = 0) tmp -left = q; void PreOrder(tree p)if(p)printf(%d,p-data);PreOrder(p-left);PreOrder(p-right);void InOrder(tree p)if(p)InOrder(p-left);printf(%d,p-data);InOrder(p-right);void PostOrder(tree p)if(p)PostOrder(p-left);PostOrder(p-right);printf(%d,p-data);/先序遍历，中序遍历，后序遍历思想基本一致：/(1)最左结点（且是尚未访问）依次进栈，/(2)右结点（左结点为空或左结点已访问且是尚未访问）依次进栈/(3)叶子结点(或已访问的（左或右）+ 空子树) 出栈/先序遍历，中序遍历，后序遍历输出原则：/(1) 先序遍历进栈的均输出/(2) 中序遍历“无左子树”输出/(3) 后序遍历void PreOrder1(tree p)tree T = p; int i; tree q100; i =1; q0= T;int k ; k = 0;int rs100;int ls100; /rs,ls数组存放的是“当前结点”的左、右结点是否访问. int j; for(j=0; jdata); while(T-left & lsi = 0)T =T-left;lsi = 1; i+; qi = T;k+;lsi =0; rsi = 0;printf(%d,qi-data);if( T-left =NULL & T-right & rsi =0 ) | (lsi =1 & T-right& rsi =0 ) ) T = T-right; rsi =1; k+;i+;qi = T;lsi =0; rsi = 0; printf(%d,qi-data); if( (T-left =NULL & rsi = 1 ) |(T-left =NULL & T-right = NULL) |(T-right =NULL & lsi = 1 ) |( rsi =1& lsi = 1 ) )i-; k+;T = qi; void InOrder1(tree p)tree T = p; int i; tree q100; i =1; q0= T; qi = T; int k ; k = 0;int rs100;int ls100; int j; for(j=0; jleft & lsi = 0)T =T-left;lsi = 1; i+; qi = T;k+;lsi =0; rsi = 0;if( T-left =NULL & T-right & rsi =0 ) | (lsi =1 & T-right& rsi =0 ) )printf(%d,qi-data); /“无”左结点就输出。 T = T-right; rsi =1; k+;i+;qi = T;lsi =0; rsi = 0; if( (T-left =NULL & rsi = 1 ) |(T-left =NULL & T-right = NULL) |(T-right =NULL & lsi = 1 ) |( rsi =1& lsi = 1 ) ) if(lsi = 0 & rsi = 0) | ( lsi = 1 & qi-right = NULL) )/尚未访问的，或左结点已访问的输出 printf(%d,qi-data); i-; k+;T = qi; void PostOrder1(tree p)tree T = p; int i; tree q100; i =1; q0= T; qi = T; int k ; k = 0;int rs100;int ls100; int j; for(j=0; jleft & lsi = 0)T =T-left;lsi = 1; i+; qi = T;k+;lsi =0; rsi = 0;if( T-left =NULL & T-right & rsi =0 ) | (lsi =1 & T-right& rsi =0 ) ) T = T-right; rsi =1; k+;i+;qi = T;lsi =0; rsi = 0; if( (T-left =NULL & rsi = 1 ) |(T-left =NULL & T-right = NULL) |(T-right =NULL & lsi = 1 ) |( rsi =1& lsi = 1 ) ) printf(%d,qi-data); /为空的时候输出i-; k+;T = qi; void main()tree p =NULL; int num; scanf(%d,&num); p =(tree) malloc( sizeof(struct Tree) );p-data = num; p-left =NULL; p-right =NULL;int i;for(i=1; i=9;i+)scanf(%d,&num); InsertTree(p,num)