数据结构树的复制--非递归算法

红太狼 2022-05-09 10:50 279阅读 0赞

*  借助队列来实现，树结构的复制

typedef struct BiTree {
        char data;
        struct BiTree *leftChild;
        struct BiTree *rightChild;
    } BiTree;
    
    
    typedef struct QueueTree {
        // 为了节省空间，使用的是循环队列
        BiTree **base;    // 用于存放树结点的指针
        int front;
        int rear;
        int tag;      // 队列是否为空
        int length;
    } QueueTree;
    
    
    QueueTree InitQueueTree(int length);
    
    bool ENQueueTree(QueueTree *queue, BiTree *e);
    
    bool DEQueueTree(QueueTree *queue, BiTree **result);
    
    BiTree *CopyBinaryTree(BiTree *root);

*  详细代码

bool ENQueueTree(QueueTree *queue, BiTree *e) {
        if (queue->tag == queue->length) return false;
        queue->base[queue->rear] = e;
        if (queue->rear == queue->length - 1) {
            queue->rear = 0;
            queue->tag++;
            return true;
        }
        queue->rear++;
        queue->tag++;
        return true;
    }
    
    bool DEQueueTree(QueueTree *queue, BiTree **result) {
        if (queue->tag == 0) return false;
        *result = queue->base[queue->front];
        if (queue->front == queue->length - 1) {
            queue->front = 0;
            queue->tag--;
            return true;
        }
        queue->front++;
        queue->tag--;
        return true;
    }
    
    IStack InStackHTree(int stack_size) {
        IStack CS;
        CS.stack_size = stack_size;
        if (!(CS.base = (int *) malloc(stack_size * sizeof(int)))) exit(OVERFLOW);
        CS.top = CS.base;
        return CS;
    }
    
    BiTree *StackCopyBinaryTree(BiTree *root) {
        // 注意复制时，操作的都是树节点的指针，
        // 在队列中存储的都是树节点的指针
        QueueTree Q1, Q2;
        BiTree *middle, *root_copy, *middle_copy;
        if (!root) {
            return NULL;
        }
        Q1 = InitQueueTree(20);
        Q2 = InitQueueTree(20);
        if (!(middle_copy = root_copy = (BiTree *) malloc(sizeof(BiTree)))) exit(OVERFLOW);
        middle = root;
        ENQueueTree(&Q1, root);
        ENQueueTree(&Q2, root_copy);
        while (Q1.tag != 0) {
            DEQueueTree(&Q1, &middle);
            DEQueueTree(&Q2, &middle_copy);
            middle_copy->data = middle->data;
            if (middle->leftChild) {
                if (!(middle_copy->leftChild = (BiTree *) malloc(sizeof(BiTree)))) exit(OVERFLOW);
                ENQueueTree(&Q1, middle->leftChild);
                ENQueueTree(&Q2, middle_copy->leftChild);
            }
            if (middle->rightChild) {
                if (!(middle_copy->rightChild = (BiTree *) malloc(sizeof(BiTree)))) exit(OVERFLOW);
                ENQueueTree(&Q1, middle->rightChild);
                ENQueueTree(&Q2, middle_copy->rightChild);
            }
        }
        return root_copy;
    }