《1》 编写函数bool isEqualTree(BiTNode *T1,BiTNode *T2) ， 判别两颗二叉树是否相等

好的，我可以帮你编写判断两颗二叉树是否相等的函数。以下是C++代码实现：

bool isEqualTree(BiTNode *T1, BiTNode *T2) {
    if (T1 == nullptr && T2 == nullptr) { // 两颗树均为空，返回true
        return true;
    }
    if (T1 == nullptr || T2 == nullptr) { // 有一颗树为空，返回false
        return false;
    }
    if (T1->data != T2->data) { // 根节点数据不相等，返回false
        return false;
    }
    bool leftEqual = isEqualTree(T1->lchild, T2->lchild); // 递归判断左子树是否相等
    bool rightEqual = isEqualTree(T1->rchild, T2->rchild); // 递归判断右子树是否相等
    return leftEqual && rightEqual; // 左右子树均相等，返回true，否则返回false
}

该函数的思路是：若两颗树均为空，返回true；若有一颗树为空，返回false；若根节点数据不相等，返回false；否则递归判断左右子树是否相等。最终判断左右子树是否均相等，返回结果。

你可以将函数加入到你的代码中，并传入两颗二叉树的根节点进行测试。

相关问题

编写函数bool isCompleteTree(BiTNode *T)，判断T是否为完全二叉树

完全二叉树的定义是：对于一棵具有n个结点的二叉树，如果其结点按层序编号(从1开始)，对任一结点i(1<=i<=n)：

1. 如果i=1，则结点i是二叉树的根结点，无双亲；如果i>1，则其双亲是结点i/2（下取整）。

2. 如果2i>n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点2i。

3. 如果2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+1。

因此，判断一棵二叉树是否为完全二叉树，可以按照以下步骤进行：

1. 从根节点开始，按照层序遍历二叉树，将每个节点依次编号为1,2,3,...n。

2. 如果当前节点的编号为i，且其左孩子编号为j，右孩子编号为k，则有以下几种情况：

（1）如果j>n，说明当前节点已经是叶子节点，后面的节点都应该是叶子节点，否则不是完全二叉树。

（2）如果k>n，说明当前节点只有左孩子，后面的节点都应该没有孩子，否则不是完全二叉树。

（3）如果j<=n且k<=n，继续遍历。

3. 如果遍历完所有节点，都没有发现不符合上述规则的情况，则该二叉树是完全二叉树。

下面是判断完全二叉树的代码实现：

#include <queue>
#include <cmath>

using namespace std;

struct BiTNode {
    int val;
    BiTNode *left;
    BiTNode *right;
    BiTNode(int x) : val(x), left(NULL), right(NULL) {}
};

bool isCompleteTree(BiTNode *T) {
    if (T == NULL) return true; // 空树是完全二叉树

    queue<BiTNode*> q;
    q.push(T);
    int i = 1, n = 1; // i为当前节点编号，n为当前层总节点数

    while (!q.empty()) {
        int cnt = q.size(); // 当前层节点数
        if (cnt != n) return false; // 不满足完全二叉树的条件

        for (int j = 0; j < cnt; j++) {
            BiTNode* node = q.front();
            q.pop();
            if (i != node->val) return false; // 不满足完全二叉树的条件

            if (node->left != NULL) {
                q.push(node->left);
                if (2 * i > pow(2, floor(log2(n)) + 1)) return false; // 不满足完全二叉树的条件
            }

            if (node->right != NULL) {
                q.push(node->right);
                if (2 * i + 1 > pow(2, floor(log2(n)) + 1)) return false; // 不满足完全二叉树的条件
            }

            i++;
        }

        n *= 2;
    }

    return true;
}

其中，floor(log2(n))表示n的二进制位数减1，即层数。pow(2, floor(log2(n)) + 1)表示当前层的最大节点编号。

用c语言 编写函数bool isCompleteTree(BiTNode *T)，判断T是否为完全二叉树

以下是用C语言编写的判断二叉树是否为完全二叉树的函数：

#include <stdbool.h>

typedef struct BiTNode {
    int data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

// 获取二叉树的深度
int getDepth(BiTree T) {
    if (T == NULL) {
        return 0;
    } else {
        int leftDepth = getDepth(T->lchild);
        int rightDepth = getDepth(T->rchild);
        return 1 + (leftDepth > rightDepth ? leftDepth : rightDepth);
    }
}

bool isCompleteTree(BiTree T) {
    if (T == NULL) { // 空树也是完全二叉树
        return true;
    }

    int depth = getDepth(T);
    int level = 1;

    while (T) {
        if (T->lchild == NULL && T->rchild != NULL) { // 左子树为空，右子树不为空，不是完全二叉树
            return false;
        }

        if (level < depth - 1) { // 不到最后一层时，必须左右子树都存在
            if (T->lchild == NULL || T->rchild == NULL) {
                return false;
            }
        } else if (level == depth - 1) { // 如果是最后一层，那么只要左子树存在，右子树可以为空
            if (T->lchild == NULL) {
                return false;
            }
            if (T->rchild != NULL) {
                return false;
            }
        } else { // 如果level > depth - 1，那么不可能存在非空节点
            if (T->lchild != NULL || T->rchild != NULL) {
                return false;
            }
        }

        level++;

        if (T->lchild != NULL) {
            T = T->lchild;
        } else {
            T = T->rchild;
        }
    }

    return true;
}

该函数的基本思路是：先获取二叉树的深度，然后从根节点开始逐层判断，如果左子树为空，右子树不为空，则不是完全二叉树；如果不到最后一层，那么左右子树都必须存在；如果是最后一层，那么只要左子树存在，右子树可以为空；如果超过了最后一层，那么不可能存在非空节点。