用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 21:08:03 浏览: 59
1. 算法关键语句注释:
typedef struct bianarytree
{
char data;
struct bianarytree *left,*right;
}Node;
// 建立二叉树
void creat(Node **root)
{
char ch;
scanf("%c",&ch);
if(ch==' ')
{
*root=NULL; // 如果该节点为空则赋值为NULL
}
else
{
*root=(Node*)malloc(sizeof(Node)); // 给该节点分配空间
(*root)->data=ch; // 节点数据赋值
creat(&(*root)->left); // 递归建立左子树
creat(&(*root)->right); // 递归建立右子树
}
}
2. 二叉树中序遍历的递归算法:
void inorder(Node *root) // 中序遍历的递归算法
{
if(root!=NULL)
{
inorder(root->left); // 先遍历左子树
printf("%c ",root->data); // 输出当前节点
inorder(root->right); // 再遍历右子树
}
}
3. 主程序输入数据为4ephq,该二叉树中序遍历序列为:e 4 h p q。该二叉树画图如下:
4
/ \
e p
/ \
h q
该算法建立的二叉树特点是:从根节点出发,尽可能往左建树,然后再往右建树,使得二叉树的高度尽可能小。同时,该二叉树中序遍历序列是按照节点的数据从小到大输出的。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)
![](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)