二叉排序树的建立

浏览数：22 / 时间：2015年06月08日

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

测试数据：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>

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

二叉排序树的建立