c語言二叉樹排序

㈠ c語言二叉樹排序

前:FCADBEG
中:ACBDFEG
後:ABDCGEF

㈡ 用C語言實現二叉排序樹排序，並按遞減順序列印各個數據

#include <stdio.h>
#include <malloc.h>
typedef int KeyType;
typedef char InfoType[10];
typedef struct node //記錄類型
{
KeyType key; //關鍵字項
InfoType data; //其他數據域
struct node *lchild,*rchild; //左右孩子指針
} BSTNode;
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) //樹中存在相同關鍵字的結點,返回0
return 0;
else if (k<p->key)
return InsertBST(p->lchild,k); //插入到*p的左子樹中
else
return InsertBST(p->rchild,k); //插入到*p的右子樹中
}
BSTNode *CreateBST(KeyType A[],int n) //返回BST樹根結點指針
{
BSTNode *bt=NULL; //初始時bt為空樹
int i=0;
while (i<n)
{
InsertBST(bt,A[i]); //將關鍵字A[i]插入二叉排序樹T中
i++;
}
return bt; //返回建立的二叉排序樹的根指針
}

void DispInDescrease(BSTNode *bt){ //按從小到大輸出查找樹中的內容，對該樹中序遍歷即可
if(bt){
DispInDescrease(bt->lchild);
printf("%d\t",bt->key);
DispInDescrease(bt->rchild);
}
}
void main()
{
BSTNode *bt,*p,*f;
int n=9;
KeyType a[]={1,12,5,8,3,10,7,13,9};
bt=CreateBST(a,n);
DispInDescrease(bt);
}
//已上機驗證成功

