c樹的存儲

① 二叉樹的存儲結構是怎樣的有哪些類型的存儲結構對應的c語言描述是

樓上回答的是樹的存儲，不是二叉樹的存儲，主要如下：
1、順序存儲：適用於完全二叉樹，如果根從1開始編號，則第i結點的左孩子編號為2i，右孩子為2i+1，雙親編號為(i/2）下取整，空間緊密
2、二叉鏈表：適用於普通二叉樹，每個結點除了數據外，還有分別指向左右孩子結點的指針，存儲n個結點有n+1個空指針域，存儲密度小於順序存儲，但是適用范圍廣，缺陷是正常遍歷只能從雙親向孩子，退回來一般需要藉助棧（或者用遞歸，其實也是棧）
3、三叉鏈表：同樣適用於普通二叉樹，結點除了數據外，還有左右孩子與雙親的指針，存儲密度低於二叉鏈表，但是可以非常方便地在二叉樹中遍歷，不需要其他輔助工具

② 數據結構 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<malloc.h>

typedef int ElemType;

typedef struct LNode{

ElemType data;

struct LNode *lchild,*rchild;

}LNode,*TLNode;

void create(TLNode * Tree){ //創建

ElemType e;

scanf("%d",&e);

if(e==0)

*Tree=NULL;

else{

(*Tree)=(TLNode)malloc(sizeof(LNode));

(*Tree)->data=e;

printf("input %d lchild: ",e);

create(&(*Tree)->lchild);

printf("input %d rchild: ",e);

create(&(*Tree)->rchild);

}

}

void print1(TLNode Tree){ //先序遍歷

if(Tree!=NULL){

printf("%d-",Tree->data);

print1(Tree->lchild);

print1(Tree->rchild);

}

}

void print2(TLNode Tree){ //中序遍歷

if(Tree!=NULL){

print2(Tree->lchild);

printf("%d-",Tree->data);

print2(Tree->rchild);

}

}

void print3(TLNode Tree){ //後序遍歷

if(Tree!=NULL){

print3(Tree->lchild);

print3(Tree->rchild);

printf("%d-",Tree->data);

}

}

int leaf=0; //求葉子節點數

int depth(TLNode Tree){ //深度

int s1,s2;

if(Tree==NULL)

return 0;

else{

s1=depth(Tree->lchild);

s2=depth(Tree->rchild);

if(s1==0 && s2==0) leaf++;

return (s1>s2?s1:s2)+1;

}

}

int Cnode(TLNode Tree){ //總結點

int s1,s2;

if(Tree==NULL)

return 0;

else{

s1=Cnode(Tree->lchild);

s2=Cnode(Tree->rchild);

return s1+s2+1;

}

}

void main(){

TLNode Tree;

printf("input 根節點: ");

create(&Tree);

printf("先序遍歷:");

print1(Tree);

printf("中序遍歷");

print2(Tree);

printf("後序遍歷");

print3(Tree);

printf(" 深 度:%d ",depth(Tree));

printf("總結點數:%d ",Cnode(Tree));

printf("葉子結點數:%d ",leaf);

}