創建二叉樹的鏈表存儲結構
⑴ 二叉樹的鏈式存儲結構的數據結構定義、創建、先序和後序遍歷，並將結果序列輸出。
1、建立一個單鏈表，並從屏幕顯示單鏈表元素列表。
2、從鍵盤輸入一個數，查找在以上創建的單鏈表中是否存在該數;如果存在，顯示它的位置;如果不存在，給出相應提示。
3、在上述的單鏈表中的指定位置插入指定的元素
4、刪除上述單鏈表中指定位置的元素。
源程序：頭文件
#include<iostream.h>
#include<malloc.h>
typedef char ElemType;
typedef int Status;
#define OK 1
#define ERROR 0
typedef struct LNode{
ElemType data;
LNode *next;
}LNode,*LinkList;
void about(){ //版本信息
cout<<"單鏈表的操作"
}
void showmenu(){ //功能列表
cout<<endl <<" **********功能**********"<<endl
<<" * 1.輸出單鏈表的全部數據*"<<endl
<<" * 2.查找鏈表元素 *"<<endl
<<" * 3.鏈表插入元素 *"<<endl
<<" * 4.鏈表刪除元素 *"<<endl
<<" * 5.結束 *"<<endl
<<" ************************"<<endl
<<"請輸入所需功能: ";
}
//*******查看輸入的全部數據*********
void PrintList(LinkList L){
LinkList p;
cout<<endl<<"你輸入的數據為: ";
p=L->next; //從頭結點開始掃描
while(p){ //順指針向後掃描，直到p->next為NULL或i=j為止
cout<<p->data;
p=p->next; }
cout<<endl; }
//逆序輸入 n 個數據元素，建立帶頭結點的單鏈表
void CreateList_L(LinkList &L, int n) {
int i;
LinkList p;
L = new LNode;
L->next = NULL; // 先建立一個帶頭結點的單鏈表
cout<<"逆序輸入 n 個數據元素，建立帶頭結點的單鏈表"<<endl;
for (i = n; i > 0; --i) {
p = new LNode;
cin>>p->data; // 輸入元素值
p->next = L->next; L->next = p; // 插入
}
}
// L是帶頭結點的鏈表的頭指針，以 e 返回第 i 個元素
Status GetElem_L(LinkList L, int i, ElemType &e) {
int j;
LinkList p;
p = L->next; j = 1; // p指向第一個結點，j為計數器
while (p && j<i) { p = p->next; ++j; } // 順指針向後查找，直到 p 指向第 i 個元素或 p 為空
if ( !p || j>i )
return ERROR; // 第 i 個元素不存在
e = p->data; // 取得第 i 個元素
return OK;
}
// 本演算法在鏈表中第i 個結點之前插入新的元素 e
Status ListInsert_L(LinkList L, int i, ElemType e) {
int j;
LinkList p,s;
p = L; j = 0;
while (p && j < i-1)
{ p = p->next; ++j; } // 尋找第 i-1 個結點
if (!p || j > i-1)
return ERROR; // i 大於表長或者小於1
s = new LNode; // 生成新結點
if ( s == NULL) return ERROR;
s->data = e;
s->next = p->next; p->next = s; // 插入
return OK;
}
Status ListDelete_L(LinkList L, int i, ElemType &e)
{LinkList p,q;
int j;
p = L; j = 0;
while (p->next && j < i-1) { p = p->next; ++j; }
// 尋找第 i 個結點，並令 p 指向其前趨
if (!(p->next) || j > i-1)
return ERROR; // 刪除位置不合理
q = p->next; p->next = q->next; // 刪除並釋放結點
e = q->data; free(q);
return OK;
}
#include"LinkList.h"
void main()
{LinkList L;
int n,choice,i;
ElemType e;
about();
cout<<"請輸入鏈表中元素的個數";
cin>>n;
CreateList_L(L, n);
showmenu(); //功能列表
cin>>choice;
while(choice!=5)
{ //輸入時候退出程序
switch(choice){
case 1:PrintList(L);break; //1.查看輸入的全部數據
case 2:{
cout<<"輸入你要查找的元素的位置： ";
cin>>i;GetElem_L(L, i, e);
cout<<"第"<<i<<"個元素的值是"<<e<<endl;
break;} //2.查找鏈表元素
case 3:
{cout<<"請輸入你要插入元素的位置i： ";
cin>>i;
cout<<endl<<"請輸入你要插入元素的值： ";
cin>>e;
ListInsert_L(L, i,e);
break;} //3.鏈表插入元素
case 4:
{cout<<"請輸入你要刪除元素的位置";
cin>>i;
ListDelete_L(L, i, e) ;
break;} //4.鏈表刪除元素
default:cout<<"輸入錯誤,請輸入-5,輸入重顯示功能表^_^ "<<endl;
}
cout<<endl<<"輸入功能序號:";
cin>>choice;
}
}
⑵ 二叉樹採用鏈表存儲結構，實現建立、遍歷（先序、中序、後序）、求結點總數、葉子數、度為1.2的結點數。
前幾天寫的，輸入二叉樹的廣義表形式，建立二叉樹的鏈式存儲。輸出的是中序。有注釋。例如輸入：a(b,c(d,e(f)),g,h(i))
#include<stdio.h>
#include<stdlib.h>
int n=0; //全局變數
struct tree //二叉樹結構體
{
char data;
struct tree *lc;
struct tree *rc;
};
tree *creat(char a[]) //創建樹的二叉樹
{
tree *h;
h=(tree *)malloc(sizeof(tree));
h->lc=NULL;
h->rc=NULL;
if(a[n]!=')'&&a[n]!='('&&a[n]!=',') //當a[n]為字母存入a[]
{
h->data=a[n];
n++;
}
if(a[n]=='(') //a[n]為左括弧對h->lc遞歸操作
{
n++;
h->lc=creat(a);
}
if(a[n]==',') //a[n]為逗號對h->rc遞歸操作
{
n++;
h->rc=creat(a);
return h;
}
if(a[n]==')') //a[n]為右括弧返回h
{
n++;
return h;
}
else
return h;
}
void print(tree *h) //二叉樹中序輸出
{
if(h!=NULL)
{
print(h->lc);
printf("%c",h->data);
print(h->rc);
}
}
int high(char a[]) //判斷樹的高度
{
int i=0,max=0,p=0;
while(a[i]!=0)
{
if(a[i]=='(')
{
p++;
if(max<i)
max=p;
}
if(a[i]==')')
p--;
i++;
}
if(p!=0)
{
printf("左右括弧數不等,輸入錯誤\n"); //判斷左右括弧數是否相等
exit(1);
}
return max+1;
}
void main() //主函數
{
int i=0;
tree *h;
char a[50]={0};
gets(a);
while(a[i]!=0) //判斷各種可能出現的輸入錯誤
{
if(i==0&&(a[i]=='('||a[i]==')'||a[i]==',')) //判斷數組首元素是否為字母
{
printf("首節點錯誤\n");
exit(1);
}
if(a[i]=='(') //左括弧之前一定是字母
{
if(a[i-1]=='('||a[i-1]==')'||a[i-1]==',')
{
printf("輸入錯誤\n");
exit(1);
}
}
if(a[i]!='('&&a[i]!=')'&&a[i]!=',') //兩個字母不能在一起
{
if(a[i+1]!='('&&a[i+1]!=')'&&a[i+1]!=',')
{
printf("輸入錯誤,兩個字母不能在一起\n");
exit(1);
}
}
i++;
}
h=creat(a); //創建樹
printf("該樹的高度為:%d\n",high(a));
printf("該二叉樹的中序輸出為:");
print(h);
printf("\n");
}
⑶ 用C語言編寫：建立一棵以二叉鏈表結構存儲的二叉樹，並對其進行遍歷。求該二叉樹中的結點個數等操作。
存儲結構
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 ;
};
}
⑷ 編寫程序，用先序遞歸遍歷法建立二叉樹的二叉鏈表存儲結構，輸出其先序、中序、後序遍歷第k個訪問結點
#include "stdio.h"
#include "malloc.h"
#define ELEMTYPE char
BiTNode *bulid() /*建樹*/
{ BiTNode *q;
BiTNode *s[20];
int i,j;
char x;
printf("請按順序輸入二叉樹的結點以輸入0和*號結束 ");
printf("請輸入要輸入的為第幾個結點i= ");
scanf("%d",&i);
printf("請輸入你要輸入該結點的數為x=");
getchar();
scanf("%c",&x);
while(i!=0&&x!='*')
{q=(BiTNode*)malloc(sizeof(BiTNode));
q->data=x;
q->rchild=NULL;
q->lchild=NULL;
case(1): preoder(bt); goto k1;
case(2): InOrder(bt); goto k1;
case(3): postOrder(bt); goto k1;
case(0): break;
root=(struct lbtree *)malloc(sizeof(struct lbtree));
root->data=ch;
root->lchild=createbtree();
root->rchild=createbtree();
return(root);
}
dl=treedepth(root->lchild);
dr=treedepth(root->rchild);
if(dl>dr)depth=dl+1;
else depth=dr+1;
(4)創建二叉樹的鏈表存儲結構擴展閱讀：
(1)完全二叉樹——若設二叉樹的高度為h，除第 h 層外，其它各層 (1～h-1) 的結點數都達到最大個數，第h層有葉子結點，並且葉子結點都是從左到右依次排布，這就是完全二叉樹。
(2)滿二叉樹——除了葉結點外每一個結點都有左右子葉且葉子結點都處在最底層的二叉樹。
(3)平衡二叉樹——平衡二叉樹又被稱為AVL樹（區別於AVL演算法），它是一棵二叉排序樹，且具有以下性質：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，並且左右兩個子樹都是一棵平衡二叉樹。
⑸ 編寫一個建立二叉樹的演算法，要求採用二叉鏈表存儲結構
typedef struct node
{
char data;
struct node *lchild,*rchild;
}node,*bitptr;
bitptr creat(void)
{
bitptr root;
char c;
cin
⑹ 建立任意二叉樹的二叉鏈表存儲，並對其進行先序、中序、後序遍歷。
#include "stdio.h"
#include "stdlib.h"
#define STACK_INIT_SIZE 10 //棧的初始長度
#define STACKINCREMENT 5 //棧的追加長度
typedef struct bitree{
char data;
struct bitree *lchild,*rchild;
}bitree; //二叉樹結點定義
typedef struct {
bitree **base;
bitree **top;
int stacksize;
}sqstack; // 鏈棧結點定義top棧頂 base棧底 且棧元素是指向二叉樹結點的二級指針
//建立一個空棧
int initstack(sqstack *s)
{s->base=(bitree *)malloc(STACK_INIT_SIZE*sizeof(bitree)); //棧底指向開辟空間
if(!s->base) exit(1); //拋出異常
s->top=s->base; //棧頂=棧尾 表示棧空
s->stacksize=STACK_INIT_SIZE; //棧長度為開辟空間大小
return 1;
}
//進棧
int push(sqstack *s,bitree *e)
{if(s->top-s->base>=s->stacksize) //如果棧滿 追加開辟空間
{s->base=(bitree *)realloc (s->base,(s->stacksize+STACKINCREMENT)* sizeof(bitree));
if(!s->base) exit(1); //拋出異常
s->top=s->base+s->stacksize; //感覺這一句沒用
s->stacksize+=STACKINCREMENT;}
*(s->top)=e;s->top++; //進棧 棧頂後移
return 1;
}
//出棧
int pop(sqstack *s,bitree **e)
{if(s->top==s->base) return 0; //棧空 返回0
--s->top;*e=*(s->top); //棧頂前移 取出棧頂元素給e
return 1;}
//取棧頂
int gettop(sqstack *s,bitree **e) //去棧頂元素 注意top指向的是棧頂的後一個
{if(s->top==s->base) return 0; //所以 s->top-1
*e=*(s->top-1);
return 1;
}
/*------------------------非遞歸-----先序建立二叉樹----------------------------------*/
bitree *createprebitree()
{char ch;bitree *ht,*p,*q;
sqstack *s;
s=malloc(sizeof(bitree)); //加上這一句為s 初始化開辟空間
ch=getchar();
if(ch!='#'&&ch!='\n') /* 輸入二叉樹先序順序 是以完全二叉樹的先序順序
不是完全二叉樹的把沒有的結點以#表示 */
{ht=(bitree *)malloc(sizeof(bitree));
ht->data=ch;
ht->lchild=ht->rchild=NULL;
p=ht;
initstack(s);
push(s,ht); //根節點進棧
while((ch=getchar())!='\n') // 算
{if(ch!='#') {q=(bitree *)malloc(sizeof(bitree)); // 法
q->data=ch; //
if(p==*(s->top-1)) p->lchild=q; // 核
else p->rchild=q; //
push(s,q);p=q; // 心
} //
else {if(p==*(s->top-1)) p->lchild=NULL; // 的
else p->rchild=NULL; //
pop(s,&p);} // 步
//
} // 驟
return ht;
}
else return NULL;
}
/*--------------------------遞歸---------先序建立二叉樹-------------------------------*/
void CreateBiTree(bitree **T) {
//按先序次序輸入二叉樹中的結點的值（一個字元），空格字元表示空樹，
//構造二叉鏈表表示二叉樹
char ch;
scanf("%c",&ch);
if(ch=='#') *T=NULL;
else{
*T=(bitree * )malloc(sizeof(bitree));
if(!*T) exit(1);
(*T)->data=ch; //生成根結點
CreateBiTree(&(*T)->lchild); //構造左子樹
CreateBiTree(&(*T)->rchild); //構造右子樹
}
}
/*--------------------------非遞歸-------中序建立二叉樹-------------------------------*/
/*--------------------------遞歸---------中序建立二叉樹-------------------------------*/
/*--------------------------非遞歸-------後序建立二叉樹-------------------------------*/
/*--------------------------遞歸---------後序建立二叉樹-------------------------------*/
/*-----------------------非遞歸------先序輸出二叉樹------------------------------*/
void preordertraverse(bitree *h)
{sqstack m;
initstack(&m);
while(h||m.base!=m.top)
{if(h) {push(&m,h);printf("%c",h->data);h=h->lchild;}
else{pop(&m,&h);
h=h->rchild;}
}
}
/*------------------------非遞歸-----中序輸出二叉樹----------------------------*/
void inordertraverse(bitree *h)
{sqstack m;
initstack(&m);
while(h||m.base!=m.top)
{if(h) {push(&m,h);h=h->lchild;}
else {
pop(&m,&h);
printf("%c",h->data);
h=h->rchild;
}
}
}
/*---------------------非遞歸----後序遍歷二叉樹----------------------------------*/
void postordertraverse(bitree *h)
{
sqstack m;
initstack(&m);
while(h||m.base!=m.top)
{if(h) {
push(&m,h);
h=h->lchild;}
else {
bitree *r; //使用r結點表示訪問了右子樹 代替標志域
gettop(&m,&h);
if(h->rchild&&h->rchild!=r)
{h=h->rchild;
push(&m,h);
h=h->lchild;}
else{pop(&m,&h);
printf("%c",h->data);
r=h;h=NULL;}
}
}
}
//層次遍歷二叉樹 用隊列 哈哈以後做
/*-------------------------------主過程-------------------------------*/
int main()
{bitree *ht;
printf("先序非遞歸建立一個二叉樹:");
if((ht=createprebitree())!=NULL) //非遞歸建立
//CreateBiTree(&ht);
//if(ht!=NULL) //遞歸建立
{
printf("先序遍歷輸出二叉樹:");
preordertraverse(ht);
putchar('\n');
printf("中序遍歷輸出二叉樹:");
inordertraverse(ht);
putchar('\n');
printf("後序遍歷輸出二叉樹:");
postordertraverse(ht);
putchar('\n');
}
else printf("空二叉樹\n");
}
這是先序遞歸和非遞歸建立二叉樹 和 先、中、後 的遍歷輸出
⑺ 用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);
}
⑻ 十一、設計在鏈式存儲結構上建立一棵二叉樹的演算法。
二叉樹存儲結構採用鏈式存儲結構，對於滿二叉樹與完全二叉樹可以按層序進行順序4.3關系代數關系資料庫系統的特點之一是它建立在數據理論的基礎之上，有