二叉樹c語言實現
⑴ 二叉樹怎樣用c語言實現
以下代碼可實現二叉樹的遞歸創建與中序遍歷,但在輸入時需在輸入完有效數據後再連續輸入多個負數才可以。
#include <stdio.h>
#include <stdlib.h>
typedef struct BitNode
{
int data;
struct BitNode *lchile,*rchild;
}*BiTree;
BiTree CreateBiTree(BiTree &T)
{
int d;
scanf("%d",&d);
if (d<0)
return NULL;
else
{
if (!(T=(BiTree)malloc(sizeof(BiTree))))
{
exit(1);
}
T->data=d;//先根序創建二叉樹
printf("%d ",T->data);
T->lchile=CreateBiTree(T->lchile);//創建左子樹
T->rchild=CreateBiTree(T->rchild);//創建右子樹
return T;
}
}
void InOrderView(BiTree &T)//中序遍歷二叉樹
{
if(T)
{
InOrderView(T->lchile);
printf("%d ",T->data);
InOrderView(T->rchild);
}
}
void main()
{
BiTree T;
T=CreateBiTree(T);//遞歸創建二叉樹
InOrderView(T);
}
⑵ C語言實現二叉樹存儲
//dev c++
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
typedef struct node
{
int data;//節點信息
int no;
struct node *lchild;//左孩子
struct node *rchild;//右孩子
}BTnode;
void Init(BTnode *&b)//初始化
{b=NULL;}
static int count=1;
int Insert(BTnode *&b,int m)//插入操作
{
BTnode *q;
if(count==1)
{b=(BTnode*)malloc(sizeof(BTnode));
b->data=m;
b->no=count;
b->lchild=b->rchild=NULL;
count++;
}
else if(b!=NULL)
{if(b->no!=count/2)
{
if(Insert(b->lchild,m)==0)return 0;
if(Insert(b->rchild,m)==0)return 0;
}
else
{
q=(BTnode*)malloc(sizeof(BTnode));
q->data=m;
q->no=count;
q->lchild=q->rchild=NULL;
if(count%2==0)b->lchild=q;
else b->rchild=q;
count++;
return 0;
}
}
}
static char s[1024][1024],a[1024];
static int n;
int output(BTnode *&b,int i)//層次輸出
{
if(n<i)n=i;
BTnode *p=b;
if(p!=NULL)
{
itoa(p->data,a,10);
strcpy(s[i],a);
output(p->lchild,2*i+1);
output(p->rchild,2*(i+1));
}
else strcpy(s[i],"N");
}
void xianxu(BTnode*&b)//先序
{
BTnode *p=b;
if(p!=NULL)
{
printf("%d ",p->data);
xianxu(p->lchild);
xianxu(p->rchild);
}
}
void zhongxu(BTnode *&b)//中序
{
BTnode *p=b;
if(p!=NULL)
{
zhongxu(p->lchild);
printf("%d ",p->data);
zhongxu(p->rchild);
}
}
void houxu(BTnode *&b)//後序
{
BTnode *p=b;
if(p!=NULL)
{
houxu(p->lchild);
houxu(p->rchild);
printf("%d ",p->data);
}
}
void menu()
{
BTnode *b;
Init(b);
int i,j,k,y,m;
while(1)
{
printf("*****************************************\n\n");
printf("*************二叉數功能菜單**************\n");
printf("*************1.插入整數 ************\n");
printf("*************2.層次輸出二叉樹************\n");
printf("*************3.先序遍歷 ************\n");
printf("*************4.中序遍歷 ************\n");
printf("*************5.後序遍歷 ************\n");
printf("*************6.退出 ************\n\n");
printf("*****************************************\n\n");
printf("請選擇:");
scanf("%d",&y);
switch(y)
{
case 1:printf("\n請輸入整數:");scanf("%d",&m);Insert(b,m);break;
case 2:i=0;output(b,i);printf("N代表空節點\n");
for(int j=0;j<=n;j++)
{
printf("%s ",s[j]);
for(k=1;(int)pow(2,k)-2<j;k++);
if((int)pow(2,k)-2==j)printf("\n");
}
break;
case 3:xianxu(b);break;
case 4:zhongxu(b);break;
case 5:houxu(b);break;
case 6:exit(0);break;
default:printf("\n輸入錯誤!");break;
}
printf("\n\n");
}
}
int main()
{
menu();
system("pause");
}
⑶ 二叉樹c語言實現
#include<iostream.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
char data;
struct node *lchild,*rchild;//
}BiTNode,*BiTree;
void CreatBiTree(BiTree &T)
{
char ch;
ch=getchar();
if (ch == ' ')
T = 0;
else {
T=(BiTNode*)malloc(sizeof(BiTNode));
T->data=ch;//生成根節點
CreatBiTree(T->lchild);//構造左子樹
CreatBiTree(T->rchild);//構造右子樹
}
}
void preorder(BiTree T)//前序遍歷
{
if (T!=NULL){
printf ("%c",T->data);
preorder(T->lchild);
preorder(T->rchild);
}
}
void inorder(BiTree T)//中序遍歷
{
if (T!=NULL){
inorder(T->lchild);
printf ("%c",T->data);
inorder(T->rchild);
}
}
void postorder(BiTree T)//後序遍歷
{
if (T!=NULL){
postorder(T->lchild);
postorder(T->rchild);
printf ("%c",T->data);
}
}
void main ()
{
cout<<"請輸入要創建的二叉樹包括空格:"<<endl ;
BiTree T;
CreatBiTree(T);//創建二叉樹
cout<<"前序遍歷的結果為:"<<endl;
preorder(T);
cout<<endl;
cout<<"中序遍歷的結果為:"<<endl;
inorder(T);
cout<<endl;
cout<<"後序遍歷的結果為:"<<endl;
postorder(T);
}
⑷ 用c語言寫二叉樹,源代碼。
二叉樹是採用遞歸定義的,實現起來代碼簡潔(也許並不簡單)。並且它在具體的計算機科學中有很重要的運用,是一種很重要的數據結構,二叉樹有三種遍歷和建立的方式。今天先學習一下它的建立和列印。
以下代碼在Win-Tc1.9.1下編譯通過。
#include <stdio.h>
#define ElemType char
//節點聲明,數據域、左孩子指針、右孩子指針
typedef struct BiTNode{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
//先序建立二叉樹
BiTree CreateBiTree(){
char ch;
BiTree T;
scanf("%c",&ch);
if(ch=='#')T=NULL;
else{
T = (BiTree)malloc(sizeof(BiTNode));
T->data = ch;
T->lchild = CreateBiTree();
T->rchild = CreateBiTree();
}
return T;//返回根節點
}
//先序遍歷二叉樹
void PreOrderTraverse(BiTree T){
if(T){
printf("%c",T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
//中序遍歷
void InOrderTraverse(BiTree T){
if(T){
PreOrderTraverse(T->lchild);
printf("%c",T->data);
PreOrderTraverse(T->rchild);
}
}
//後序遍歷
void PostOrderTraverse(BiTree T){
if(T){
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
printf("%c",T->data);
}
}
void main(){
BiTree T;
T = CreateBiTree();//建立
PreOrderTraverse(T);//輸出
getch();
}
⑸ 求數據結構 二叉樹的基本操作實現 c語言版
# include <stdio.h>
# include <malloc.h>
struct BTNode
{
int data;
struct BTNode * pLchild;//p是指針,L是左,child是孩子
struct BTNode * pRchild;
};
//函數聲明
struct BTNode * CreateBTree(void);//創建樹
void PreTraverseBTree(struct BTNode * pT);//先序遍歷
void InTraverseBTree(struct BTNode * pT);//中序遍歷
void PostTraverseBTree(struct BTNode * pT);//後續遍歷
int main(void)
{
struct BTNode * pT = CreateBTree();
PreTraverseBTree(pT);
printf("\n");
InTraverseBTree(pT);
printf("\n");
PostTraverseBTree(pT);
return 0;
}
//創建樹
struct BTNode * CreateBTree(void)
{
struct BTNode * pA = (struct BTNode * )malloc(sizeof(BTNode));
struct BTNode * pB = (struct BTNode * )malloc(sizeof(BTNode));
struct BTNode * pC = (struct BTNode * )malloc(sizeof(BTNode));
struct BTNode * pD = (struct BTNode * )malloc(sizeof(BTNode));
struct BTNode * pE = (struct BTNode * )malloc(sizeof(BTNode));
pA->data = 'A';
pB->data = 'B';
pC->data = 'C';
pD->data = 'D';
pE->data = 'E';
pA->pLchild = pB;
pA->pRchild = pC;
pB->pLchild = NULL;
pB->pRchild = NULL;
pC->pLchild = pD;
pC->pRchild = NULL;
pD->pLchild = NULL;
pD->pRchild = pE;
pE->pLchild = NULL;
pE->pRchild = NULL;
return pA;
}
//先序遍歷
void PreTraverseBTree(struct BTNode * pT)
{ //先訪問根節點,再先序訪問左子樹,最後先序訪問右子樹
if ( pT != NULL)
{
printf("%c\n",pT->data);//訪問根節點
//pT->pLchild可以代表整個左子樹
PreTraverseBTree(pT->pLchild);
PreTraverseBTree(pT->pRchild);
}
return;
}
//中序遍歷
void InTraverseBTree(struct BTNode * pT)
{
if(pT != NULL )
{
if (NULL != pT->pLchild)
{
InTraverseBTree(pT->pLchild);
}
printf("%c\n",pT->data);
if (NULL != pT->pRchild)
{
InTraverseBTree(pT->pRchild);
}
}
return;
}
//後續遍歷
void PostTraverseBTree(struct BTNode * pT)
{
if(pT != NULL )
{
if (NULL != pT->pLchild)
{
PostTraverseBTree(pT->pLchild);
}
if (NULL != pT->pRchild)
{
PostTraverseBTree(pT->pRchild);
}
printf("%c\n",pT->data);
}
return;
}
⑹ 二叉樹C語言演算法,急!!!!
清華大學
嚴蔚敏
的<數據結構里>都有完整的代碼,解釋的也很清楚
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
typedef
struct
tree
{
struct
tree
*left;
int
date;
struct
tree
*right;
}treenode,*b_tree;
///////插入節點/////////////////////
b_tree
insert(b_tree
root,int
node)
{
b_tree
newnode;
b_tree
currentnode;
b_tree
parentnode;
newnode=(b_tree)malloc(sizeof(treenode));
newnode->date=node;
newnode->right=NULL;
newnode->left=NULL;
if(root==NULL)
return
newnode;
else
{
currentnode=root;
while(currentnode!=NULL)
{
parentnode=currentnode;
if(currentnode->date>node)
currentnode=currentnode->left;
else
currentnode=currentnode->right;
}
if(parentnode->date>node)
parentnode->left=newnode;
else
parentnode->right=newnode;
}
return
root;
}
//////建立樹///////////////////
b_tree
creat(int
*date,int
len)
{
b_tree
root=NULL;
int
i;
for(i=0;i<len;i++)
root=insert(root,date[i]);
return
root;
}
//////中序列印////////////////
void
print1(b_tree
root)
{if(root!=NULL)
{
print1(root->left);
printf("%d->",root->date);
print1(root->right);
}
}
//////後序列印////////////////
void
print2(b_tree
root)
{if(root!=NULL)
{
print2(root->left);
print2(root->right);
printf("%d->",root->date);
}
}
//////前序列印////////////////
void
print3(b_tree
root)
{if(root!=NULL)
{
printf("%d->",root->date);
print3(root->left);
print3(root->right);
}
}
//////////在二叉樹中查找給定關鍵字
////////////
b_tree
lookfor(b_tree
root,int
e)
{
b_tree
p1,p2;
if(root!=NULL)
{
if(root->date==e)
return
root;
else
p1=lookfor(root->left,e);
p2=lookfor(root->right,e);
if(p1!=NULL)
return
p1;
else
if(p2!=NULL)
return
p2;
else
return
NULL;
}
else
return
NULL;
}
///////測試函數//////////////////
void
main()
{
b_tree
root=NULL;
int
i,index;
int
value;
int
nodelist[20];
cout<<"輸入樹的節點,輸入0結束\n";
index=0;
cin>>value;
while(value!=0)
{
nodelist[index]=value;
index=index+1;
cin>>value;
}
root=creat(nodelist,index);
printf("\n中序列印\n");
print1(root);
printf("\n後序列印\n");
print2(root);
printf("\n前序列印\n");
print3(root);
printf("\n查找的詞:\n");
int
a;
scanf("%d",&a);
b_tree
p3=lookfor(root,a);
if(p3!=NULL)
printf("%d\n",p3->date);
else
printf("沒你要找的詞");
}
⑺ 求二叉樹遍歷演算法C語言實現的
Status
PreOrderTraverse
(
BiTree
T,
Status
(
*Visit
)
(
TElemType
e
)
)
{
//
採用二叉鏈表存儲結構,Visit
是對數據元素操作的應用函數,先序遍歷二叉樹
T
的遞歸演算法。
if
(
T
)
{
//
若
T
不為空
if
(
Visit
(
T->data
)
)
//
調用函數
Visit
if
(
PreOrderTraverse
(
T->lchild,
Visit
)
)
//
遞歸調用左子樹
if
(
PreOrderTraverse
(
T->rchild,
Visit
)
)
return
OK;
//
遞歸調用右子樹
return
ERROR;
}
else
return
OK;
}
//
PreOrderTraverse
⑻ 二叉樹遍歷(c語言實現)
#include <stdio.h>
#include <malloc.h>
typedef struct node{
int data;
struct node *lchild,*rchild;
}*treetp,tree;
treetp create (treetp t,int c);
void print1(treetp);
void print2(treetp);
void print3(treetp);
int number=0;
void main()
{
treetp t=0,r;
r=create (t,0);
printf("前序排列 :");
print1 (r);
printf("\n中序排列 :");
print2 (r);
printf("\n後序排列 :");
print3 (r);
}
treetp create(treetp t,int c)
{
treetp p,di;
do{
scanf("%d",&c);
if (t==0)
{
t=(treetp)malloc(sizeof(tree));
t->lchild=t->rchild=0;
t->data=c;
}
else
{ p=t;
while(p!=0)
{
di=p;
if(c<(p->data))
p=p->lchild;
else
p=p->rchild;
}
if(c<(di->data))
{
treetp NEWdi=(treetp) malloc(sizeof(tree));
NEWdi->lchild=NEWdi->rchild=0;
NEWdi->data=c;
di->lchild=NEWdi;
}
else
{
treetp NEWdi=(treetp) malloc(sizeof(tree));
NEWdi->lchild=NEWdi->rchild=0;
NEWdi->data=c;
di->rchild=NEWdi;
}
}
++number;
}while(c!=0);
printf("葉子的數量:%d",number);
return t;
}
void print1(treetp t)
{
if (t!=0)
{
printf("%d ",t->data);
print1(t->lchild);
print1(t->rchild);
}
}
void print2(treetp t)
{
if (t!=0)
{
print2(t->lchild);
printf("%d ",t->data);
print2(t->rchild);
}
}
void print3(treetp t)
{
if (t!=0)
{
print3(t->lchild);
print3(t->rchild);
printf("%d ",t->data);
}
}
希望對你有幫助
⑼ 用c語言實現二叉樹的程序,可以輸入輸出和遍歷
#include <stdio.h>
#include <stdlib.h>
#include <iostream.h>
const int MaxLength=10;//結點個數不超過10個
typedef struct tree
{
char data;
struct tree *lchild,*rchild;
}tree;
//先序遞歸 建立二叉樹
void Createbitree(tree* &T)
{
char ch;
ch=getchar();
if(ch=='#')
T=NULL;
else
{
T=(tree*)malloc(sizeof(tree));
T->data =ch;
Createbitree(T->lchild );
Createbitree(T->rchild );
}
}
//先序遞歸遍歷
void PreOrderTraverse(tree* T)
{
if(T)
{
cout<<T->data;
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
//中序遞歸遍歷
void InOrderTraverse(tree* T)
{
if(T)
{
InOrderTraverse(T->lchild);
cout<<T->data;
InOrderTraverse(T->rchild);
}
}
void PostOrderTraverse(tree* T)
{
if(T)
{
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
cout<<T->data;
}
}
//層序遍歷
void LevelOrderTraverse(tree* T)
{
tree* Q[MaxLength];
int front=0,rear=0;
tree* p;
if(T)//根結點入隊
{
Q[rear]=T;
rear=(rear+1)%MaxLength;
}
while(front!=rear)
{
p=Q[front]; //隊頭元素出隊
front=(front+1)%MaxLength;
cout<<p->data;
if(p->lchild)//左孩子不為空,入隊
{
Q[rear]=p->lchild;
rear=(rear+1)%MaxLength;
}
if(p->rchild)//右孩子不為空,入隊
{
Q[rear]=p->rchild;
rear=(rear+1)%MaxLength;
}
}
}
//主函數
void main()
{
cout<<"請按先序次序輸入二叉樹的數據:"<<endl;
tree* T;
Createbitree(T);
cout<<"二叉樹的先序序列為:"<<endl;
PreOrderTraverse(T);
cout<<endl<<"二叉樹的中序序列為:"<<endl;
InOrderTraverse(T);
cout<<endl<<"二叉樹的後序序列為:"<<endl;
PostOrderTraverse(T);
cout<<endl<<"二叉樹的層序序列為:"<<endl;
LevelOrderTraverse(T);
cout<<endl;
}
比如 1
2 3
4 5 6 7
按先序輸入是124##5##36##7##
⑽ 用c語言編程實現二叉樹的建立和遍歷二叉樹
//這是我上數據結構寫的 建議理解為主
#include<stdio.h>
#include<stdlib.h>
#define ERROR 0
#define OK 1
#define OVERFLOW -2
#define FLASE 0
#define TURE 1
typedef int Status;
typedef char TElemType;
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild;//左右孩子指針
}BiTNode,*BiTree;
//構造一個二叉樹
Status CreateBiTree(BiTree &T){
TElemType str[]="ABC$$D$EF$$G$$$";
static int i=0;
TElemType ch;
ch=str[i++];
if(ch=='$')
T=NULL;
else{
//創建樹結點
T=(BiTNode*)malloc(sizeof(BiTNode));
if(!T) exit(OVERFLOW);
T->data=ch;
//創建左子樹
CreateBiTree(T->lchild);
//創建右子樹
CreateBiTree(T->rchild);
}
return OK;
}
//輸出元素data
Status PrntTElem(TElemType data){
putchar(data);
return OK;
}
//先序遍歷二叉樹
Status PreOrderTraverse(BiTree T,Status(*visit)(TElemType e)){
if(T){
if((*visit)(T->data))
if(PreOrderTraverse(T->lchild,visit))
if(PreOrderTraverse(T->rchild,visit))
return OK;
return ERROR;
}
else return OK;
}
//中序遍歷二叉樹
Status InOrderTraverse(BiTree T,Status(*visit)(TElemType e)){
if(T){
if(InOrderTraverse(T->lchild,visit))
if(visit(T->data))
if(InOrderTraverse(T->rchild,visit))
return OK;
return ERROR;
}
else return OK;
}
//後序遍歷二叉樹
Status PostOrderTraverse(BiTree T,Status(*visit)(TElemType e)){
if(T){
if(PostOrderTraverse(T->lchild,visit))
if(PostOrderTraverse(T->rchild,visit))
if(visit(T->data))
return OK;
return ERROR;
}
else return OK;
}
//求二叉樹深度
int BiTreeDepth(BiTree T){
int ldep=0,rdep=0;
if(T==NULL)
return 0;
ldep=BiTreeDepth(T->lchild);
rdep=BiTreeDepth(T->rchild);
if(ldep>=rdep)
return ldep+1;
else
return rdep+1;
}
//求葉子數
int BiTreeLeaves(BiTree T){
if(!T)
return 0;
else if(!T->lchild&&!T->rchild)
return 1;
else
return BiTreeLeaves(T->lchild)+BiTreeLeaves(T->rchild);
}
//銷毀
int DestroyBiTree(BiTree &T){
if(T){
if(DestroyBiTree(T->lchild))
if(DestroyBiTree(T->rchild))
T=NULL;
}
return OK;
}
void main()
{
BiTree T;
CreateBiTree(T);
printf("先序結果為:");
PreOrderTraverse(T,PrntTElem);
printf("\n中序結果為:");
InOrderTraverse(T,PrntTElem);
printf("\n後序結果為:");
PostOrderTraverse(T,PrntTElem);
printf("\n二叉樹的深度為: %d\n",BiTreeDepth(T));
printf("葉子數為: %d\n",BiTreeLeaves(T));
DestroyBiTree(T);
printf("先序結果為:");
PreOrderTraverse(T,PrntTElem);
printf("\n中序結果為:");
InOrderTraverse(T,PrntTElem);
printf("\n後序結果為:");
PostOrderTraverse(T,PrntTElem);
printf("\n");
}