创建二叉排序树代码

㈠ 二叉排序树怎么构造

假设二叉排序树T为空，则创建一个keyword为k的结点。将其作为根结点。

否则将k和根结点的keyword进行比较，假设相等则返回，假设k小于根结点的keyword则插入根结点的左子树中，否则插入根结点的右子树中。

int InsertBST(BSTNode *p, KeyType k)
{
if(p==NULL)
{
p=(BSTNode*)malloc(sizeof(BSTNode));
p->key=k;
p->lchild=p->rchild=NULL;
return 1;
}
else if(k==p->key)
return 0;
else if(k<p->key)
return InsertBST(p->lchild, k);
else
return InsertBST(p->rchild, k);
}
二叉排序树的生成算法：
BSTNode *CreateBST(KeyType A[], int n)
{
BSTNode *bt=NULL;
int i=0;
while(i<n)
{
InsertBST(bt, A[i]);
i++;
}
return bt;
}

(1)创建二叉排序树代码扩展阅读：

在一般情况下，设 P（n，i）为它的左子树的结点个数为 i 时的平均查找长度。如图的结点个数为 n = 6 且 i = 3; 则 P（n,i）= P（6, 3） = [ 1+ ( P(3) + 1) * 3 + ( P(2) + 1) * 2 ] / 6= [ 1+ ( 5/3 + 1) * 3 + ( 3/2 + 1) * 2 ] / 6

注意：这里 P(3)、P(2) 是具有 3 个结点、2 个结点的二叉分类树的平均查找长度。 在一般情况，P（i）为具有 i 个结点二叉分类树的平均查找长度。平均查找长度= 每个结点的深度的总和 / 总结点数。

㈡ 急求二叉排序树的实现 用c语言写出代码

程序按你的要求改写，去掉了不少功能，大大简化，但总体功能依旧强大。
先要选择0，创建一棵树，然后程序提示你要输入的数组数字的个数，比如要输入10个数字，输入10，然后再分别输入各个数字。要注意看程序提示。
一个完整的c程序如下,程序在win-tc和Dev-c++下都调试通过。
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

struct node {
int value;
struct node* left;
struct node* right;
};
typedef struct node NODE;
typedef struct node* PNODE;

PNODE creat( PNODE tree,PNODE r,int value)
{
if(!r)
{
r = (PNODE)malloc(sizeof(NODE));
if(!r)
{
printf("内存分配失败！");
exit(0);
}
r->left = NULL;
r->right = NULL;
r->value = value;
if(!tree)
return r;
if(value<tree->value)
tree->left = r;
else
tree->right = r;
return r;
}
if(value < r->value)
creat(r,r->left,value);
else
creat(r,r->right,value);
return tree;
}
void new_node (PNODE* n, int value) {

*n = (PNODE)malloc (sizeof(NODE));
if (*n != NULL) {
(*n)->value = value;
(*n)->left = NULL;
(*n)->right = NULL;
}
}
void free_node (PNODE* n) {
if ((*n) != NULL) {
free (*n);
*n = NULL;
}
}
/* 查找结点 */
PNODE find_node (PNODE n, int value) {
if (n == NULL) {
return NULL;
} else if (n->value == value) {
return n;
} else if (value <= n->value) {
return find_node (n->left, value);
} else {
return find_node (n->right, value);
}
}
/* 插入结点 */
void insert_node (PNODE* n, int value) {
if (*n == NULL) {
new_node (n, value);
} else if (value == (*n)->value) {
return;
} else if (value < (*n)->value) {
insert_node (&((*n)->left), value);
} else {
insert_node (&((*n)->right), value);
}
}

