二叉树结点类型定义如下： typedef struct node { char data; /* 数据元素 */ struct node *lchild; /* 指向左孩子结点 */ struct node *rchild; /* 指向右孩子结点 */ } BTNode; 递归算法bool isSameTree(BTNode *p, BTNode *q)用于判断p，q两棵树是否相同，请填上以下代码中的空缺部分。 bool isSameTree(BTNode *p, BTNode *q) { if (p==NULL && q==NULL) return true; /*两棵树均为空*/ else if ( ① ) return false; /*一棵树为空*/ else if (p->data != q->data) ② ; else return ③ ; }

&& q==NULL) { // 如果p和q都为空，说明两棵树相同
return true;
}
else if (p==NULL || q==NULL) { // 如果p和q有一个为空，说明两棵树不同
return false;
}
else if (p->data != q->data) { // 如果p和q的值不同，说明两棵树不同
return false;
}
else { // 递归比较p和q的左右子树
return isSameTree(p->lchild, q->lchild) && isSameTree(p->rchild, q->rchild);
}
}

相关问题

设计统计二叉树中度为1的结点个数的算法。 二叉树结点类型定义如下： typedef struct node { char data; /* 数据元素 */ struct node *lchild; /* 指向左孩子结点 */ struct node *rchild; /* 指向右孩子结点 */ } BTNode; 设计一个算法，计算一棵给定二叉树中度为1的结点个数。参数b为指向二叉树根结点的指针，返回值为度数为1的结点个数值。 函数原型为：int SingleNodes(BTNode *b);

算法思路如下：

1. 若当前结点为空，返回0。
2. 若当前结点的左、右孩子都为空，返回0。
3. 若当前结点的左孩子不为空，右孩子为空，返回1+SingleNodes(左孩子)。
4. 若当前结点的右孩子不为空，左孩子为空，返回1+SingleNodes(右孩子)。
5. 若当前结点的左、右孩子都不为空，返回SingleNodes(左孩子)+SingleNodes(右孩子)。

实现代码如下：

int SingleNodes(BTNode *b) {
    if (!b) { // 当前结点为空，返回0
        return 0;
    }
    if (!b->lchild && !b->rchild) { // 当前结点的左、右孩子都为空，返回0
        return 0;
    }
    if (b->lchild && !b->rchild) { // 当前结点的左孩子不为空，右孩子为空，返回1+SingleNodes(左孩子)
        return 1 + SingleNodes(b->lchild);
    }
    if (!b->lchild && b->rchild) { // 当前结点的右孩子不为空，左孩子为空，返回1+SingleNodes(右孩子)
        return 1 + SingleNodes(b->rchild);
    }
    // 当前结点的左、右孩子都不为空，返回SingleNodes(左孩子)+SingleNodes(右孩子)
    return SingleNodes(b->lchild) + SingleNodes(b->rchild);
}

依据二叉树链表结点结构: typedef struct Node { // 结点结构 TElemType data; struct Node *lchild, *rchild; // 左右孩指针 } BTNode; 设计能中序输出二叉树T中各个结点数据的递归算法函数MOrder（T）。

递归算法函数MOrder(T)的实现如下：

void MOrder(BTNode *T) {
    if (T == NULL) {
        return;
    }
    MOrder(T->lchild); // 遍历左子树
    printf("%d ", T->data); // 输出结点数据
    MOrder(T->rchild); // 遍历右子树
}

该算法函数的思路是，先遍历左子树，再输出当前结点的数据，最后遍历右子树。这样就能够按照中序遍历的顺序输出二叉树T中各个结点的数据。在实现过程中，需要注意判断结点是否为空，如果为空则直接返回。