二叉树中所有节点左右字数节点的交换及遍历.doc

《二叉树中所有节点左右字数节点的交换及遍历.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、二叉树中所有节点的左右子树相互交换 递归与非递归程序(2006-10-1111:24:09)转载分类：数据结构//将二叉树中所有节点的左右子树相互交换BiNode*Exchange(BiNode*T){ BiNode*p; if(NULL==T

2、

3、(NULL==T->lchild&&NULL==T->rchild))  returnT; p=T->lchild; T->lchild=T->rchild; T->rchild=p; if(T->lchild) {  T->lchild=Exchange(T->lchi

4、ld); } if(T->rchild) {  T->rchild=Exchange(T->rchild); } returnT;}//将二叉树中所有节点的左右子树相互交换//不使用递归voidNonRecursive_Exchange(BiNode*T){ Stacks; BiNode*p; if(NULL==T)  return; InitStack(&s); Push(&s,T); while(!isEmpty(&s)) {  T=Pop(&s);  p=T->lchild;  T->lchild=T->rc

5、hild;  T->rchild=p;   if(T->rchild)   Push(&s,T->rchild);  if(T->lchild)   Push(&s,T->lchild);  }  DestroyStack(&s); }//递推形式的前续遍历，不使用递归和堆栈，//但每个节点增加了一个parent指针和Mark标记voidIteration_Mark_PreOrderTraverse(BiPMNode*T){  if(NULL==T)  return;  while(NULL!=T) {  if(0

6、==T->mark)  {   T->mark++;   printf("%d",T->data);   while(NULL!=T->lchild)   {         T=T->lchild;    T->mark++;    printf("%d",T->data);   }    T->mark++;   if(NULL!=T->rchild)    T=T->rchild;   continue;  }  if(1==T->mark)  {   T->mark++;   if(NULL!=T->rch

7、ild)    T=T->rchild;      continue;  }  if(2==T->mark)  {      T=T->parent;     }  }}//递推形式的中续遍历，不使用递归和堆栈，//但每个节点增加了一个parent指针和Mark标记voidIteration_Mark_InOrderTraverse(BiPMNode*T){  if(NULL==T)  return;  while(NULL!=T) {  if(0==T->mark)  {   T->mark++;      wh

8、ile(NULL!=T->lchild)   {         T=T->lchild;    T->mark++;       }    printf("%d",T->data);   T->mark++;   if(NULL!=T->rchild)    T=T->rchild;   continue;  }  if(1==T->mark)  {   printf("%d",T->data);   T->mark++;   if(NULL!=T->rchild)    T=T->rchild;      co

9、ntinue;  }  if(2==T->mark)  {      T=T->parent;     }  }} //递推形式的后续遍历，不使用递归和堆栈，//但每个节点增加了一个parent指针和Mark标记voidIteration_Mark_PostOrderTraverse(BiPMNode*T){  if(NULL==T)  return;  while(NULL!=T) {  if(0==T->mark)  {   T->mark++;   while(NULL!=T->lchild)   {    

10、     T=T->lchild;    T->mark++;   }    T->mark++;   if(NULL!=T->rchild)    T=T->rchild;   continue;  }  if(1==T->mark)  {   T->mark++;   if(NULL!=T->rchild)    T=T->rchild;      co