5.17在以双亲链表表示法存储结构的树中，写出以下算法： （1）求树中结点双亲的算法； （2）求树中结点孩子的算法。5.14编一算法判别给定的二叉树是否是完全二叉树。

算法1：求树中结点双亲

1. 输入参数：当前节点p，根节点root
2. 如果p为根节点root，则p没有双亲，返回空
3. 从root开始进行深度优先遍历，直到找到p的父节点parent
4. 返回parent作为p的双亲节点

算法2：求树中结点孩子

1. 输入参数：当前节点p
2. 如果p没有孩子节点，返回空
3. 如果p有左孩子节点，返回左孩子节点
4. 如果p没有左孩子节点，但有右孩子节点，返回右孩子节点

算法3：判断二叉树是否为完全二叉树

1. 输入参数：二叉树的根节点root
2. 开始进行层次遍历，将每个节点依次加入队列中
3. 对于队列中的每个节点p，如果p有左孩子节点但没有右孩子节点，则不是完全二叉树；如果p有右孩子节点但没有左孩子节点，则不是完全二叉树；如果p没有左孩子节点和右孩子节点，则它后面的所有节点都必须没有孩子节点，否则不是完全二叉树
4. 如果遍历完所有节点都没有发现不符合条件的节点，则是完全二叉树

相关问题

请写出树的带双亲的孩子链表法存储结构，基于此结构，设计算法：计算树的度。

### 回答1：
树的带双亲的孩子链表法存储结构如下：

typedef struct CTNode {
    TElemType data; // 结点数据
    struct CTNode *parent; // 指向双亲结点
    struct CTNode *firstchild; // 指向第一个孩子结点
    struct CTNode *rightsib; // 指向右兄弟结点
} CTNode, *CTree;

基于此结构，计算树的度的算法如下：

int TreeDegree(CTree T) {
    int degree = 0;
    CTree p = T;
    while (p) {
        int count = 0;
        CTree q = p->firstchild;
        while (q) {
            count++;
            q = q->rightsib;
        }
        if (count > degree) {
            degree = count;
        }
        p = p->rightsib;
    }
    return degree;
}

算法思路：

从根结点开始，依次遍历每个结点，对于每个结点，遍历它的所有孩子结点，统计孩子结点的个数，如果孩子结点的个数大于当前的度，则更新度的值。最后返回度的值即可。

### 回答2：
带双亲的孩子链表法是一种树的存储结构，它包含两个指针，一个指向它的父节点，另一个指向它的第一个孩子节点，如果没有孩子节点，则指向空。每个节点还有一个指向它的下一个兄弟节点的指针。

以下是带双亲的孩子链表法的示意图：

               A
              / \
             B   C
            / \   \
           D   E   F
              / \  
             G   H  

节点 A 的双亲指针为空，它的孩子指针分别指向 B 和 C。节点 B 的双亲指针指向 A，孩子指针分别指向 D 和 E。节点 C 的双亲指针指向 A，孩子指针指向 F。节点 D 和 E 没有孩子节点，它们的孩子指针均为空。节点 F 的双亲指针指向 C，孩子指针分别指向 G 和 H。节点 G 和 H 没有下一个兄弟节点，它们的下一个兄弟指针均为空。

现在我们需要设计一个算法来计算树的度。树的度指的是树中节点的最大度数。在上面的示意图中，节点 A 的度数为 2，节点 B、C 和 F 的度数为 2，节点 D 和 E 的度数为 0，节点 G 和 H 的度数为 0。因此，这棵树的度数为 2。

下面是计算树的度的算法：

1. 从根节点开始，初始化树的度为 0。

2. 遍历每个节点，如果它有孩子节点，则将它的度数加 1。

3. 如果它的度数大于当前树的度数，则更新树的度为它的度数。

4. 遍历它的每个孩子节点，递归地执行步骤 2 和步骤 3。

5. 返回树的度数。

通过以上算法，我们可以轻松地计算出任何一棵树的度数。该算法的时间复杂度为 O(n)，其中 n 是树中节点的数量。

### 回答3：
1. 树的带双亲的孩子链表法存储结构

在树的带双亲的孩子链表法中，每个节点包含三个指针，分别指向其父节点、第一个孩子节点和下一个兄弟节点。使用该结构，可以方便地访问节点的父亲、孩子和兄弟节点，更加灵活地处理树的各种操作。

定义如下：

struct TreeNode {
    int val;               // 节点的值
    TreeNode* parent;      // 父亲节点指针
    TreeNode* firstChild;  // 第一个孩子节点指针
    TreeNode* nextSibling; // 下一个兄弟节点指针
};

2. 计算树的度

树的度是指树中节点的子树个数的最大值。因此，计算树的度，需要计算所有节点的子树个数，并找到最大值。

具体算法如下：

定义一个变量 maxDegree，记录树的最大度数。同时遍历树中的每一个节点，对于每个节点，遍历其所有子孙节点，记录子孙节点的个数，每记录一次，maxDegree 加一。最后，返回 maxDegree。

代码实现如下：

int computeDegree(TreeNode* root) {
    // 初始化树的最大度数为 0
    int maxDegree = 0;

    // 遍历树中每一个节点
    for (TreeNode* node = root; node != nullptr; node = node->nextSibling) {
        // 初始化节点的子孙节点个数为 1，即该节点本身
        int num = 1;

        // 遍历该节点的所有子孙节点
        for (TreeNode* child = node->firstChild; child != nullptr; child = child->nextSibling) {
            num += computeSubtreeSize(child);
        }

        // 记录节点的子孙节点个数，更新树的最大度数
        maxDegree = max(maxDegree, num);
    }

    return maxDegree;
}

int computeSubtreeSize(TreeNode* node) {
    // 递归计算节点的子孙节点个数
    int num = 1;
    for (TreeNode* child = node->firstChild; child != nullptr; child = child->nextSibling) {
        num += computeSubtreeSize(child);
    }
    return num;
}

时间复杂度为 O(n^2)，其中 n 是树中节点的个数。在最坏情况下，树为单链，每个节点的子孙节点数都要计算一遍。因此，算法效率较低，需要改进。可以在遍历树的过程中，同时计算每个节点的子孙节点个数，避免重复计算。

1）设计树的孩子链表法存储结构；2）基于该结构设计算法：求下标为i的结点的双亲。

1）树的孩子链表法存储结构是指，将每个结点的孩子结点用一个单链表链接起来，同时在每个结点中记录该结点的第一个孩子结点的指针和该结点的双亲结点的指针。

2）求下标为i的结点的双亲的算法如下：

（1）如果i为根结点，则返回空指针；

（2）从根结点开始遍历树，直到找到下标为i的结点；

（3）返回该结点的双亲结点的指针。