c語言多叉樹
① 如何用c語言建立一棵N層的完全二叉樹，要求除根結點，其餘的結束左結點值為0，右結點值為1。求完全代碼!
存儲結構
typedef struct {
int weight;
int parent, lchild, rchild;
} HTNode ,*HuffmanTree; // 動態分配數組存儲huffman樹
演算法設計
void createHuffmantree(){
ht=(HuffmanTree)malloc(m+1)*sizeof(HTNode);// 動態分配數組存儲huffman樹,0號單元未用
// m:huffman 樹中的結點數（m=2*n-1）
for (i=1;i<=m;++i)
ht[i].parent= ht[i]->lch= ht[i]->rch=0;
for (i=1;i<=n;++i)
ht[i].weight=w[i]; //初始化，w[i]：n個葉子的權值
for (i=n+1;i<=m,++i) ｛ //建哈夫曼樹
select(i-1),s1,s2); //在ht[k](1<=k<=i-1)中選擇兩個雙親域為零而權值取最小的結點 :s1和s2
ht[s1].parent= ht[s2].parent=i;
ht[i].lch=s1;
ht[i].rch=s2;
ht[i].weight=ht[s1].weight + ht[s2].weight ;
};
}
② C語言鏈表問題
由0到多個節點以節點指針連接起來的數據結構，稱為鏈表，
鏈表結點通常是結構體(或類)，至少含有一個指向本結構體類型的指針
只含指向子節點不含指向父節點的鏈表為單向鏈表，只有從父向子遍歷，
當節點同時含有指向父節點的指針時，就是雙向鏈表，可以父到子的遍歷也可以從子到父的遍歷
指向子節點的指針只有一個時，就是單鏈表，遍歷最為簡單
有兩個時為二叉樹，兩個以上的是多叉樹，遍歷就有點復雜
增加節點，就是把新的節點添加到鏈表中，使其成為鏈的一分子
刪除節點就是把一個在鏈表中的節移除，使鏈表遍歷時不會訪問到這個被刪除的元素
下面程序有演示添加和刪除操作:
//本來是回復另一個問題未沒能完整帖上程序，這里竟然可以發個完整版就做學習參考的例子吧
//要求用鏈表
//給出兩個整數數列，先要將其合並為一個數列，並且合並後整個數列有序(從小到大)
#include<stdio.h>
typedef struct node{node* next;int data;} Node;
void Sort_Select(Node**phead) //簡單排序之選擇法(因為鏈表結構,想簡單冒泡都不成咧)
{
Node *pSelect,*pSelectPre,*p1,*p2,*p2_pre,*newHead,*newEnd;
newHead = newEnd =NULL;
for(p1=*phead; p1; )
{
for(pSelectPre=NULL,pSelect=p2_pre=p1,p2=p1->next; p2; p2_pre=p2,p2=p2->next) //選擇最小元素
if(pSelect->data > p2->data)
{
pSelect = p2;
pSelectPre = p2_pre;//單鏈表，不能直接訪問當前結點的父結點，只好用兩指針跟蹤了
}
//從舊鏈刪除pSelect
if(!pSelectPre) //刪頭結點
p1 = p1->next;
else
pSelectPre->next = pSelect->next;
//追加到新鏈表尾部
if(!newEnd)//第一次
{
newEnd = newHead = pSelect;
newEnd->next = NULL;
}
else
{
newEnd->next = pSelect;
newEnd = pSelect;
newEnd->next = NULL;
}
}
*phead = newHead;
}
void main()
{
int iN,iM,i,j;
Node *headN=NULL, *headM=NULL, *endN=NULL, *endM=NULL,*Ntmp;
do{
printf("輸入第一數列大小(1-5000):");
scanf("%d",&iN);
if(iN>5000||iN<1) printf("輸入不合法，請重試\n");
}while(iN>5000||iN<1);
printf("輸入第一數列的%d個整數:\n",iN);
for(i=0;i<iN;i++)
{
scanf("%d",&j);
Ntmp = (Node*)malloc(sizeof(Node));
Ntmp->data = j;
Ntmp->next = NULL;
if(!headN)
{
endN = headN = Ntmp;//<<<第一個結點
}
else
{
endN->next = Ntmp; endN = Ntmp;//<<<直接添在尾(未排序)
}
}
do{
printf("輸入第二數列大小(1-5000):");
scanf("%d",&iM);
if(iM>5000||iM<1) printf("輸入不合法，請重試\n");
}while(iM>5000||iM<1);
printf("輸入第二數列的%d個整數:\n",iM);
for(i=0;i<iM;i++)
{
scanf("%d",&j);
Ntmp = (Node*)malloc(sizeof(Node));
Ntmp->data = j;
Ntmp->next = NULL;
if(!headM)
{
endM = headM = Ntmp;
}
else
{
endM->next = Ntmp; endM = Ntmp;
}
}
endN->next = headM; //<<<合並到連表headN 就是這么簡單
//endN = endM; headM=endM=NULL; //<<<完成使命了不再需要也不必理它們
Sort_Select(&headN);//鏈表排序
printf("\n合並排序的結果:\n");
for(Ntmp=headN; Ntmp; Ntmp=Ntmp->next) printf("%d ",Ntmp->data); //<<<遍歷鏈表
//釋放內存 //程序就要退出系統，下面的內存釋放已不是必需，系統能回收這些內存 不過為了好習慣
while(headN)
{
Ntmp = headN;
headN = headN->next;
free(Ntmp);
}
printf("\n"); system("pause");//窗口可能會關，稍等方便查看結果
}
③ 跪求關於c語言多叉樹添加節點的問題
數據結構:
struct list
{
/* other data */
int effectif_class_1;
int effectif_class_2;
struct list *parent;
struct list *child[];
}
struct list * findNode(struct list *point)
{
int i;
if(point->data == data)
return point;
i=0;
while(point->child[i] != NULL){
if( (findNode(point->child[i])) == point->child[i])
return point->child[i];
i++;
}
return NULL;
}
void addNode_changeNoeud(struct list *point)
{
int i=0;
while(point->child[i] != NULL)
{
point->child[i]->Noeud ++;
addNode_changeNoeud(point->child[i]);
i++;
}
}
void addNode(struct list *point, /* data */)
{ //在point的最右端插入一個子節點
int i=0;
/* 定位到最右端 */
while(point->child[i] != NULL){
i++;
}
point->child[i] = (struct list *)malloc(sizeof(struct list));
/* 保存其他數據到 point->child[i]->data */
/* 更改所有父節點的 effectif_class */
struct list *tmp;
tmp = point->parent;
while(tmp != NULL){
tmp->effectif_class_1 = tmp->effectif_class_1 + /* effectif_class_1 */ ;
tmp->effectif_class_2 = tmp->effectif_class_2 + /* effectif_class_2 */ ;
tmp = tmp->parent;
}
/* 插入節點後,更新編號 */
point->child[i] = point->child[i-1] + 1;
addNode_changeNoeud(point); /* 這個不好說,用於更新編號Noeud的,自己理解吧... */
}
④ C語言數字拼圖最少步數解法
可以參考樓天成在網路之星中的程序。他用了A*演算法，速度較快，但這個演算法學習難度稍大，簡單的可以用深度優先搜索，稍微進一步可以用雙向深度優先搜索 + 散列的存儲方法。當然還有其他的演算法。這幾種比較常見
⑤ 數據結構 c語言版二叉樹(1) 建立一棵含有n個結點的二叉樹，採用二叉鏈表存儲；
#include<stdio.h>
#include<stdlib.h>
typedef struct node *tree_pointer;
struct node{
char ch;
tree_pointer left_child,right_child;
};
tree_pointer root=NULL;
tree_pointer create(tree_pointer ptr)
{
char ch;
scanf("%c",&ch);
if(ch==' ')
ptr=NULL;
else{
ptr=(tree_pointer)malloc(sizeof(node));
ptr->ch=ch;
ptr->left_child=create(ptr->left_child);
ptr->right_child=create(ptr->right_child);
}
return ptr;
}
void preorder(tree_pointer ptr)
{
if(ptr){
printf("%c",ptr->ch);
preorder(ptr->left_child);
preorder(ptr->right_child);
}
}
void inorder(tree_pointer ptr)
{
if(ptr){
inorder(ptr->left_child);
printf("%c",ptr->ch);
inorder(ptr->right_child);
}
}
void postorder(tree_pointer ptr)
{
if(ptr){
postorder(ptr->left_child);
postorder(ptr->right_child);
printf("%c",ptr->ch);
}
}
void main()
{
printf("構建一個二叉樹（結點數為n)：\n");
root=create(root);
printf("前序遍歷二叉樹：\n");
preorder(root);
printf("\n");
printf("中序遍歷二叉樹：\n");
inorder(root);
printf("\n");
printf("後序遍歷二叉樹：\n");
postorder(root);
printf("\n");
}
⑥ 用C語言建立一棵含有n個結點的二叉樹，採用二叉鏈表存儲，然後分別實現前序，中序，後序遍歷該二叉樹
#include <stdio.h>
#include <stdlib.h>
#define max 100
typedef struct node{ //二叉樹結構
char data;
struct node *lc,*rc; //左右子樹
}bt,*list;
/*
二叉樹
A
/ \
B C
/ \ \
D E F
/ / \
K G H
input
ABDK000E00C0FG00H00
ouput
ABDKECFGH
KDBEACGFH
KDEBGHFCA
*/
int creat(list*root){ //創建一棵二叉樹，root使用的是二維指針
char n;
scanf(" %c",&n); //注%C前面加空格是為了起間隔作用 scanf不讀入空格
if (n=='0') //0為間隔
{
*root=NULL; return 0; //輸入結束
}
*root=(list)malloc(sizeof(bt));
if (!*root) return 0;
(*root)->data=n;
creat(&(*root)->lc);
creat(&(*root)->rc);
return 1;
}
int pre(list root){ //先序遍歷
if (!root) return 0;
printf("%c",root->data);
pre(root->lc);
pre(root->rc);
return 1;
}
int mid(list root){ //中序遍歷
if (!root) return 0;
mid(root->lc);
printf("%c",root->data);
mid(root->rc);
return 1;
}
int bh(list root){ //後序遍歷
if (!root) return 0;
bh(root->lc);
bh(root->rc);
printf("%c",root->data);
return 1;
}
int sum(list root,int *cnt){ //求結點的個數sum
if(root){
(*cnt)++;
sum(root->lc,cnt);
sum(root->rc,cnt);
return 1;
}
return 0;
}
int sumleaf(list root,int *cnt){ //求葉子節點的個數
if (root)
{
if ((!root->lc)&&(!root->rc))
{ (*cnt)++; }
sumleaf(root->lc,cnt);
sumleaf(root->rc,cnt);
return 1;
}
return 0;
}
int deep(list root,int *cnt){ //求深度
if (!root)
{
*cnt=0; return 0;
}
int m,n;
n=m=*cnt;
deep(root->lc,&m);
deep(root->rc,&n);
*cnt=m+1;
if(m<n) *cnt=n+1;
return 1;
}
int floor(list root){ //層次遍歷
if(root)
{
list s[max]; int front,rear; //用隊進行存儲
front=-1; rear=0; s[rear]=root; //初始化
while (rear!=front) //當隊為空時結束
{
printf("%c",s[++front]->data);
if (s[rear]->lc)
{s[1+rear]=s[rear]->lc; rear++; } //將左子樹存入隊列中
if (s[rear]->rc)
{s[1+rear]=s[rear]->rc; rear++; } //將右子書存入隊列中
}
return 1;
}
return 0;
}
int scop(list *r,list *p){ //樹的復制
if(*r){
*p=(list)malloc(sizeof(bt));
if(*p){
(*p)->data=(*r)->data;
scop(&(*r)->lc,&(*p)->lc);
scop(&(*r)->rc,&(*p)->rc);
return 1;
}
}
*p=NULL;
return 0;
}
int sepect(list root,list *p,char e){ //查找節點返回指針*p p為二級指針
if(root){
if (root->data==e)
{ *p=root; return 1;
}
sepect(root->lc,p,e);
sepect(root->rc,p,e);
}
return 0;
}
void main(){
list b,s,m;
int n,t=1;
char ch='\0';
printf("***********Bitree************\n");
while(t){ //循環操作
printf("input a tree(int):\n");
s=m=b=NULL; //二叉樹的初始化
creat(&b);
//按三種遍歷輸出二叉樹
printf("\npre "); pre(b);
printf("\nmid "); mid(b);
printf("\nbh "); bh(b); printf("\n");
//求節點數目，葉子節點的個數，深度
n=0; sum(b,&n); printf("sumdata: %d\n",n);
n=0; sumleaf(b,&n); printf("sumleaf: %d\n",n);
n=0; deep(b,&n); printf("deep: %d\n",n);
//二叉樹的復制
scop(&b,&s);
printf("\ns tree:\npre ");
pre(s); printf("\nmid ");
mid(s); printf("\nbh ");
bh(s); printf("\n");
//查找節點
printf("sepect a data:\n");
scanf(" %c",&ch); //注%C前面加空格是為了起間隔作用 scanf不讀入空格
sepect(b,&m,ch);
if(m)
printf("sepect : %c \n",m->data);
else
printf("Error,no this data: %c\n",ch);
//繼續則輸入 1，退出輸入 0
printf("continue input 1,break input 0:\n");
scanf("%d",&t);
}
}
⑦ 完整正確的C語言二叉樹程序
我有現成的，分享給大家了。
#include<stdio.h>
#include<stdlib.h>
#define maxsize 100
typedef struct btnode
{
int data ; //結點數據類型
struct btnode *lchild, *rchild; //定義左、右孩子為指針型
} bitree;
bitree *creat(bitree *t) //創建二叉樹
{
bitree *s,*p,*q;
int x;
scanf("%d",&x);
while(x!=0)
{
s= ( bitree *)malloc(sizeof(bitree));
s->data=x;
s->lchild=s->rchild=NULL;
if(t==NULL)
t=s;
else
{
p=t;
while(p)
{
q=p;
if(s->data<p->data)
p=p->lchild;
else
p=p->rchild;
}
if(s->data<q->data)
q->lchild=s;
else
q->rchild=s;
}
scanf("%d",&x);
}
return(t);
}
bitree *insert(bitree *t) //插入結點
{
bitree *s,*p,*q;
int x;
scanf("%d",&x);
while(x!=0)
{
s= ( bitree *)malloc(sizeof(bitree));
s->data=x;
s->lchild=s->rchild=NULL;
if(t==NULL)
t=s;
else
{
p=t;
while(p)
{
q=p;
if(s->data<p->data)
p=p->lchild;
else
p=p->rchild;
}
if(s->data<q->data)
q->lchild=s;
else
q->rchild=s;
}
scanf("%d",&x);
}
return(t);
}
void search(bitree *t,int k) //查找數據
{
int flag=0;
while(t!=NULL)
{
if(t->data==k)
{
printf("已查到要找的數!\n");
flag=1;
break;
}
else
if(t->data<k)
t=t->rchild;
else
t=t->lchild;
}
if(flag!=1)
printf("沒有找到要查找的數據!\n");
}
bitree *dele(bitree *t,int k) //刪除數據
{
int flag;
bitree *p,*q,*s=NULL,*f;
f=t;
while(t!=NULL) //查找數據
{
if(t->data==k)
{
printf("已找到所查找的數!\n");
break;
}
else
if(t->data<k)
{
p=t;
t=t->rchild;
flag=0;
}
else
{
p=t;
t=t->lchild;
flag=1;
}
}
if(t->lchild==NULL&&t->rchild==NULL) //刪除葉子結點
{
free(t);
if(flag==0)
p->rchild=NULL;
else
p->lchild=NULL;
}
else
{
if(t->lchild==NULL&&t->rchild!=NULL) //刪除只有右子樹的結點
{
if(flag==0)
p->rchild=t->rchild;
else
p->lchild=t->rchild;
free(t);
}
else
{
if(t->lchild!=NULL&&t->rchild==NULL) //刪除只有左子樹的結點
{
if(flag==0)
p->rchild=t->lchild;
else
p->lchild=t->lchild;
free(t);
}
else //刪除左右子樹都有的結點
{
p=t;
t=t->lchild;
q=t;
while(t->rchild)
{
q=t;
t=t->rchild;
}
if(t==q)
{
p->data=t->data;
p->lchild=t->lchild;
free(t);
}
else
{
p->data=t->data;
q->rchild=t->lchild;
free(t);
}
}
}
}
return(f);
}
void output(bitree * t) //實現二叉樹的遍歷
{
bitree *q[maxsize],*p;
int f,r;
q[0]=t;
f=r=0;
while (f<=r)
{
p=q[f];
f++;
printf("%d ",p->data);
if(p ->lchild!=NULL)
{
r++;
q[r]=p->lchild;
}
if (p->rchild!=NULL)
{
r++;
q[r]=p->rchild;
}
}
}
void main()
{
bitree *q=NULL,*r;
int m,n,x=1;
while(x==1)
{
system("cls");
printf(" ********************************\n");
printf(" 創建請按1\n");
printf(" 插入請按2\n");
printf(" 查找請按3\n");
printf(" 刪除請按4\n");
printf(" 顯示請按5\n");
printf(" 退出請按0\n");
printf(" ********************************\n");
scanf("%d",&m);
switch(m)
{
case 1:printf("請輸入數據並以'0'結束\n");
r=creat(q);system("pause");break;
case 2:printf("請輸入數據並以'0'結束\n");
r=insert(r);break;
case 3:printf("請輸入要查找的數:");
scanf("%d",&n);
search(r,n);
system("pause");
break;
case 4:printf("請輸入要刪除的數:");
scanf("%d",&n);
r=dele(r,n);
printf("已刪除輸入數據!\n");
system("pause");
break;
case 5:output(r);system("pause");printf("\n");
break;
case 0:x=0;break;
}
}
}
⑧ C語言的家譜圖。。想求一個運用結構鏈表的源程序
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<string.h>
#define OK 1
#define ERROR -1
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef int Status;
struct BiNode{
//用結構體定義結點類型。
//數據域信息包含家譜中該對的男、女名字，其雙親名字，以及這對夫婦位於家譜中的輩分
//指針域指向他們的第一個孩子以及其他兄弟
char man[10],woman[10],father[10],mother[10];
int level;
struct BiNode *firstchild,*nextsibling;
};
struct SqStack{
//對棧類型進行定義
BiNode *base;
BiNode *top;
int stacksize;
};
//函數聲明
Status InitStack (SqStack &S);
Status Push (SqStack &S,BiNode e);
Status CreateBiTree(BiNode *s);
Status Pop(SqStack &S,BiNode e);
Status EmptyStack(SqStack &S);
Status Preorder(BiNode *T,char name[10],BiNode *p);
//Status CreateParent(BiNode *s);
void findchildren(BiNode *p);
void putoutchildren(BiNode *q,int n);
void findparents(BiNode *p);
void levelhome(BiNode *T);
void leveling(SqStack S1,SqStack S2,int n);
void print(BiNode *p);
//主函數
void main()
{
BiNode *home=NULL,*p=NULL;
char name[10];
printf("請按先序遍歷的順序根據提示輸入家譜信息，不存在則輸入「#」\n");
CreateBiTree(home);
printf("層次化的家譜信息為\n");
levelhome(home);
printf("請輸入要查找的人的名字");
gets(name);
Preorder(home,name,p);
if(!p)printf("家譜中無此人");
else{
printf("輩分：%d\n",p->level);
printf("孩子信息");
findchildren(p);
printf("父母信息：");
findparents(p);
}
}
//函數定義
Status InitStack (SqStack &S){
//初始化函數
S.base=(BiNode*)malloc(STACK_INIT_SIZE * sizeof(BiNode));
if(!S.base) return ERROR;
S.top=S.base;
S.stacksize =STACK_INIT_SIZE;
return OK;
}
Status Push (SqStack &S,BiNode e){
//將e結點推入棧，作為棧頂元素
if(S.top-S.base >=S.stacksize ){
S.base=(BiNode *)realloc(S.base ,(S.stacksize +STACKINCREMENT)*sizeof(BiNode));
if(!S.base ) return ERROR;
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return OK;
}
Status Pop(SqStack &S,BiNode e){
//取出棧頂元素
if(S.base==S.top) return ERROR;
e=*--S.top;
return OK;
}
Status EmptyStack(SqStack &S){
//若棧空，則返回0
return (S.top == NULL);
}
Status CreateBiTree(BiNode *root){
//創建家譜二叉樹
char man1[10],woman1[10],father[10],mother[10];
printf("man:");//男方名字，不存在則輸入「#」
gets(man1);
printf("woman:");//女方名字，不存在則輸入「#」
gets(man1);
if(strcmp(man1,"#")==0&&strcmp(woman1,"#")==0)//若該結點男女都不存在，則說明該結點為空，即該子樹的根結點不存在
{
root=NULL;
}
else{
root=(BiNode *)malloc(sizeof(BiNode));
strcpy(root->man,man1); //將男女的名字賦給該結點的數據域
strcpy(root->woman,woman1);
printf("father:"); //輸入該結點的雙親名字
gets(father);
printf("mother:");
gets(mother);
CreateBiTree(root->firstchild); //遞歸創建該結點的左、右子樹
CreateBiTree(root->nextsibling);
root->level=0;//將改結點的層數暫時定義為0
}
return OK;
}
Status Preorder(BiNode *T,char name[10],BiNode *p){
//先序遍歷家譜樹，查找與name名字相同的結點位置
if(T){
if(strcmp(T->man,name)==0||strcmp(T->woman,name)==0){
p=T;
return OK;
}
else{
if(Preorder(T->firstchild,name,p))return OK;
else return(Preorder(T->nextsibling,name,p));
}
}
else return ERROR;
}
void findchildren(BiNode *p){
//查找所得名字的孩子信息，輸出他們的名字，若無孩子，則輸出無孩子
int n=1;
BiNode *q;
if(p->firstchild){//該結點的firstchild指針指向的為他的第一個孩子
q=p->firstchild;
putoutchildren(q,n);//輸出
}
while(q->nextsibling){
//第一個孩子的nextsibling指針指向的為孩子的兄弟，即第二個孩子
//如此繼續，知道結點的右指針為空
q=q->nextsibling;
putoutchildren(q,n);//輸出
}
if(n==1)printf("無孩子");
}
void putoutchildren(BiNode *q,int n){
//輸出其孩子的結點的信息，並把孩子數加一
printf("第%d個孩子,男方名字%s,女方名字%s\n",n++,q->man,q->woman);
}
void findparents(BiNode *s){
//查詢該結點的雙親名字
if(s->father=="#"&&s->mother=="#")
printf("沒有父母信息");
else{
if((s->father)!="#")printf("father:%s\n",s->father);
if((s->mother)!="#")printf("mother:%s\n",s->mother);
}
}
void levelhome(BiNode *T){
//按層輸出該家譜
SqStack S,N; //定義兩個棧並初始化
InitStack(S);
InitStack(N);
BiNode *p;
p=T;
int n=1;
printf("第%d層的信息為:\n");
if(p){
print(p);
p->level=n;//修改p所指向的結點的輩分信息
Push(S,*p);//將該結點推進棧S
}
while(p=p->nextsibling){
//用循環來查找該層的所有信息，只要其nextsibling指向的結點不空，均為同一層
print(p);
p->level=n;
Push(S,*p);
}
while(!EmptyStack(S)||!EmptyStack(N)){
//循環，知道棧S和N都為空，說明按輩分遍歷完成
leveling(S,N,n++);
leveling(N,S,n++);
}
printf("\n");
}
void leveling(SqStack S1,SqStack S2,int n){
//將S1棧保存的信息一一取出，查找他孩子的結點，輸出其名字，並推入棧S2.
//即S2棧保存的結點是S1的下一輩
BiNode *p,*q;
printf("第%d層的信息為：\n");
while(!EmptyStack(S1)){
Pop(S1,*p);
q=p->firstchild;
if(q){
print(q);
q->level=n;
Push(S2,*q);
while(q=q->nextsibling){
print(q);
q->level=n;
Push(S2,*q);
}
}
}
}
void print(BiNode *p){
//輸出該結點處的夫婦名字
printf("%s,%s\\",p->man,p->woman);
}