论坛 › 【编程】编程圣殿 › 数据结构又一难题

苏格拉底柏拉图 发表于 2007-6-2 23:19

数据结构又一难题

编写递归算法，将二叉树中所有左右子树交换。其中树的根结点为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 发表于 2007-6-2 23:31

LZ怎么写得这么复杂……



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

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

iptton 发表于 2007-6-2 23:39

void Exchange(BiTree &bt)
/* Exchange the left and right leaves of */
/* bitree whose root node is bt          */
{
/* 空树返回 */
    if(!bt ||
       (!bt->lchild && !bt->rchild)
       )
       return ;

/*左右相换*/
    bt->lchild　　<=>bt->rchild;
/*和swap(int *a,int *b)类似，具体怎么写，楼主应该也可以解决吧*/

    Exchange(bt->lchild);
    Exchange(bt->rchild);
}

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

苏格拉底柏拉图 发表于 2007-6-2 23:42

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 发表于 2007-6-2 23:48

直接给代码你好了……


    BiTree tmp;
    if(!bt ||
       (!bt->lchild && !bt->rchild)
       )
       return ;
    tmp=bt->lchild;
    bt->lchild=bt->rchild;
    bt->rchild=tmp;
    Exchange(bt->lchild);
    Exchange(bt->rchild);

九月鹰飞 发表于 2007-6-3 00:54

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

onttpi 发表于 2007-6-3 02:54

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

查看完整版本: 数据结构又一难题