建立二叉樹鏈式存儲結構

⑴ 建立任意二叉樹的二叉鏈表存儲，並對其進行先序、中序、後序遍歷。

#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");
}
這是先序遞歸和非遞歸建立二叉樹 和 先、中、後 的遍歷輸出

⑵ 如下圖所示，通過輸入該完全二叉樹的順序存儲結構，建立該完全二叉樹的鏈式存儲結構，並實現對該二叉樹的

你書上都有代碼，書名《數據結構》

⑶ 十一、設計在鏈式存儲結構上建立一棵二叉樹的演算法。

二叉樹存儲結構採用鏈式存儲結構，對於滿二叉樹與完全二叉樹可以按層序進行順序4.3關系代數關系資料庫系統的特點之一是它建立在數據理論的基礎之上，有

⑷ 二叉樹的鏈式存儲 c語言實現

這個是存儲結構，你參考下

⑸ 怎麼建立一棵以二叉鏈表方式存儲的二叉樹，並且對其進行遍歷（先序、中序和後序）

#include<stdio.h>
#include<stdio.h>
#include<malloc.h>
#include"c6_2.h"
#include<stdlib.h>#define TRUE 1
#define NULL 0
#define FALSE 0
#define ERROR 0
#define WRONG 0
#define OK 1
#define OVERFLOW 0typedef int TElemType;
typedef int Status;//二叉樹結構體
typedef struct BiTNode
{ TElemType data;//結點的值
BiTNode *lchild,*rchild;
}BiTNode,*BiTree;//隊列結構體
typedef BiTree QElemType;
typedef struct QNode
{ QElemType data;
QNode *next;
}*QueuePtr;struct LinkQueue
{ QueuePtr front,rear;//隊頭，隊尾指針
};#define ClearBiTree DestoryBiTree//清空二叉樹的操作和銷毀二叉樹的操作一樣
void InitBiTree(BiTree &T)
{ T=NULL;
}
void DestroyBiTree(BiTree &T)
{ //銷毀二叉樹
if(T)
{ DestroyBiTree(T->lchild);//銷毀左子樹
DestroyBiTree(T->rchild);//銷毀右子樹
free(T);
T=NULL;
}
}
void PreOrderTraverse(BiTree T,void(*visit)(TElemType))
{//先序遍歷二叉樹
if(T)
{ visit(T->data);
PreOrderTraverse(T->lchild,visit);
PreOrderTraverse(T->rchild,visit);
}
}
void InOrderTraverse(BiTree T,void(*visit)(TElemType))
{ //中序遍歷二叉樹
if(T)
{ InOrderTraverse(T->lchild,visit);
visit(T->data);
InOrderTraverse(T->rchild,visit);
}
}
void PostOrderTraverse(BiTree T,void(*visit)(TElemType))
{ //後序遍歷二叉樹
if(T)
{ PostOrderTraverse(T->lchild,visit);
PostOrderTraverse(T->rchild,visit);
visit(T->data);
}
}
Status BiTreeEmpty(BiTree T)
{ //判斷二叉樹是否為空
if(T)
return FALSE;
else
return TRUE;
}
int BiTreeDepth(BiTree T)//返回T的深度
{ int i,j;
if(!T)
return 0;
i=BiTreeDepth(T->lchild);//i為左孩子的深度
j=BiTreeDepth(T->rchild);//j為右孩子的深度
return i>j?i+1:j+1;
}
TElemType Root(BiTree T)
{ //返回二叉樹的根結點
if(BiTreeEmpty(T))
return NULL;
else
return T->data;
}
TElemType Value(BiTree p)
{//返回P所指結點的值
return p->data;
}
void Assign(BiTree p,TElemType value)
{ //給P的結點賦新值
p->data=value;
}BiTree Point(BiTree T,TElemType s)//返回二叉樹T中指向元素值為S的結點指針
{ LinkQueue q;
QElemType a;
if(T)
{ InitQueue(q);//初始化隊列
EnQueue(q,T);//根指針入隊
while(!QueueEmpty(q))//隊不空
{ DeQueue(q,a);//出隊，隊列元素賦給e
if(a->data==s)//a所指結點為的值為s
return a;
if(a->lchild)//有左孩子
EnQueue(q,a->lchild);//入隊左孩子
if(a->rchild)//有右孩子
EnQueue(q,a->rchild);//入隊右孩子
}
}
return NULL;
}
TElemType LeftChild(BiTree T,TElemType e)
{//返回e的左孩子
BiTree a;
if(T)
{ a=Point(T,e);//a是指向結點e的指針
if(a&&a->lchild)
return a->lchild->data;
}
return NULL;
}
TElemType RightChild(BiTree T,TElemType e)
{ BiTree a;
if(T)
{ a=Point(T,e);//a是指向結點e的指針
if(a&&a->rchild)//T中存在結點e並且e存在右孩子
return a->rchild->data;
}
return NULL;
}
Status DeleteChild(BiTree p,int LR)
{ if(p)
{ if(LR==0)
DestroyBiTree(p->lchild);
else
DestroyBiTree(p->rchild);
return OK;
}
return ERROR;
}void visit(TElemType e)
{ printf("%d",e);
}
void LevelOrderTraverse(BiTree T,void(*visit)(TElemType))
{//層序遍歷
LinkQueue q;
QElemType a;
if(T)
{ InitQueue(q);//初始化隊列
EnQueue(q,T);//根指針入隊
while(!QueueEmpty(q))
{ DeQueue(q,a);//出隊元素，賦給a
visit(a->data);//訪問a所指結點
if(a->lchild!=NULL)
EnQueue(q,a->lchild);
if(a->rchild!=NULL)
EnQueue(q,a->rchild);
}
}
}
void CreateBiTree(BiTree &T)
{ TElemType ch;scanf("%d",&ch);//輸入結點的值
if(ch==0)//結點為空
T=NULL;
else
{T=(BiTree)malloc(sizeof(BiTNode));<br>//生成根結點<br>if(!T)<br>exit(OVERFLOW);<br>T->data=ch;//將值賦給T所指結點</p><p>CreateBiTree(T->lchild);//遞歸構造左子樹<br>CreateBiTree(T->rchild);<br>} } TElemType Parent(BiTree T,TElemType e)
{//返回雙親
LinkQueue q;
QElemType a;
if(T)
{ InitQueue(q);
EnQueue(q,T);//樹根入隊列
while(!QueueEmpty(q))//隊不空
{DeQueue(q,a);//出隊，隊列元素賦給a<br> if(a->lchild&&a->lchild->data==e||a->rchild&&a->rchild->data==e)//找到e<br> return a->data;<br> else<br> { if(a->lchild)<br> EnQueue(q,a->lchild);//入隊列左孩子<br> if(a->rchild)<br> EnQueue(q,a->rchild);//入隊列右孩子<br> }
}
}
return NULL;
}
TElemType LeftSibling(BiTree T,TElemType e)
{ //返回左兄弟
TElemType a;
BiTree p;
if(T)
{ a=Parent(T,e);//a為e的雙親
if(a!=NULL)
{ p=Point(T,a);//p指向結點a的指針
if(p->lchild&&p->rchild&&p->rchild->data==e)//p存在左右孩子而且右孩子是e
return p->lchild->data;
}
}
return NULL;
}
TElemType RightSibling(BiTree T,TElemType e)
{ //返回右孩子
TElemType a;
BiTree p;
if(T)
{ a=Parent(T,e);//a為e的雙親
if(a!=NULL)
{ p=Point(T,a);//p為指向結點的a的指針
if(p->lchild&&p->rchild&&p->lchild->data==e)
return p->lchild->data;
}
}
return NULL;
}
Status InsertChild(BiTree p,int LR,BiTree c)
{ //根據LR為0或1，插入C為T中P所指結點的左或右子樹，P所結點的原有左或右子樹則成為C的右子樹
if(p)
{ if(LR==0)//把二叉樹C插入P所指結點的子樹
{ c->rchild=p->lchild;//p所結點的原有左子樹成為C的右子樹
p->lchild=c;//二叉樹成為P的左子樹
}
else{ c->rchild=p->rchild;//p指結點的原有右子樹成為C的右子樹
p->rchild=c;
}
return OK;
}
return ERROR;
}
//隊列操作
void InitQueue(LinkQueue &Q)
{//初始化一個隊列
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
if(!Q.front)//生成頭結點失敗
exit(OVERFLOW);
Q.front->next=NULL;
}
Status QueueEmpty(LinkQueue Q)
{ //判斷隊列是否為空
if(Q.front->next==NULL)
return TRUE;
else return FALSE;
}void EnQueue(LinkQueue &Q,QElemType e)
{ //插入元素e為隊列Q的新的隊尾元素
QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode));
//動態生成新結點
if(!p)
exit(OVERFLOW);
p->data=e;//將e的值賦給新結點
p->next=NULL;//新結點的指針為空
Q.rear->next=p;//原隊尾結點的指針域為指向新結點
Q.rear=p;//尾指針指向新結點
}
Status DeQueue(LinkQueue &Q,QElemType &e)
{ //若隊列不為空，刪除Q的隊頭元素，用e返回其值
QueuePtr p;
if(Q.front==Q.rear)//隊列為空
return ERROR;
p=Q.front->next;//p指向隊頭結點
e=p->data;//隊頭元素賦給e
Q.front->next=p->next;//頭結點指向下一個結點
if(Q.rear==p)//如果刪除的隊尾結點
Q.rear=Q.front;//修改隊尾指針指向頭結點
free(p);
return OK;
}
//主函數文件
#include<stdio.h>
#include"c6_2.h"main()
{ int i,j;
BiTree T,p,c;
TElemType e0,e1,e2,e3,e4;
InitBiTree(T);//初始化二叉樹
printf("構造二叉樹後，樹空否?%d(1,是,0否).樹的深度=%d.\n",BiTreeEmpty(T),BiTreeDepth(T));CreateBiTree(T);//建立二叉樹T
printf("構造二叉樹後，樹空否?%d(1,是,0否).樹的深度=%d.\n",BiTreeEmpty(T),BiTreeDepth(T));
e1=Root(T);//e1為二叉樹T的根結點的值
if(e1!=NULL)
printf("二叉樹的根為%d",e1);
else
printf("樹空，無根");e2=LeftChild(T,e1);
printf("左孩子:%d",e2);
e3=RightChild(T,e1);
printf("右孩子:%d",e3);
printf("\n");printf("先序遞歸遍歷:\n");
PreOrderTraverse(T,visit);
printf("\n");printf("後序遞歸遍歷:\n");
PostOrderTraverse(T,visit);
printf("\n");printf("中序遞歸遍歷:\n");
InOrderTraverse(T,visit);
printf("\n");printf("輸入一個結點的值:");
scanf("%d",&e1);
p=Point(T,e1);//p指向為e的指針
printf("結點的值為%d\n",Value(p));
e0=Parent(T,e1);//返回e1的雙親
printf("結點%d的雙親為%d",e1,e0);
printf("\n");e0=LeftChild(T,e1);//返回e1的左孩子
if(e0==NULL)
printf("沒有孩子");
else
printf("左孩子為%d",e0);
printf("\n");e0=RightChild(T,e1);//返回e1的右孩子
if(e0==NULL)
printf("沒有右孩子");
else
printf("右孩子為%d",e0);
printf("\n");
e0=RightSibling(T,e1);//返回e1的右兄弟
if(e0!=NULL)
printf("右兄弟為%d",e0);
else
printf("沒有右兄弟");
printf("\n");e0=LeftSibling(T,e1);//返回e1的左兄弟
if(e0!=NULL)
printf("左兄弟為%d",e0);
else
printf("沒有左兄弟");
printf("\n");
printf("要改變結點%d的值，請輸入新值:",e1);
scanf("%d",&e2);
Assign(p,e2);//將e2的值賦給p所指結點，代替e1
printf("層序遍歷二叉樹:\n");
LevelOrderTraverse(T,visit);
printf("\n");
printf("創建一棵根結點右子樹為空的新樹:");
CreateBiTree(c);//創建二叉樹
printf("先序遞歸遍歷二叉樹c:\n");
PreOrderTraverse(c,visit);
printf("將樹C插入樹T中，請輸入樹T中樹C的雙親結點C為左（0）或右（1）子樹:");
scanf("%d,%d",&e1,&i);
p=Point(T,e1);//p指向二叉樹T中將T中作為二叉樹C的雙親結點的e1
InsertChild(p,i,c);//將樹C插入到二叉樹T中作為結點的左或右子樹
printf("構造二叉樹後，樹空否?%d(1,是,0否).樹的深度=%d.\n",BiTreeEmpty(T),BiTreeDepth(T));
printf("先序遞歸遍歷二叉樹:\n");
PreOrderTraverse(T,visit);
}