㈢ 二叉排序樹的實現(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語言二叉樹排序的一道題目

#include<stdio.h>
#include<stdlib.h>
#define Maxsize 100
typedef char elemtype;
typedef struct node
{ elemtype data;
struct node* lchild;
struct node* rchild;
}BTNode;

#include<stdio.h>
#include<stdlib.h>
#define Maxsize 100
typedef char elemtype;

int BTWidth(BTNode *b)
{ struct
{ int lno;
BTNode *p;
}Qu[Maxsize];
int front,rear;
int lnum,max,i,n;
front=rear=0;
if(b!=NULL)
{ rear++;
Qu[rear].p=b;
Qu[rear].lno=1;
while(rear!=front)
{ front++;
b=Qu[front].p;
lnum=Qu[front].lno;
if(b->lchild!=NULL)
{ rear++;
Qu[rear].p=b->lchild;
Qu[rear].lno=lnum+1;
}
if(b->rchild!=NULL)
{ rear++;
Qu[rear].p=b->rchild;
Qu[rear].lno=lnum+1;
}
}
max=0;
lnum=1;
i=0;
while(i<=rear)
{ n=0;
while(i<=rear&&Qu[i].lno==lnum)
{ n++;
i++;
}
lnum=Qu[i].lno;
if(n>max)
max=n;
}
return max;
}
else
return 0;
}

int Btnodedepth(BTNode *b)
{ int h1,h2;
if(!b)return 0;
if(!b->lchild&&!b->rchild)
return 1;
else
{ h1=Btnodedepth(b->lchild);
h2=Btnodedepth(b->rchild);
return 1+(h1>h2?h1:h2);
}
}

int Leafnode(BTNode *b)
{ int h,h1,h2;
if(!b)return 0;
if(!b->lchild&&!b->rchild)
return 1;
else
{ h1=Leafnode(b->lchild);
h2=Leafnode(b->rchild);
h=h1+h2;
return h;
}
}

void disp(BTNode* b)
{ if(b)
{ printf("%c",b->data);
if(b->lchild||b->rchild)
{ printf("(");
disp(b->lchild);
printf(",");
disp(b->rchild);
printf(")");
}
}
}

int creat(BTNode* &b)
{ char ch;
scanf("%c",&ch);
if(ch==',')b=NULL;
else
{ b=(BTNode*)malloc(sizeof(node));
if(!b)exit(0);
b->data=ch;
creat(b->lchild);
creat(b->rchild);
}
return 0;
}

int nodenumber(BTNode* b)
{ if(!b)
return 0;
else
return (nodenumber(b->lchild)+nodenumber(b->rchild)+1);
}

BTNode* FindNode(BTNode* b,elemtype x)
{ int flag1=0,flag2=0;
BTNode *b1,*b2;
if(!b)
return NULL;
if(b->data==x)
{ return b;flag1=1;
}
if(!flag1)
b1=FindNode(b->lchild,x);
if(b1!=NULL)
return b1;
else
b2=FindNode(b->rchild,x);
if(b2!=NULL)
return b2;
else
return NULL;
}

BTNode* LchildNode(BTNode *find)
{ return find->lchild;
}

BTNode* RchildNode(BTNode *find)
{ return find->rchild;
}

void menu()
{ printf("\t\t\t[1]建立二叉樹\n\t\t\t[2]深度\n\t\t\t[3]寬度\n\t\t\t[4]樹葉\n\t\t\t[5]\
顯示元素\n\t\t\t[6]菜單\n\t\t\t[7]所有結點個數\n\t\t\t[8]BTNode* FindNode(BTNode* b,\
elemtype x)\n\t\t\t[9] the lchild and rchild of X which found by [8]\n\t\t\t[0]退出\n");
}
int main()
{ char c,x;
BTNode *root=NULL,*find,*l,*r;
menu();
do
{ printf("功能選擇:");
scanf("%c",&c);
getchar();
switch(c)
{ case '1':printf("請輸入結點值，','為虛結點，回車結束！！\
\n---先序--請保證數據正確完整如:ABC,,DE,G,,F,,,\n:")\
;creat(root);getchar();break;
case '2':
printf("二叉樹深度%d\n",Btnodedepth(root));;break;
case '3':
printf("二叉樹寬度%d\n",BTWidth(root));break;
case '4':
printf("二叉樹樹葉數量%d\n",Leafnode(root));break;
case '5':disp(root);
printf("\n");break;
case '6':menu();break;
case '7':
printf("所有結點個數:%d\n",nodenumber(root));break;
case '8':printf("input X:");
scanf("%c",&x);getchar();
find=FindNode(root,x);
if(find!=NULL)
printf("the element is:%c\n",find->data);
else printf("not found!\n");break;
case '9':
printf("the lchild and rchild of X:\n");
if((l=LchildNode(find))==NULL)
printf("lchild is NULL\n");
else printf("lchild is %c\n",l->data);
if((r=RchildNode(find))==NULL)
printf("rchild is NULL\n");
else printf("rchild is %c\n",r->data);
break;
case '0':break;
default:printf("輸入有誤\n");break;
}
}while(c!='0');
return 0;
}

中序遍歷
http://..com/question/36183981.html?si=1
時間復雜度
http://..com/question/82193747.html?si=6

㈤ C語言，二叉樹

void insert(node ** tree, int val) {
node * temp = NULL; if(!(*tree)) {
temp = (node *)malloc(sizeof(node));
temp->left = temp->right = NULL;
temp->data = val; *tree = temp; return ;
}
if (val < (*tree)->data) {
insert(&(*tree)->left,val);
}else if (val > (*tree)->data) {
insert(&(*tree)->right,val);
}
}

㈥ c語言數組實現二叉樹的問題，怎麼把二叉樹按順序列印出來。

#include<stdio.h> #include<stdlib.h> struct BiTNode *stack[100]; struct BiTNode//定義結構體 { char data; struct BiTNode *lchild,*rchild; }; void later(struct BiTNode *&p) //前序創建樹 { char ch; scanf("%c",&ch); if(ch==' ') p=NULL; else { p=(struct BiTNode *)malloc(sizeof(struct BiTNode)); p->data=ch; later(p->lchild); later(p->rchild); } } void print(struct BiTNode *p) //前序遍歷（輸出二叉樹） { int i=-1; while(1) { while(p!=NULL) { stack[++i]=p->rchild;/*printf("ok？\n");*/ printf("%c",p->data); p=p->lchild; } if(i!=-1) { p=stack[i]; i--; } else return; } } void main()//主函數 { struct BiTNode *p,*t; later(p); print(p); }

㈦ c語言 二叉排序樹 100分

#include <stdio.h>
#include <stdlib.h>

typedef struct _BiTNode {
int val;
struct _BiTNode* lhs;
struct _BiTNode* rhs;
}BiTNode;

//建立二叉排序樹
void inserttree(BiTNode** Tree, int val) //插入函數
{
BiTNode* t, *p, *n;
t = (BiTNode*)malloc(sizeof(BiTNode));
t->val = val;
t->lhs = t->rhs = NULL;

p = NULL, n = *Tree;
while(n) {
p = n;
n = val < n->val ? n->lhs : n->rhs;
}
(p ? val < p->val ? p->lhs : p->rhs : *Tree) = t;
}

void buildBST(BiTNode** Tree)
{
int val;
char c;
*Tree = NULL;
while(1) {
scanf("%d", &val);
inserttree(Tree, val);
if((c = getchar()) == '\n')
break;
else
ungetc(c, stdin);
}
}

//二叉排序樹查找
BiTNode* search(BiTNode* Tree, int val)
{
while(Tree) {
if(val < Tree->val)
Tree = Tree->lhs;
else if(val > Tree->val)
Tree = Tree->rhs;
else
return Tree;
}
return NULL;
}

//二叉排序樹刪除
void del(BiTNode* Tree)
{
if(Tree) {
del(Tree->lhs);
del(Tree->rhs);
free(Tree);
}
}

int main()
{
return 0;
}

㈧ C語言用三種不同的方法遍歷二叉樹並用兩種方式排序

以下是我的數據結構實驗的作業：肯定好用，裡面還包括了統計樹的深度和葉子數！記住每次做完一個遍歷還要重新輸入你的樹哦！
#include "stdio.h"
#include "string.h"
#define NULL 0
typedef struct BiTNode{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
BiTree Create(BiTree T){
char ch;
ch=getchar();
if(ch=='#')
T=NULL;
else{
if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))
printf("Error!");
T->data=ch;
T->lchild=Create(T->lchild);
T->rchild=Create(T->rchild);
}
return T;
}
void Preorder(BiTree T){
if(T){
printf("%c",T->data);
Preorder(T->lchild);
Preorder(T->rchild);
}
}
int Sumleaf(BiTree T){
int sum=0,m,n;
if(T){
if((!T->lchild)&&(!T->rchild))
sum++;
m=Sumleaf(T->lchild);
sum+=m;
n=Sumleaf(T->rchild);
sum+=n;
}
return sum;
}
void zhongxu(BiTree T){
if(T){
zhongxu(T->lchild);
printf("%c",T->data);
zhongxu(T->rchild);
}
}
void houxu(BiTree T){
if(T){
houxu(T->lchild);
houxu(T->rchild);
printf("%c",T->data);
}
}
int Depth(BiTree T){
int dep=0,depl,depr;
if(!T) dep=0;
else{
depl=Depth(T->lchild);
depr=Depth(T->rchild);
dep=1+(depl>depr?depl:depr);
}
return dep;
}
main(){
BiTree T;
int sum,dep;
T=Create(T);
Preorder(T);
printf("\n");
zhongxu(T);
printf("\n");
houxu(T);
printf("\n");
sum=Sumleaf(T);
printf("%d",sum);
dep=Depth(T);
printf("\n%d",dep);
}
在Turbo C的環境下，先按Ctrl+F9運行程序，此時就是建立二叉樹的過程，例如輸入序列ABC##DE#G##F###（其中的「#」表示空，並且輸入過程中不要加回車，因為回車也有對應的ASCII碼，是要算字元的，但是輸入完之後可以按回車退出），然後再按ALT+F5顯示用戶界面，這時候就能夠看到結果了。
另外你必須會手動建立一棵二叉樹，保證你輸入的序列能構成一棵二叉樹，否則你怎麼輸入，按最後按多少回車程序也不會結束！

