用C语言完成下列人物1:读懂已给出的建立二叉树的算法 ;在算法关键语句处写出注释 2:写出二叉树中序遍历的递归算法; 3:在以上基础上,针对给出的主程序,假设输入的数据依次是4(回车)ephq,请输出该二叉树的中序遍历序列,画出该二叉树,并分析用该算法建立的二叉树的特点。 #include<stdio.h> #include<stdlib.h> typedef struct node { char data; struct node *lchild,*rchild; }bnode,*blink; blink add(blink bt,char ch) { if(bt==NULL) // { bt=(blink)malloc(sizeof(bnode)); bt->data=ch; bt->lchild=bt->rchild=NULL; } else if(ch<bt->data) // bt->lchild=add(bt->lchild,ch); // else // bt->rchild=add(bt->rchild,ch); // return bt; } void inorder(blink bt)//中序遍历算法 { } int main() { blink root=NULL; int i,n; char x; scanf("%d",&n);//结点总个数为n getchar();//获取上面语句中多余的回车符 for(i=1;i<=n;i++) { x=getchar(); root=add(root,x); } inorder(root); printf("\n"); return 0; }
时间: 2023-06-01 11:08:09 浏览: 63
1. 算法注释:
建立二叉树的算法基于递归实现,如果当前节点为空,则新建一个节点,并将该节点的值设为输入的字符;如果当前节点存在,则判断它的左右子节点是否为空,如果为空,就将新建一个节点作为该节点的子节点;如果不为空,就递归进入该节点的子节点,直到左右子节点有空的位置可以插入新节点。
2. 二叉树中序遍历的递归算法:
中序遍历二叉树的递归实现是:先递归遍历左子树,再输出当前节点的值,最后递归遍历右子树。代码实现如下:
void inorderTraversal(TreeNode *root)
{
if (root != NULL)
{
inorderTraversal(root->left);
printf("%c ", root->data);
inorderTraversal(root->right);
}
}
3. 给定数据4ephq的二叉树中序遍历序列为:e h p q 4。
该二叉树的结构如下图所示:
```
4
/ \
e p
/ \
h q
```
该算法建立的二叉树的特点是,它是一个完全二叉树。在该算法中,新建节点时,总是先将节点插入左子树,如果左子树已经存在,才会依次递归进入右子树。因此,如果得到的输入数据是按照完全二叉树的顺序排列,那么该算法建立的二叉树就是完全二叉树。
相关问题
请用C语言写出程序:输入字符序列,建立二叉树;按先序中序后序遍历二叉树(三种递归算法和中序遍历的非递归算法)
```c
#include <stdio.h>
#include <stdlib.h>
//定义二叉树结构体
struct TreeNode {
char data;
struct TreeNode* left;
struct TreeNode* right;
};
//根据输入的字符序列建立二叉树
struct TreeNode* createBinaryTree() {
char ch;
scanf("%c", &ch);
if (ch == '#') {
return NULL;
}
struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->data = ch;
root->left = createBinaryTree();
root->right = createBinaryTree();
return root;
}
//先序遍历二叉树(递归算法)
void preOrderTraversalRecursive(struct TreeNode* root) {
if (root == NULL) {
return;
}
printf("%c ", root->data);
preOrderTraversalRecursive(root->left);
preOrderTraversalRecursive(root->right);
}
//中序遍历二叉树(递归算法)
void inOrderTraversalRecursive(struct TreeNode* root) {
if (root == NULL) {
return;
}
inOrderTraversalRecursive(root->left);
printf("%c ", root->data);
inOrderTraversalRecursive(root->right);
}
//后序遍历二叉树(递归算法)
void postOrderTraversalRecursive(struct TreeNode* root) {
if (root == NULL) {
return;
}
postOrderTraversalRecursive(root->left);
postOrderTraversalRecursive(root->right);
printf("%c ", root->data);
}
//中序遍历二叉树(非递归算法)
void inOrderTraversal(struct TreeNode* root) {
struct TreeNode* stack[100];
int top = -1;
struct TreeNode* p = root;
while (p != NULL || top != -1) {
if (p != NULL) {
stack[++top] = p;
p = p->left;
} else {
p = stack[top--];
printf("%c ", p->data);
p = p->right;
}
}
}
int main() {
printf("请输入字符序列,以#表示空节点:\n");
struct TreeNode* root = createBinaryTree();
printf("先序遍历结果:");
preOrderTraversalRecursive(root);
printf("\n中序遍历结果:");
inOrderTraversalRecursive(root);
printf("\n后序遍历结果:");
postOrderTraversalRecursive(root);
printf("\n中序遍历结果(非递归算法):");
inOrderTraversal(root);
return 0;
}
```
以二叉链表作为二叉树的存储结构, 编写以下算法: (2) 判别 两棵树是否相等。用c语言写出完整的代码与注释
以下是用 C 语言实现判断两棵树是否相等的算法,基于二叉链表存储结构:
```c
#include <stdio.h>
#include <stdlib.h>
/* 定义二叉树节点 */
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
/* 创建新节点 */
TreeNode* createNode(int val) {
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
}
/* 判断两棵树是否相等 */
bool isSameTree(TreeNode* p, 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);
}
/* 测试 */
int main() {
/* 构造两棵树 */
TreeNode* p = createNode(1);
p->left = createNode(2);
p->right = createNode(3);
TreeNode* q = createNode(1);
q->left = createNode(2);
q->right = createNode(3);
/* 判断两棵树是否相等 */
if (isSameTree(p, q)) {
printf("两棵树相等\n");
} else {
printf("两棵树不相等\n");
}
return 0;
}
```
注释在代码中已经给出。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![.zip](https://img-home.csdnimg.cn/images/20210720083646.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)