⑹ 採用順序存儲方法和鏈式存儲方法分別畫出圖6.1所示二叉樹的存儲結構。【在線等】

線性是線性，順序是順序，線性是邏輯結構，順序是儲存結構，兩者不是一個概念。線性是指一個節點只有一個子節點，而樹，或二叉樹一個節點後有多個子節點，且子節點不能相互聯系。

順序存儲可能會浪費空間(在非完全二叉樹的時候)，但是讀取某個指定的節點的時候效率比較高。

鏈式存儲相對二叉樹比較大的時候浪費空間較少，但是讀取某個指定節點的時候效率偏低。

二叉樹的順序存儲，尋找後代節點和祖先節點都非常方便，但對於普通的二叉樹，順序存儲浪費大量的存儲空間，同樣也不利於節點的插入和刪除。因此順序存儲一般用於存儲完全二叉樹。

鏈式存儲相對順序存儲節省存儲空間，插入刪除節點時只需修改指針，但回尋找指定節點時很不方便。不過普通答的二叉樹一般是用鏈式存儲結構。

(6)建立二叉樹鏈式存儲結構擴展閱讀：

(1)完全二叉樹——若設二叉樹的高度為h，除第h層外，其它各層 (1～h-1) 的結點數都達到最大個數，第h層有葉子結點，並且葉子結點都是從左到右依次排布，這就是完全二叉樹。