㈨ 二叉排序樹的實現（c語言）

/*二叉樹的基本運算與實現*/
#include <stdio.h>
#include <malloc.h>
#define MAXNODE 256
typedef int datatype;
typedef struct BiTNode
{
datatype data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
typedef struct
{
BiTree link;
int flag;
}stacktype;void menu();
int Initiate(BiTree *bt,datatype x);
BiTree InsertL(BiTree bt,datatype x,BiTree parent);
BiTree InsertR(BiTree bt,datatype x,BiTree parent);
BiTree DeleteL(BiTree bt,BiTree parent);
BiTree DeleteR(BiTree bt,BiTree parent);
void PreOrder(BiTree bt);
void InOrder(BiTree bt);
void PostOrder(BiTree bt);
void LevelOrder(BiTree bt);
BiTree Find(BiTree parent,datatype a);
void NRPreOrder(BiTree bt);
void NRInOrder(BiTree bt);
void NRPostOrder(BiTree bt);void main()
{
int n,m=1;
BiTree t; /*clrscr();*/
while(m)
{
menu();
scanf("%d",&n);
switch(n)
{
case 1:{/*初始化*/
int flag;
datatype x;
printf("please input head point x:\n");
scanf("%d",&x);
flag=Initiate(&t,x);
if(flag==1)
printf("\nInitiate success!");
else
printf("\nInitiate fail!");
break;
}
case 2:{/*建樹*/
break;
}
case 3:{/*插入結點x作為a的左孩子*/
datatype a,x;/*x作為a的左孩子*/
BiTree parent=t;
printf("please input a and x:\n");
scanf("%d%d",&a,&x);
parent=Find(parent,a);
parent=InsertL(t,x,parent);
if(parent!=NULL)
t=parent;
break;
}
case 4:{/*插入結點x作為a的右孩子*/
datatype a,x;/*x作為a的右孩子*/
BiTree parent=t;
printf("please input a and x:\n");
scanf("%d%d",&a,&x);
parent=Find(parent,a);
parent=InsertR(t,x,parent);
if(parent!=NULL)
t=parent;
break;
}
case 5:{/*刪除結點a的左孩子*/
datatype a;
BiTree parent=t;
printf("please input a:\n");
scanf("%d",&a);
parent=Find(parent,a);
parent=DeleteL(t,parent);
if(parent!=NULL)
t=parent;
break;
}
case 6:{/*刪除結點a的左孩子*/
datatype a;
BiTree parent=t;
printf("please input a:\n");
scanf("%d",&a);
parent=Find(parent,a);
parent=DeleteR(t,parent);
if(parent!=NULL)
t=parent;
break;
}
case 7:{/*遞歸先序遍歷*/
PreOrder(t);
break;
}
case 8:{/*遞歸中序遍歷*/
InOrder(t);
break;
}
case 9:{/*遞歸後序遍歷*/
PostOrder(t);
break;
}
case 10:{/*層次遍歷*/
LevelOrder(t);
break;
}
case 11:{/*先序遍歷的非遞歸實現*/
NRPreOrder(t);
break;
}
case 12:{/*中序遍歷的非遞歸實現*/
NRInOrder(t);
break;
}
case 13:{/*後序遍歷的非遞歸實現*/
NRPostOrder(t);
break;
}
case 0:m=0;
}
}
}
void menu()
{
/*clrscr();*/
printf("\n");
printf("\t\t1.initiate\n\n");
printf("\t\t2.create thread\n\n");
printf("\t\t3.insert Left\n\n");
printf("\t\t4.insert Right\n\n");
printf("\t\t5.delete Left\n\n");
printf("\t\t6.delete Right\n\n");
printf("\t\t7.preorder\n\n");
printf("\t\t8.inorder\n\n");
printf("\t\t9.postorder\n\n");
printf("\t\t10.levelorder\n\n");
printf("\t\t11.nrpreorder\n\n");
printf("\t\t12.nrinorder\n\n");
printf("\t\t13.nrpostorder\n\n");
printf("\t\t0.exit\n\n");
printf("\n\n\n\tplease select:");
}
int Initiate(BiTree *bt,datatype x)
{
if((*bt=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)
return 0;
(*bt)->data=x;
(*bt)->lchild=NULL;
(*bt)->rchild=NULL;
return 1;
}
BiTree InsertL(BiTree bt,datatype x,BiTree parent)
{
BiTree p;
if(parent==NULL)
{
printf("\nerror!\n");
return NULL;
}
if((p=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)
return NULL;
p->data=x;
p->lchild=NULL;
p->rchild=NULL;
if(parent->lchild==NULL)
parent->lchild=p;
else
{
p->lchild=parent->lchild;
parent->lchild=p;
}
return bt;
}
BiTree InsertR(BiTree bt,datatype x,BiTree parent)
{
BiTree p;
if(parent==NULL)
{
printf("\nerror!\n");
return NULL;
}
if((p=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)
return NULL;
p->data=x;
p->lchild=NULL;
p->rchild=NULL;
if(parent->rchild==NULL)
parent->rchild=p;
else
{
p->rchild=parent->rchild;
parent->rchild=p;
}
return bt;
}
BiTree DeleteL(BiTree bt,BiTree parent)
{
BiTree p;
if(parent==NULL||parent->lchild==NULL)
{
printf("\ndelete error!");
return NULL;
}
p=parent->lchild;
parent->lchild=NULL;
free(p);
return bt;
}
BiTree DeleteR(BiTree bt,BiTree parent)
{
BiTree p;
if(parent==NULL||parent->rchild==NULL)
{
printf("\ndelete error!");
return NULL;
}
p=parent->rchild;
parent->rchild=NULL;
free(p);
return bt;
}
void PreOrder(BiTree bt)
{
if(bt==NULL)
return;
printf("%5d",bt->data);
PreOrder(bt->lchild);
PreOrder(bt->rchild);
}
void InOrder(BiTree bt)
{
if(bt==NULL)
return;
InOrder(bt->lchild);
printf("%5d",bt->data);
InOrder(bt->rchild);
}
void PostOrder(BiTree bt)
{
if(bt==NULL)
return;
PostOrder(bt->lchild);
PostOrder(bt->rchild);
printf("%5d",bt->data);
}
void LevelOrder(BiTree bt)
{
BiTree Queue[MAXNODE];
int front,rear;
if(bt==NULL)
{
return;
}
front = -1;
rear = 0;
Queue[rear] = bt;
while(front!=rear)
{
front++;
printf("%5d",Queue[front]->data);
if(Queue[front]->lchild!=NULL)
{
rear++;
Queue[rear]=Queue[front]->lchild;
}
if(Queue[front]->rchild!=NULL)
{
rear++;
Queue[rear]=Queue[front]->rchild;
}
}//end while
}
BiTree Find(BiTree parent,datatype a)
{
BiTree p;
if(parent==NULL)
p=NULL;
else if(parent->data==a)
p=parent;
else
{
p=Find(parent->lchild,a);
if(p==NULL)
p=Find(parent->rchild,a);
}
return p;
}
void NRPreOrder(BiTree bt)
{
BiTree stack[MAXNODE],p;
int top;
if(bt==NULL)
{
printf("Tree is empty!\n");
return;
}
top=-1;
p=bt;
while((p!=NULL)||(top!=-1))
{
while(p!=NULL)
{
printf("%5d",p->data);
if(top==MAXNODE-1)
{
printf("Stack overflow!\n");
return;
} /* end if */
else
{
top++;
stack[top]=p;
} /* end if-else */
p=p->lchild;
} /* end while p */
p=stack[top];
top--;
p=p->rchild;
} /* end while p && top */
}
void NRInOrder(BiTree bt)
{
BiTree stack[MAXNODE],p;
int top;
if(bt==NULL)
{
printf("Tree is empty!\n");
return;
}
top=-1;
p=bt;
while((p!=NULL)||(top!=-1))
{
while(p!=NULL)
{
if(top==MAXNODE-1)
{
printf("Stack overflow!\n");
return;
} /* end if */
else
{
top++;
stack[top]=p;
} /* end if-else */
p=p->lchild;
} /* end while p */
p=stack[top];
top--;
printf("%5d",p->data);
p=p->rchild;
} /* end while p && top */
}
void NRPostOrder(BiTree bt)
{
stacktype stack[MAXNODE];
BiTree p;
int top,sign;
if(bt==NULL)
{
printf("Tree is empty!\n");
return;
}
top=-1;
p=bt;
while((p!=NULL)||(top!=-1))
{
if(p!=NULL) /*結點第一次入棧*/
{
top++;
stack[top].link=p;
stack[top].flag=1; /*標記第一次入棧*/
p=p->lchild;
} /* end if */
else
{
p=stack[top].link;
sign=stack[top].flag;
top--;
if(sign==1) /*結點第二次入棧*/
{
top++;
stack[top].link=p;
stack[top].flag=2; /*標記第二次入棧*/
p=p->rchild;
} /* end if */
else
{
printf("%5d",p->data);
p=NULL;
} /* end if-else */
} /* end if-else */
} /* end while */
}