将二叉树的两个孩子换位置,即左变右,右变左(用递归和非递归两种方法).doc

将二叉树的两个孩子换位置，即左变右，右变左。(用递归和非递归两种方法)变相的二叉树遍历题目，可以采用先序遍历，层次遍历等typedef struct node int key; struct node *llink,*rlink;NODE;void exchange(NODE *root) NODE *r,*p,stackMAX;int top=0;stack+top=root;while(top0)p=stacktop-;if(p!=NULL) r=p-llink; p-llink=p-rlink; p-rlink=r;stack+top=p-llink;stack+top=p-rlink;迭代版的如下，使用了队列 void change( BTree * pTree ) if( NULL = pTree ) return; queue qu; qu.push(pTree); BTree*pTree2 = null; while(!qu.empty() pTree2= qu.front( ); qu.pop(); BTree * pTemp = pTree2- left; pTree2- left = pTree2- right; pTree2- right= pTemp; if(pTree2- left!=null) qu.push(pTree2- left); if(pTree2- right!=null) qu.push(pTree2- right); 节点定义：typedef struct node char data; struct node *lchild; struct node *rchile;NODE;二叉树的两个孩子换位置(递归版本)：void exchange(BiTree BT) BiTree p; if(BT=NULL) p=BT- lchild; BT- lchild=BT- rchild; BT- rchild=p; exchange(BT- lchild); exchange(BT- rchild); 二叉树的两个孩子换位置(非递归版本):/ 在二叉链表下的交换操作void exchange(BiTree BT) BiTree r,p; BiTree stack100; int tp=0; stack0=BT; while(tp 0) p=stacktp; tp=tp-1; if(p!=NULL) r=p- lchild; p- lchild=p- rchild; BT- rchild=r; stacktp+1=p- lchild; tp=tp+1; stacktp+1=p- rchild; tp=tp+1; void exchange(BiTree BT) BiTree r,p; BiTree stack100; int tp=0; stack0=BT; while(tp 0) /前面tp已经为0了怎么还可能大于0那？ p=stacktp; tp=tp-1; if(p!=NULL) r=p- lchild; p- lchild=p- rchild; BT- rchild=r; stacktp+1=p- lch