/* 删除结点 */
void deletenode (PNODE *n) {
PNODE tmp = NULL;
if (n == NULL) return;
if ((*n)->right == NULL) {
tmp = *n;
*n = (*n)->left;
free_node (n);
} else if ((*n)->left == NULL) {
tmp = *n;
*n = (*n)->right;
free_node (n);
} else {
for (tmp = (*n)->right; tmp->left != NULL; tmp = tmp->left);
tmp->left = (*n)->left;
tmp = (*n);
*n = (*n)->right;
free_node (&tmp);
}
}
void delete_node (PNODE *n, int value) {
PNODE node;
if (n == NULL) return;
node = find_node (*n, value);
if ((*n)->value == value) {
deletenode (n);
} else if (value < (*n)->value) {
delete_node (&((*n)->left), value);
} else {
delete_node(&((*n)->right), value);
}
}
void pre_order_traversal(PNODE n) /* 前序遍历 */
{
if (n != NULL) {
printf ("%i ", n->value);
pre_order_traversal (n->left);
pre_order_traversal( n->right);
}
}
void in_order_traversal (PNODE n) /* 中序遍历 */
{
if (n != NULL) {
in_order_traversal (n->left);
printf ("%i ", n->value);
in_order_traversal ( n->right);
}
}
void post_order_traversal (PNODE n) /* 后序遍历 */
{
if (n != NULL) {
post_order_traversal (n->left);
post_order_traversal (n->right);
printf ("%i ", n->value);
}
}
int get_num_nodes (PNODE n) /* 计算树的节点数 */
{int left = 0;
int right = 0;
if (n == NULL) {
return 0;
}
if (n->left != NULL) {
left = get_num_nodes (n->left);
}
if (n->right != NULL) {
right = get_num_nodes (n->right);
}
return (left + 1 + right);
}
int main() {
char buf[50];
int i,n,option,s[80];
PNODE tree = NULL;/*树的第一个结点*/
PNODE node = NULL;
while (1) {
printf ("--------------------------\n");
printf ("Options are:\n\n");
printf (" 0 Creat tree\n");
printf (" 1 Insert node\n");
printf (" 2 Delete node\n");
printf (" 3 Find node\n");
printf (" 4 Pre order traversal\n"); /* 前序遍历 */
printf (" 5 In order traversal\n"); /* 中序遍历 */
printf (" 6 Post order traversal\n");/* 后序遍历 */
printf (" 7 Node Count\n");
printf (" 8 Exit\n\n");
printf ("--------------------------\n");
printf ("Select an option: ");
fgets (buf, sizeof(buf), stdin);
sscanf (buf, "%i", &option);
printf ("--------------------------\n");
if (option < 0 || option > 12) {
fprintf (stderr, "Invalid option");
continue;
}
switch (option) {
case 0:
printf ("Enter number of elements of array: ");
scanf("%d",&n);
printf ("Enter %d elements of array:\n",n);
for(i=0;i<n;i++)
{ scanf("%d",&s[i]);
tree = creat(tree,tree,s[i]);
}
fflush(stdin);
break;
case 1:
printf ("Enter number to insert: ");
fgets (buf, sizeof(buf), stdin);
sscanf (buf, "%i", &option);
printf ("\n\n");
insert_node (&tree, option);
break;
case 2:
printf ("Enter number to delete: ");
fgets (buf, sizeof(buf), stdin);
sscanf (buf, "%i", &option);
printf ("\n\n");
delete_node (&tree, option);
break;
case 3:
printf ("Enter number to find: ");
fgets (buf, sizeof(buf), stdin);
sscanf (buf, "%i", &option);
printf ("\n\n");
node = find_node (tree, option);
if (node != NULL) {
printf ("Found node\n\n");
} else {
printf ("There is no node which you input!\n\n");
}
break;
case 4:
printf ("Pre order traversal: ");
pre_order_traversal (tree);
printf ("\n\n");
break;
case 5:
printf ("In order traversal: ");
in_order_traversal (tree);
printf ("\n\n");
break;
case 6:
printf ("Post order traversal: ");
post_order_traversal (tree);
printf ("\n\n");
break;
case 7:
printf ("Node Count is %i\n\n", get_num_nodes (tree));
break;
case 8:
exit (0);
}
}
return 0;
}