设计一个递归算法检查以二叉链表存储的两棵二叉树是否完全相同(C语言)
时间: 2024-05-16 14:14:39 浏览: 23
以下是递归算法实现:
```c
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
bool isSameTree(struct TreeNode* p, struct TreeNode* q){
if (p == NULL && q == NULL) {
return true;
}
if (p == NULL || q == NULL) {
return false;
}
if (p->val != q->val) {
return false;
}
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
```
该算法接收两个二叉树的根节点 `p` 和 `q`,如果 `p` 和 `q` 都为 `NULL`,则这两棵二叉树相同,返回 `true`。如果其中一个为 `NULL`,则这两棵二叉树不同,返回 `false`。如果两棵二叉树的根节点值不相等,则这两棵二叉树不同,返回 `false`。最后使用递归调用判断 `p` 和 `q` 的左子树和右子树是否相同,如果都相同则这两棵二叉树也相同,返回 `true`。
相关问题
用C语言求二叉树高度 用二叉链表创建一棵二叉树并利用递归算法求它的高度。
C语言代码如下:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
int tree_height(TreeNode* root) {
if (!root) {
return 0;
}
int left_height = tree_height(root->left);
int right_height = tree_height(root->right);
return (left_height > right_height ? left_height : right_height) + 1;
}
int main() {
// 创建一棵二叉树
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = 1;
root->left = (TreeNode*)malloc(sizeof(TreeNode));
root->left->val = 2;
root->left->left = NULL;
root->left->right = NULL;
root->right = (TreeNode*)malloc(sizeof(TreeNode));
root->right->val = 3;
root->right->left = (TreeNode*)malloc(sizeof(TreeNode));
root->right->left->val = 4;
root->right->left->left = NULL;
root->right->left->right = NULL;
root->right->right = (TreeNode*)malloc(sizeof(TreeNode));
root->right->right->val = 5;
root->right->right->left = NULL;
root->right->right->right = NULL;
// 计算二叉树高度
int height = tree_height(root);
printf("二叉树的高度为:%d\n", height);
return 0;
}
```
在这个程序中,我们定义了一个`TreeNode`结构体表示二叉树节点,其中包含`val`表示节点的值,`left`和`right`分别表示左右子树指针。接着,我们定义了一个`tree_height`函数用于递归计算二叉树高度。在函数中,先判断当前节点是否为空,如果为空,则返回0;否则,分别递归求解左子树和右子树的高度,最后返回左右子树高度的较大值加1。
在`main`函数中,我们创建了一棵二叉树,并调用`tree_height`函数计算它的高度。最后,程序输出二叉树的高度。
用c语言创建一棵二叉链表存储结构的二叉树; 利用先序遍历非递归算法遍历所建二叉树
以下是C语言创建二叉链表存储结构的二叉树,并使用先序遍历非递归算法进行遍历的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
char data;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
typedef struct Stack {
int top;
int size;
TreeNode** data;
} Stack;
// 初始化栈
Stack* init_stack(int size) {
Stack* s = (Stack*)malloc(sizeof(Stack));
s->size = size;
s->data = (TreeNode**)malloc(sizeof(TreeNode*) * size);
s->top = -1;
return s;
}
// 入栈
void push(Stack* s, TreeNode* node) {
if (s->top == s->size - 1) {
return;
}
s->data[++s->top] = node;
}
// 出栈
TreeNode* pop(Stack* s) {
if (s->top == -1) {
return NULL;
}
return s->data[s->top--];
}
// 创建二叉树
TreeNode* create_tree() {
char ch;
scanf("%c", &ch);
if (ch == '#') {
return NULL;
}
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->data = ch;
root->left = create_tree();
root->right = create_tree();
return root;
}
// 非递归先序遍历
void preorder_traversal(TreeNode* root) {
if (!root) {
return;
}
Stack* s = init_stack(100);
push(s, root);
while (s->top > -1) {
TreeNode* node = pop(s);
printf("%c ", node->data);
if (node->right) {
push(s, node->right);
}
if (node->left) {
push(s, node->left);
}
}
}
int main() {
printf("请输入二叉树,#表示空节点:\n");
TreeNode* root = create_tree();
printf("非递归先序遍历结果为:\n");
preorder_traversal(root);
return 0;
}
```
在这个示例代码中,我们首先定义了一个二叉树节点的结构体`TreeNode`,其中包含了节点的数据`data`以及左右子节点的指针`left`和`right`。接着,我们定义了一个栈的结构体`Stack`,用于辅助实现非递归遍历。`init_stack`函数用于初始化栈,`push`函数用于将节点入栈,`pop`函数用于将节点出栈。
在`create_tree`函数中,我们使用递归的方式创建二叉树。读入一个字符,如果是`#`则表示这个节点为空,返回`NULL`;否则创建一个新节点,将这个字符赋值给节点的数据域,然后递归创建左右子树,并将左右子树的根节点分别赋值给节点的左右指针。
最后,在`preorder_traversal`函数中,我们使用非递归的方式实现了先序遍历。首先初始化一个栈,将根节点入栈。然后重复如下步骤:从栈中取出一个节点,输出它的数据域,并将它的右子节点和左子节点(如果存在)分别入栈。直到栈为空为止。
最终,我们在`main`函数中调用`create_tree`函数创建二叉树,然后调用`preorder_traversal`函数进行先序遍历,并将结果输出。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)