以二叉链表作为二叉树的存储结构,使用c++编写判别两棵树是否相等的算法。
时间: 2024-05-01 18:19:03 浏览: 140
二叉树的二叉链表存储结构定义如下:
```c
typedef struct BiTNode {
int data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
```
其中,`data`表示节点的数据,`lchild`和`rchild`分别指向节点的左子树和右子树。
判断两棵二叉树是否相等的算法如下:
```c
int isSameTree(BiTree p, BiTree q) {
if (p == NULL && q == NULL) { // 两棵树均为空,相等
return 1;
} else if (p == NULL || q == NULL) { // 一棵树为空,不相等
return 0;
} else if (p->data != q->data) { // 数据不相等,不相等
return 0;
} else { // 递归判断左子树和右子树
return isSameTree(p->lchild, q->lchild) && isSameTree(p->rchild, q->rchild);
}
}
```
首先判断两棵树是否均为空,若均为空,则两棵树相等;若一棵树为空,则两棵树不相等。若两棵树均不为空,但数据不相等,则两棵树不相等。若两棵树数据相等,则递归判断左子树和右子树是否相等。
完整代码如下:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct BiTNode {
int data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
BiTree createTree()
{
int data;
scanf("%d", &data);
if (data == -1) {
return NULL;
} else {
BiTree root = (BiTree)malloc(sizeof(BiTNode));
root->data = data;
root->lchild = createTree();
root->rchild = createTree();
return root;
}
}
int isSameTree(BiTree p, BiTree q) {
if (p == NULL && q == NULL) {
return 1;
} else if (p == NULL || q == NULL) {
return 0;
} else if (p->data != q->data) {
return 0;
} else {
return isSameTree(p->lchild, q->lchild) && isSameTree(p->rchild, q->rchild);
}
}
int main()
{
BiTree p = createTree();
BiTree q = createTree();
if (isSameTree(p, q)) {
printf("Two trees are same.\n");
} else {
printf("Two trees are not same.\n");
}
return 0;
}
```
阅读全文