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);
}