二叉排序树 求树的深度 各个结点的深度.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;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;else tmp = T; T= T-left; sign =0;if(T =NULL & sign = 1) tmp -right = q;if(T =NULL & sign = 0) tmp -left = q; int TreeDepth(tree p) /统计根“的深度tree T = p; int i; tree q100; i =1; q0= T;int k ; k = 0;int rs100;int ls100; int j; int num =1; int max=1;for(j=0; jleft & lsi = 0)T =T-left; lsi = 1; /访问了当前结点的左结点，则标记Lsi=1;i+; qi = T;k+;lsi =0; rsi = 0; /每次进栈的新结点，其左子树和右子树均为访问 num+; if(max left =NULL & T-right & rsi =0 ) | (lsi =1 & T-right& rsi =0 ) ) T = T-right; rsi =1; /访问了当前结点的右结点，则标记Rsi=1; k+; i+; qi = T; lsi =0; rsi = 0; num+;if(max left =NULL & rsi = 1 ) |(T-left =NULL & T-right = NULL) |(T-right =NULL & lsi = 1 ) |( rsi =1& lsi = 1 ) )i-; k+; num-;T = qi; return max;void AllTreeDepth(tree p) /所有“结点”的深度 ，利用“每个结点“重新作为”根“，重复运用”求根的深度“函数则可tree T = p; int i; tree q100; i =1; q0= T;int k ; k = 0;int rs100;int ls100; int j; for(j=0; jdata,TreeDepth(qi); while(T-left & lsi = 0)T =T-left;lsi = 1; i+; qi = T;k+;lsi =0; rsi = 0; printf(结点值为%d的深度：%dn,qi-data,TreeDepth(qi);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的深度：%dn,qi-data,TreeDepth(qi); 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 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=4;i+)scanf(%d,&num); Inser