采用二叉链表的存储结构，用非递归算法（pop(s,t),pu

[问答题]

采用二叉链表的存储结构，用非递归算法（pop(s,t),push(s,t)）交换二叉树的左右子树，要求：

（1）给出算法的基本设计思想。

（2）根据设计思想，设计一个算法。

（3）说明你所设计算法的时间复杂度。

追影逐梦

遍历每个结点，交换每个结点的左右子树

void swap(BiTree bt)
{
    push(s,bt);
    while(!IsEmpty(s))
    {
        pop(s,t);//出栈
        // 交换左右子树
        BiTree temp = t->lchild;
        t->lchild = t->rchild;
        t->rchild = temp;
        if(t->lchild)// 左子不空
            push(s,t->lchild);
        if(t->rchild)// 右子不空
            push(s,t->rchild);
    }
}

发表于 2020-12-03 16:44:35 回复(0)