C语言数据结构二叉树找出两个结点的最近的共同祖先节点非递归算法

小咪咪 2022-05-09 12:08 155阅读 0赞

1.  分别找出连个结点的所有祖先节点，利用循环队列存储
2.  比较，两个结点的祖先结点
3.  利用队列的先进先出的特点，一次由远及近比较，
4.  利用循环队列，在内循环中，将比较过的结点重新存入队列
5.  在重新，存入时，设置标志位，便于判断内循环的结束

[循环队列可以参考这篇文章][Link 1]

## 代码如下： ##

// 找结点的所有父节点
    bool FindParent(BiTree *biTree, QueueTree *parent, char c) {
        if (!biTree) return false;
        if (biTree->data == c) return true;
        if (FindParent(biTree->leftChild, parent, c)) {
            ENQueueTree(parent, biTree);
            return true;
        }
        if (FindParent(biTree->rightChild, parent, c)) {
            ENQueueTree(parent, biTree);
            return true;
        }
        return false;
    }
    
    // 找两个节点的最近父节点
    BiTree *TreeChildrenParent(BiTree *root, char e1, char e2) {
        if (!root) return NULL;
        QueueTree Q1, Q2;
        BiTree *middle1;
        BiTree *middle2;
        BiTree middle_null;
        middle_null.leftChild = NULL;
        middle_null.rightChild = NULL;
        middle_null.data = ' ';
        Q1 = InitQueueTree(20);
        Q2 = InitQueueTree(20);
        if (!FindParent(root, &Q1, e1)) return NULL;
        if (!FindParent(root, &Q2, e2)) return NULL;
        middle1 = middle2 = root;
        // 还可以在此，将祖先节点较少队列作为内层循环，减少循环次数
        // 会增加代码量
        while (Q1.tag != 0) {
            DEQueueTree(&Q1, &middle1);
            // 循环队列，添加标志结点，以便于识别是否比较完成一个循环
            ENQueueTree(&Q2, &middle_null);
            while (Q2.tag != 0) {
                DEQueueTree(&Q2, &middle2);
                if (middle2->data == ' ') break;
                if (middle1 == middle2) return middle1;
                ENQueueTree(&Q2, middle2);
            }
        }
    }

[Link 1]: https://blog.csdn.net/wei_bo_cai/article/details/82953114