『壹』 二叉樹_鏈式存儲
二叉鏈：數據域（data）、左子結點域（lchild）、右子節點域（rchild）
定義：
求指定節點的左子節點地址：
求指定節點的右子節點地址：
二叉樹的遍歷：
定義： 按照某種順序訪問二叉樹中的每個結點，使每個結點被訪問一次且僅被訪問一次；
用途： 它是樹結構插入、刪除、修改、查找和排序運算的前提，是二叉樹一切運算的基礎和核心；
遍歷規則：
1、先序遍歷(DLR)： 頭 -> 左 -> 右
2、中序遍歷(LDR)： 左 -> 頭 -> 右
3、後序遍歷(LRD)： 左 -> 右 -> 頭
先中後都是對於根結點而言。
二叉樹遍歷的遞歸實現：
訪問方法：
先序遍歷：
中序遍歷：
後序遍歷：
插一嘴：遞歸實現的思路清晰，易於理解，但是執行效率很低。非遞歸實現效率高些。
二叉樹遍歷的非遞歸實現：
先序遍歷：
中序遍歷：
後序遍歷：好難-.-||略
利用「擴展先序遍歷序列」 創建二叉樹二叉鏈表：
1、若輸入的字元是 '#'，則建立空樹；
2、否則建立根結點，接著遞歸建立左子樹，然後遞歸建立右子樹。
『貳』 二叉樹的鏈式存儲結構的數據結構定義、創建、先序和後序遍歷，並將結果序列輸出。
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>
#include<cstdio>
#include<stdlib.h>
using namespace std;
typedef int Elemtype;
typedef struct BiTnode
{
Elemtype data;//數據域
struct BiTnode* Lchild,*Rchild; //左右子樹域；
}BiTnode,*BiTree;
int create(BiTree *T)
{
Elemtype ch;
Elemtype temp;
scanf("%d",&ch);
temp=getchar();
if(ch==-1)
{
*T=NULL;
}
else
{
*T=(BiTree)malloc(sizeof(BiTnode) );
if(!(*T))
{
exit(-1);
}
else
{
(*T)->data=ch;
printf("請輸入%d的左節點的值",ch);
create(&(*T)->Lchild);
printf("請輸入%d的右節點的值",ch);
create(&(*T)->Rchild);
}
}
return 1;
}
void Traverse(BiTree T)//前序遍歷二叉樹
{
if(NULL==T)
{
return;
}
else
{
printf("%d ",T->data);
Traverse(T->Lchild);
Traverse(T->Rchild);
}
}
//中序遍歷二叉樹
void midTraverse(BiTree T)
{
if(T==NULL){return;}
midTraverse(T->Lchild);
printf("%d ",T->data);
midTraverse(T->Rchild);
}
//後序遍歷二叉樹
void lasTraverse(BiTree T)
{
if(T==NULL){return;}
lasTraverse(T->Lchild);
lasTraverse(T->Rchild);
printf("%d ",T->data);
}
//求二叉樹的深度
int TreeDeep(BiTree T)
{
int deep=0;
if(T)
{
int leftdeep=TreeDeep(T->Lchild);
int rightdeep=TreeDeep(T->Rchild);
deep=leftdeep>=rightdeep?leftdeep+1:rightdeep+1;
}
return deep;
}
//求二叉樹葉子節點個數
int Leafcount(BiTree T,int &num)
{
if(T)
{
if(T->Lchild==NULL&&T->Rchild==NULL)
{
num++;
}
Leafcount(T->Lchild,num);
Leafcount(T->Rchild,num);
}
return num;
}
int main()
{
BiTree T;
BiTree *p=(BiTree*)malloc(sizeof(BiTree));
int deepth=0,num=0;
printf("請輸入第一個節點的值，-1代表沒有葉節點: ");
create(&T);
printf("先序遍歷二叉樹： ");
Traverse(T);
printf(" ");
printf("中序遍歷二叉樹: ");
midTraverse(T);
printf(" ");
printf("後序遍歷二叉樹： ");
lasTraverse(T);
printf(" ");
deepth=TreeDeep(T);
printf("樹的深度:%d ",deepth);
printf(" ");
Leafcount(T,num);
printf("二叉樹的葉子節點個數為:%d ",num);
printf(" ");
return 0;
(3)二叉鏈存儲先後序擴展閱讀：
二叉鏈表是樹的二叉鏈表實現方式。
樹的二叉鏈表實現方式：（孩子兄弟表示法）
以二叉鏈表作為樹的存儲結構。鏈表中結點的兩個鏈域分別指向該結點的第一個孩子結點和下一個兄弟結點。
結構描述：
typedefstruct CSNode{
ElemType data；
struct CSNode *firstchild ， *netsibling；
} CSNode，* CSTree；
由於二叉樹的存儲結構比較簡單，處理起來也比較方便，所以有時需要把復雜的樹，轉換為簡單的二叉樹後再作處理。
『肆』 建立任意二叉樹的二叉鏈表存儲，並對其進行先序、中序、後序遍歷，怎麼做
建立任意二叉樹的二叉鏈表存儲，並對其進行先序、中序、後序遍歷，程序操作如下:
#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(){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;}
}
}
『伍』 以二叉鏈表為存儲結構，分別寫出前序、中序、後序遍歷二叉樹的遞歸與非遞歸演算法。（數據結構）
#include<iostream.h>
#include<stdlib.h>
typedef char ElemType;
struct BTreeNode
{
ElemType data;
BTreeNode*left;
BTreeNode*right;
};
void InitBTree(BTreeNode*& BT)
{
BT=NULL;
}
void CreateBTree(BTreeNode*& BT,char*a)
{
const int MaxSize=1000;
BTreeNode*s[MaxSize];
int top=-1;
BT=NULL;
BTreeNode*p;
int k;
int i=0;
while (a[i])
{
switch(a[i])
{
case ' ':
break;
case'(':
if(top==MaxSize-1)
{
cout<<"棧空間太少，請增加MaxSize的值！"<<endl;
exit(1);
}
top++; s[top]=p;k=1;
break;
case ')':
if(top==-1)
{
cout<<"二叉樹的廣義表出錯!"<<endl; exit(1);
}
top--;
break;
case ',':
k=2;
break;
default:
p=new BTreeNode;
p->data=a[i];p->left=p->right=NULL;
if(BT==NULL) BT=p;
else
{
if(k==1) s[top]->left=p;
else s[top]->right=p;
}
}
i++;
}
}
bool EmptyBTree (BTreeNode*BT)
{
return BT==NULL;
}
void PreOrder(BTreeNode* BT)
{
if(BT!=NULL)
{
cout<<BT->data<<' ';
PreOrder(BT->left);
PreOrder(BT->right);
}
}
void InOrder(BTreeNode* BT)
{
if(BT!=NULL)
{
InOrder(BT->left);
cout<<BT->data<<' ';
InOrder(BT->right);
}
}
void PostOrder(BTreeNode* BT)
{
if(BT!=NULL)
{
PostOrder(BT->left);
PostOrder(BT->right);
cout<<BT->data<<' ';
}
}
void LevelOrder(BTreeNode* BT)
{
const int MaxSize=30;
BTreeNode* q[MaxSize];
int front=0,rear=0;
BTreeNode* p;
if(BT!=NULL)
{
rear=(rear+1)%MaxSize;
q[rear]=BT;
}
while (front!=rear)
{
front=(front+1)%MaxSize;
p=q[front];
cout<<p->data<<' ';
if(p->left!=NULL)
{
rear=(rear+1)%MaxSize;
q[rear]=p->left;
}
if(p->right!=NULL)
{
rear=(rear+1)%MaxSize;
q[rear]=p->right;
}
}
}
void PrintBTree(BTreeNode*BT)
{
if(BT!=NULL)
{
cout<<BT->data;
if(BT->left!=NULL || BT->right!=NULL )
{
cout<<'(';
PrintBTree(BT->left);
if(BT->right!=NULL)
cout<<',';
PrintBTree(BT->right);
cout<<')';
}
}
}
void ClearBTree(BTreeNode*&BT)
{
if(BT!=NULL)
{
ClearBTree(BT->left);
ClearBTree(BT->right);
delete BT;
BT=NULL;
}
}
void main()
{
BTreeNode* bt;
InitBTree(bt);
char b[50];
cout<<"輸入二叉樹的廣義表字元串"<<endl;
cin.getline(b,sizeof(b));
CreateBTree(bt,b);
PrintBTree(bt); cout<<endl;
cout<<"前序："; PreOrder(bt);cout<<endl;
cout<<"中序："; InOrder(bt); cout<<endl;
cout<<"後序: "; PostOrder(bt); cout<<endl;
cout<<"按層："; LevelOrder(bt); cout<<endl;
}
『陸』 二叉鏈表存儲二叉樹的先序遍歷演算法
二叉鏈表存儲二叉樹的先序遍歷演算法，通常採用遞歸的演算法實現。首先訪問二叉樹的根節點，然後遞歸遍歷它的左子樹，最後，遞歸遍歷他的右子樹。