怎么建立二叉排序树(二叉排序树建立方法说明)

图标

豆瓜

豆瓜网

豆瓜官网专栏

豆瓜 图标 2022-01-15 10:15:24

设计一个算法,读入一整串整数构成一棵二叉排序树并进行查找。

测试数据:60 35 69 84 96 13 66 34 21 0

输出:13 21 34 35 60 66 69 84 96

输入查找数据:40

输出:13 21 34 35 60 66 69 84 96

算法思想:二叉排序树的构成,从空的二叉树开始,每次输入一个结点数据,就建立一个新结点插入到当前已生成的二叉排序树中,所以它的主要操作是二叉排序树的插入运算。在二叉排序树插入新的结点,只要保证插入后仍符合二叉排序树的定义即可。二叉排序树的查找过程:当二叉排序树非空时,首先将给定值与根结点比较,若相等,则查找成功,若小于根结点,则在左子树继续查找,若大于根结点的值,则在右子树上继续查找。

代码:

(1)中序遍历二叉树算法 inorder  (2)二叉排序树的插入算法 inserbst  (3)生成二叉排序树算法 creatord  (4)主函数

复制代码

#include <iostream>#include <stdio.h>#include<malloc.h>using namespace std;
typedef struct node
{    int key;    struct node *lchild, *rchild;
}bstnode;void inorder(bstnode *t)
{    if(t!=NULL)
    {
        inorder(t->lchild);
        printf("%4d",t->key);
        inorder(t->rchild);
    }//中序查找}
bstnode * insertbst(bstnode *t,int k)
{
    bstnode *p;    if(t==NULL)
    {
        p=(bstnode *)malloc(sizeof(bstnode));
        p->key=k;
        p->lchild=NULL;
        p->rchild=NULL;        return (p);
    }    else if(t->key==k) return(t);    else if(t->key>k){t->lchild=insertbst(t->lchild,k);return (t);}    else{t->rchild=insertbst(t->rchild,k);return(t);}
}
bstnode *creatord(){
bstnode *t;int key;
t=NULL;
scanf("%d",&key);while(key!=0)
    {
        t=insertbst(t,key);
        scanf("%d",&key);}        return (t);

}int main()
{    //cout << "Hello world!" << endl;
    int key;
    bstnode * root;
    root=creatord();
    inorder(root);
    printf("\n input search key:");
    scanf("%d",&key);
    insertbst(root,key);
    inorder(root);
    printf("\n");    return 0;
}


malloc函数为动态分配空间;
原型为: void * malloc(int size);

使用方法一般为:
假设你定义了一个名为Node的struct类型,你要定义一个名为a的Node类型的指针变量,使用以下语句:
Node * a=(Node *)malloc(sizeof(Node));
其中(Node *)为强制转换,把返回类型void *转换为Node *,sizeof(Node)为获取Node类型占据空间的大小,如在我机子上int类型占4字节,sizeof(int)就返回4;
使用malloc需要包含#include <malloc.h>

 


本文由豆瓜网专栏作家 豆瓜 投稿发布,并经过豆瓜网编辑审核。

转载此文章须经作者同意,并附上出处(豆瓜网)及本页链接。

若稿件文字、图片、视频等内容侵犯了您的权益,请联系本站进行 投诉处理

相关搜索

二叉排序树
图标 图标

豆瓜

豆瓜网

豆瓜官网专栏

  • 找不到或无法加载主类

    找不到或无法加载主类

    图标
    豆瓜 图标 · 今天 10:49:41 · 147浏览
  • grep命令

    图标
    豆瓜 图标 · 今天 10:48:54 · 77浏览
  • 数据库设计有什么好处

    图标
    豆瓜 图标 · 今天 10:23:13 · 225浏览
  • 全部评论

    豆瓜

    豆瓜网

    豆瓜官网专栏

  • 找不到或无法加载主类
  • grep命令
  • 数据库设计有什么好处
  • 怎么建立二叉排序树(二叉排序树建立方法说明)
  • mysql怎么备份数据
  • 我来说两句