二叉排序树c语言的创建
❶ 请问c语言如何创建二叉树
创建二叉树的源程序如下：
#include <cstdlib>
#include <stdio.h>
typedef struct node
{ //树的结点
int data;
struct node* left;
struct node* right;
} Node;
typedef struct
{ //树根
Node* root；
} Tree;
void insert(Tree* tree, int value)//创建树
{
Node* node=(Node*)malloc(sizeof(Node));//创建一个节点
node->data = value;
node->left = NULL;
node->right = NULL;
if (tree->root == NULL)//判断树是不是空树
{
tree->root = node;
}
else
{//不是空树
Node* temp = tree->root;//从树根开始
while (temp != NULL)
{
if (value < temp->data)//小于就进左儿子
{
if (temp->left == NULL)
{
temp->left = node;
return;
}
else
{//继续判断
temp = temp->left;
}
}
else {//否则进右儿子
if (temp->right == NULL)
{
temp->right = node;
return;
}
else {//继续判断
temp = temp->right;
}
}
}
}
return；
}
void inorder(Node* node)//树的中序遍历
{
if (node != NULL)
{
inorder(node->left);
printf("%d ",node->data);
inorder(node->right);
}
}
int main()
{
Tree tree;
tree.root = NULL;//创建一个空树
int n;
scanf("%d",&n);
for (int i = 0; i < n; i++)//输入n个数并创建这个树
{
int temp;
scanf("%d",&temp);
insert(&tree, temp);
}
inorder(tree.root);//中序遍历
getchar();
getchar();
return 0;
}
(1)二叉排序树c语言的创建扩展阅读：
简单二叉树定义范例：此树的顺序结构为：ABCDE
#include <cstdlib>
#include <stdio.h>
#include <string>
int main()
{
node* p = newnode;
node* p = head;
head = p;
string str;
cin >> str;
creat(p, str, 0)//默认根结点在str下标0的位置
return 0;
}
//p为树的根结点（已开辟动态内存）,str为二叉树的顺序存储数组ABCD##E或其他顺序存储数组，r当前结点所在顺序存储数组位置
void creat(node* p, string str, int r)
{
p->data = str[r];
if (str[r * 2 + 1] == '#' || r * 2 + 1 > str.size() - 1)p->lch = NULL；
else
{
p->lch = newnode;
creat(p->lch, str, r * 2 + 1);
}
if (str[r * 2 + 2] == '#' || r * 2 + 2 > str.size() - 1)p->rch = NULL;
else
{
p->rch = newnode;
creat(p->rch, str, r * 2 + 2);
}
}
❷ 二叉排序树的实现(c语言)
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
typedef struct btnode
{char data; /*suppose the data field's type is char*/
struct btnode *lchild; /*left pointer field */
struct btnode *rchild; /*right pointer field */
}NODE;
void main()
{ NODE *root,*q,n;
NODE *create(NODE *p);
void preorder(NODE *root);
void inorder(NODE *root);
void postorder(NODE *root);
int t;
q=&n;
root=create(q);
printf("At the first,we create a tree\n");
printf("Please input nodes of tree\n");
if (root==NULL) printf("It's an empty tree!\n");
else
{
printf("\n1.The preordetraverse \n");
printf(" 2.The inordertraverse \n");
printf(" 3.The postordertraverse \n");
printf(" Please choose a kind of order\n");
scanf("%d",&t);
switch (t)
{
case 1: preorder(root); break;
case 2: inorder(root); break;
case 3:postorder(root); break;
default: printf(" The error!");
}
}
}
NODE * create(NODE *p) /*create the structure of binary tree */
{ char ch;
NODE *t;
scanf("%c",&ch);
if(ch==' ') p=NULL;
else
{p->data=ch;
t=(NODE *)malloc(sizeof(NODE));
p->lchild=create(t);
t=(NODE*)malloc(sizeof(NODE));
p->rchild=create(t);
}
return p;
}
void preorder(NODE *root) /*travel the tree using preorder */
{ if (root!=NULL)
{ printf( " %c", root->data);
preorder(root->lchild);
preorder(root->rchild);
}
return;
}
void inorder (NODE *root) /*travel the tree using inorder */
{ if (root!=NULL)
{ inorder(root->lchild);
printf(" %c ", root->data);
inorder(root->rchild);
}
return;
}
void postorder(NODE *root) /*travel the tree using postorder */
{ if (root!=NULL)
{ postorder (root->lchild);
postorder (root->rchild);
printf(" %c ", root->data);
}
return;
}
❸ 急求二叉排序树的实现 用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;
}
❹ 二叉排序树的C语言实现
两处编译错误 已修改
见代码中注释([flczzhang]->XXX)
#include<stdio.h>
#include<stdlib.h>
typedefintKeyType;
typedefstructnode
{
KeyTypekey;
structnode*lchild,*rchild;
}BSTNode;
typedefBSTNode*BSTree;
//二叉排序树插入
//若二叉排序树*Tptr中没有关键字为key，则插入，否则直接返回
voidInsertBST(BSTree*TPtr,KeyTypekey)
{
BSTNode*f,*p;
p=*TPtr; //p的初值指向根结点
while(p) //查找插入位置
{
if(p->key==key) //树中已有key，无须插入
{
return;
}
f=p; //f保存当前查找的结点
//若key<p->key，则在左子树中查找，否则在右子树中查找
p=(key<p->key)?p->lchild:p->rchild;
}
p=(BSTNode*)malloc(sizeof(BSTNode));
p->key=key;
p->lchild=p->rchild=NULL; //生成新结点
if(*TPtr==NULL) //原树为空
{
*TPtr=p; //新插入的结点为新的根
}
else//原树非空时将新结点p作为f的左孩子或右孩子插入
{
if(key<f->key)
{
f->lchild=p;
}
else
{
f->rchild=p;
}
}//[flczzhang]->missa}
}
//创建二叉排序树
//输入一个结点序列，建立一棵二叉排序树，将根结点指针返回
BSTreeCreateBST(void)
{
BSTreeT=NULL;
KeyTypekey;
scanf("%d",&key);
while(key) //假设key=0是输人结束标志
{
InsertBST(&T,key); //将key插入二叉排序树T
scanf("%d",&key); //读人下一关键字
}
returnT;
}
//查找二叉排序树T中是否存在指定的key
//指针f指向T的双亲,f初始值为NULL
//若查找成功返回1，指针p指向该数据元素结点，否则返回0，p指向查找过程中的最后一个结点
intSearchBST(BSTreeT,intkey,BSTreef,BSTree*p)
{
if(!T)
{
*p=f;
return0;
}
elseif(T->key==key)
{
*p=T;
return1;
}
elseif(T->key>key)
{
returnSearchBST(T->lchild,key,T,p);
}
else
{
returnSearchBST(T->rchild,key,T,p);
}
}
//访问节点数据
voidvisit(KeyTypec,intlevel)
{
printf("%d在第%d层 ",c,level);
}
//前序遍历树节点
voidPreorderTraverse(BSTreeT,intlevel)
{
if(T)
{
visit(T->key,level);
PreorderTraverse(T->lchild,level+1);
PreorderTraverse(T->rchild,level+1);
}
}
intmain()
{
intlevel=1;
BSTreeT;
T=CreateBST();//[flczzhang]->(missinge)
PreorderTraverse(T,level);
return0;
}
❺ 用C语言实现二叉排序树的构造
#include <滑判stdio.h>
#include <stdlib.h>
typedef struct bnode
{
int data;
struct bnode *left , *right ;
} btree ;
void insert(btree **b , btree *s)
{
if(*b==NULL) *b = s ;
else if((*b)->data == s->data)
return ;
else if(s->橡枣data > (*b)->data)
insert(&(*b)->right , s);
else if(s->data < (*b)->data)
insert(&(*b)->left , s);
}
void creatTree(btree **b)
{
int x ;
btree *s ;
*b = NULL ;
do
{
printf("Input data please : ");
scanf("%d",&x);
s = (btree *)malloc(sizeof(btree)) ;
s->data = x ;
s->left = NULL ;
s->right = NULL ;
insert( b , s );
} while(x != 0 );
}
void print(btree *b)
{
if (b != NULL)
{
printf("%d",b->data);
if (b->left != NULL || b->信如改right != NULL)
{
printf("(");
print(b->left);
if(b->right != NULL)
printf(", ");
print(b->right);
printf(")");
}
}
}
void preorder(btree *b)
{
if (b!=NULL)
{
printf("%d",b->data);
preorder(b->left);
preorder(b->right);
}
}
void main()
{
btree *t = NULL;
creatTree(&t);
printf("The binary tree is : ");
print(t);
printf("\n");
preorder(t);
printf("\n");
}