二叉排序樹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");
}