(2)滿二叉樹——除了葉結點外每一個結點都有左右子葉且葉子結點都處在最底層的二叉樹。

(3)平衡二叉樹——平衡二叉樹又被稱為AVL樹（區別於AVL演算法），它是一棵二叉排序樹，且具有以下性質：是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，並且左右兩個子樹都是一棵平衡二叉樹。

二叉樹是樹的一種特殊情形，是一種更簡單而且應用更加廣泛的樹。

⑺ 二叉樹的鏈式存儲結構的數據結構定義、創建、先序和後序遍歷，並將結果序列輸出。

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

}

⑻ 建立一棵用二叉鏈表方式存儲的二叉樹，並對其進行先序遍歷，列印輸出結果

#include<iostream>
using namespace std;
class tree
{
public:
tree(){lchild=NULL;rchild=NULL;}
char data;
class tree *lchild;
class tree *rchild;
};
void build(tree *&t)//先序建樹
{
char c;
cin>>c;
if(c=='#')
{
t=NULL;
}
else
{
t=new tree;
t->data=c;
build(t->lchild);
build(t->rchild);
}
}

void preorder(tree *root)//這是遞歸實現
{
if (root!=NULL)
{
preorder(root->lchild);
cout<<root->data;
preorder(root->rchild);
}

}
class stack
{
public:
tree *top,*base;
};
void init (stack *s)//初始化棧
{
s->base=new tree[100];
s->top=s->base;
}
void push(stack *s,tree *t)//入棧
{
*(s->top++)=*t;
}
void pop(stack *s,tree &t)//取棧頂元素
{
t=*(--(s->top));
}
void inorder(tree *t)//這是非遞歸實現
{
stack *s=new stack;
tree *p;
init(s);
p=t;
tree temp=*t;
while(p||s->top!=s->base)
{
while(p)
{
push(s,p);
p=p->lchild;
}
if(s->top!=s->base)
{
pop(s,temp);
cout<<temp.data;
p=temp.rchild;
}
}
}
int main()
{
tree *t;
build(t);
preorder(t);
cout<<"非遞歸中序遍歷"<<endl;
inorder(t);
cout<<endl;
return 0;
}

