数据结构又一难题

苏格拉底柏拉图

编写递归算法，将二叉树中所有左右子树交换。其中树的根结点为bt。
二叉树链表类型定义：
typedef struct BiTNode{
TElemType data;
BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

我写的算法是：
void Exchange(BiTree &bt)
/* Exchange the left and right leaves of */
/* bitree whose root node is bt          */
{  BiTNode *t;
   if(!bt)
   return;//空树返回
    if(!bt->lchild&&!bt->rchild)
   return;//只有一个结点也返回
   if(!bt->lchild)
  {
  bt->lchild=
(struct BiTNode*)malloc
(sizeof(struct BiTNode));
  bt->lchild->data=bt->rchild->data;
  bt->lchild->lchild=bt->rchild->lchild;
  bt->lchild->rchild=bt->rchild->rchild;
  bt->rchild=NULL;
  return;}//左子树为空
  if(!bt->rchild)
  {
    bt->rchild=
(struct BiTNode*)malloc
(sizeof(struct BiTNode));
  bt->rchild->data=bt->lchild->data;
  bt->rchild->lchild=bt->lchild->lchild;
  bt->rchild->rchild=bt->lchild->rchild;
  bt->lchild=NULL;
  return;}//右子树为空
    t=                                      //左右子树均不空时，交换左右子树
(struct BiTNode*)malloc
(sizeof(struct BiTNode));
  t->data=bt->lchild->data;
  t->lchild=bt->lchild->lchild;
  t->rchild=bt->lchild->rchild;
  bt->lchild->data=bt->rchild->data;
  bt->lchild->lchild=bt->rchild->lchild;
  bt->lchild->rchild=bt->rchild->rchild;
  bt->rchild->data=t->data;
  bt->rchild->lchild=t->lchild;
  bt->rchild->rchild=t->rchild;
  t=NULL;
  Exchange(bt->lchild);//递归
  Exchange(bt->rchild);
  
}

用作业系统做的，居然莫名其妙出错：

    T0 = C(B,F(D,K(I,S)))
A$:  --> C(F(K(S,I),D),B)
E$:  --> C(F(K(S,I),D),B)
===== Right =====
    T1 = B(A,E(C,Q(J,X)))
A$:  --> B(E(Q(X,J),C),A)
E$:  --> B(E(Q(X,J),C),A)
===== Right =====
    T2 = I(B(#,H(F,#)),Q(M(L,N),W(V,#)))
A$:  --> I(Q(W(#,V),M(N,L)),B(H(#,F),#))
E$:  --> I(Q(W(#,V),M(N,L)),B(H(F,#),#))
----- Error -----
    T3 = A(#,X)
A$:  --> A(X,#)
E$:  --> A(X,#)
===== Right =====
    T4 =
A$:  -->
E$:  -->
===== Right =====
    T5 = U(I(B,Q(#,R)),Y(W,#))
A$:  --> U(Y(#,W),I(Q(R,#),B))
E$:  --> U(Y(#,W),I(Q(R,#),B))
===== Right =====
    T6 = L(D(C(A,#),J(E,#)),P(O,Y(V,#)))
A$:  --> L(P(Y(#,V),O),D(J(#,E),C(#,A)))
E$:  --> L(P(Y(#,V),O),D(J(#,E),C(#,A)))
===== Right =====
    T7 = P(F(A,L(K,N)),Z(X(R,#),#))
A$:  --> P(Z(#,X(#,R)),F(L(N,K),A))
E$:  --> P(Z(#,X(R,#)),F(L(N,K),A))
----- Error -----
    T8 = K(H(C(B,#),J),Z(S(R,Y),#))
A$:  --> K(Z(#,S(Y,R)),H(J,C(#,B)))
E$:  --> K(Z(#,S(R,Y)),H(J,C(#,B)))
----- Error -----
    T9 = L(D(C(A,#),K(H,#)),S(#,Z(U,#)))
A$:  --> L(S(Z(#,U),#),D(K(#,H),C(#,A)))
E$:  --> L(S(Z(U,#),#),D(K(#,H),C(#,A)))
----- Error -----
Error：4     Right：6
Compile Success!
<第6次运行>
    T0 = A(#,U(C(#,E),#))
A$:  --> A(U(#,C(E,#)),#)
E$:  --> A(U(C(#,E),#),#)
----- Error -----
    T1 = S(F(A(#,C),M(J,O)),T(#,X))
A$:  --> S(T(X,#),F(M(O,J),A(C,#)))
E$:  --> S(T(X,#),F(M(O,J),A(C,#)))
===== Right =====
    T2 =
A$:  -->
E$:  -->
===== Right =====
    T3 = W(V(N(D,Q),#),X)
A$:  --> W(X,V(#,N(Q,D)))
E$:  --> W(X,V(#,N(D,Q)))
----- Error -----
    T4 = B(#,C(#,L(H,#)))
A$:  --> B(C(L(#,H),#),#)
E$:  --> B(C(#,L(H,#)),#)
----- Error -----
    T5 = U(E(B(#,C),J(G,K)),Y(X,#))
A$:  --> U(Y(#,X),E(J(K,G),B(C,#)))
E$:  --> U(Y(#,X),E(J(K,G),B(C,#)))
===== Right =====
    T6 = H(#,Z)
A$:  --> H(Z,#)
E$:  --> H(Z,#)
===== Right =====
    T7 = O(N(J(B,L),#),T(S(R,#),U(#,Y)))
A$:  --> O(T(U(Y,#),S(#,R)),N(#,J(L,B)))
E$:  --> O(T(U(Y,#),S(#,R)),N(#,J(B,L)))
----- Error -----
    T8 = H(D,X(U(P,W),Z))
A$:  --> H(X(Z,U(W,P)),D)
E$:  --> H(X(Z,U(W,P)),D)
===== Right =====
    T9 = B(#,C(#,Q(P,U)))
A$:  --> B(C(Q(U,P),#),#)
E$:  --> B(C(#,Q(P,U)),#)
----- Error -----
Error：5     Right：5

究竟错在哪里？

[ 本帖最后由 苏格拉底柏拉图 于 2007-6-2 23:45 编辑 ]

iptton

LZ怎么写得这么复杂……



不用申请新空间，改下指针指向就行的了……

[ 本帖最后由 iptton 于 2007-6-2 23:36 编辑 ]

iptton

1. void Exchange(BiTree &bt)
   
2. /* Exchange the left and right leaves of */
   
3. /* bitree whose root node is bt          */
   
4. {
   
5. /* 空树返回 */
   
6.     if(!bt ||
   
7.        (!bt->lchild && !bt->rchild)
   
8.        )
   
9.        return ;
   
10. 
    
11. /*左右相换*/
    
12.     bt->lchild　　<=>  bt->rchild;
    
13. /*和swap(int *a,int *b)类似，具体怎么写，楼主应该也可以解决吧*/
    
14. 
    
15.     Exchange(bt->lchild);
    
16.     Exchange(bt->rchild);
    
17. }

复制代码

[ 本帖最后由 iptton 于 2007-6-3 00:53 编辑 ]

苏格拉底柏拉图

t->data=bt->lchild->data;
  t->lchild=bt->lchild->lchild;
  t->rchild=bt->lchild->rchild;
  bt->lchild->data=bt->rchild->data;
  bt->lchild->lchild=bt->rchild->lchild;
  bt->lchild->rchild=bt->rchild->rchild;
  bt->rchild->data=t->data;
  bt->rchild->lchild=t->lchild;
  bt->rchild->rchild=t->rchild;
  t=NULL;

这段是左右子树交换啊！

iptton

直接给代码你好了……

1. 
   
2.     BiTree tmp;
   
3.     if(!bt ||
   
4.        (!bt->lchild && !bt->rchild)
   
5.        )
   
6.        return ;
   
7.     tmp=bt->lchild;
   
8.     bt->lchild=bt->rchild;
   
9.     bt->rchild=tmp;
   
10.     Exchange(bt->lchild);
    
11.     Exchange(bt->rchild);
    

复制代码

九月鹰飞

LS强！
怎么我想得就那么复杂呀

onttpi

＃1的算法有错，而且还有内存泄露……有 malloc　却没有 free