程序如上，遞歸實現了先序遍歷，非遞歸實現了中序遍歷。
其他遍歷類似。
程序是可以運行的。

⑼ 用二叉鏈表作為存儲結構，建立二叉樹，對二叉樹進行前序、中序、後序遍歷，在對建立的二叉樹進行中序線索

#include

#include

using
namespace
std;
#define
maxsize
100
typedef
struct
binode
{
char
data;
struct
binode
*lchild,*rchild;
}binode,*bitree;
void
create(bitree
&t)//用先序遍歷的順序建立二叉鏈表（遞歸方法）
{
char
ch;
cin>>ch;
if(ch=='#')
t=null;
else
{
t=new
binode;
t->data=ch;
create(t->lchild);
create(t->rchild);
}
}
void
preorder(bitree
&t)//先序遍歷二叉樹（遞歸）
{
if(t)
{
cout<
data<<"
";
preorder(t->lchild);
preorder(t->rchild);
}
}
void
inorder(bitree
&t)//中序遍歷二叉樹（遞歸）
{
if(t)
{
inorder(t->lchild);
cout<
data<<"
";
inorder(t->rchild);
}
}
void
postorder(bitree
&t)//後序遍歷二叉樹（遞歸）
{
if(t)
{
postorder(t->lchild);
postorder(t->rchild);
cout<
data<<"
";
}
}
望採納~~~