二叉鏈表存儲
㈠ 具有N個結點的二叉樹,採用二叉鏈表存儲,共有( )個空 鏈域.
這道數據題一共有N＋1個空鏈域。
二叉樹是n個有限元素的集合，該集合或者為空、或者由一個稱為根的元素及兩個不相交的、被分別稱為左子樹和右子樹的二叉樹組成，是有序樹。當集合為空時，稱該二叉樹為空二叉樹。在二叉樹中，一個元素也稱作一個結點。
滿二叉樹：如果一棵二叉樹只有度為0的結點和度為2的結點，並且度為0的結點在同一層上，則這棵二叉樹被稱為滿二叉樹。
完全二叉樹：深度為k，有n個結點的二叉樹當且僅當其每一個結點都與深度為k的滿二叉樹中編號從1到n的結點一一對應時，稱為完全二叉樹。
㈡ 二叉鏈表是二叉樹的存儲結構嗎
是的，二叉鏈表是二叉樹的存儲結構。二叉鏈表的每一個節點包含一個數據域和兩個鏈接域。
㈢ 一顆二叉樹具有n個節點 用二叉鏈表存儲時，其中有（ ）個指針用於指向孩子節點
1、這個問題有點不太清晰啊，由於是n個節點，每個節點有兩個指針（左右指針），所以其2n個指針用於指向孩子節點。
2、如果從實際指向了孩子節點的指針則為n-1個，因為n個節點的二叉樹，除根結點以外都有自己的父親結點或者說其都是一個孩子節點，所以有n-1個指針指向他們。
3、函數（function）在數學中為兩不為空集的集合間的一種對應關系：輸入值集合中的每項元素皆能對應唯一一項輸出值集合中的元素。
4、其定義通常分為傳統定義和近代定義，前者從運動變化的觀點出發，而後者從集合、映射的觀點出發。其近代定義是給定一個數集A，假設其中的元素為x，對A中的元素x施加對應法則f，記作f（x），得到另一數集B，假設B中的元素為y，則y與x之間的等量關系可以用y=f（x）表示。
在一個變化過程中，發生變化的量叫變數（數學中，常常為x，而y則隨x值的變化而變化），有些數值是不隨變數而改變的，我們稱它們為常量。
函數與不等式和方程存在聯系（初等函數），令函數值等於零，從幾何角度看，對應的自變數的值就是圖像與X軸的交點的橫坐標，從代數角度看，對應的自變數是方程的解。
㈣ 以二叉鏈表作為二叉樹的儲存結構，在具有n個結點的二叉鏈表中n（n＞0），空鏈域的個數為（）
以二叉鏈表作為二叉樹的儲存結構，在具有n個結點的二叉鏈表中n（n＞0），空鏈域的個數為n+1。
二叉鏈表結構描述：
typedef struct CSNode{
ElemType data;
struct CSNode *firstchild ， *netsibling;
} CSNode，* CSTree;
由於二叉樹的存儲結構比較簡單，處理起來也比較方便，所以有時需要把復雜的樹，轉換為簡單的二叉樹後再作處理。
(4)二叉鏈表存儲擴展閱讀：
二叉樹類型：
1、完全二叉樹——若設二叉樹的高度為h，除第 h 層外，其它各層 (1～h-1) 的結點數都達到最大個數，第h層有葉子結點，並且葉子結點都是從左到右依次排布，這就是完全二叉樹。
2、滿二叉樹——除了葉結點外每一個結點都有左右子葉且葉子結點都處在最底層的二叉樹。
3、平衡二叉樹——平衡二叉樹又被稱為AVL樹（區別於AVL演算法），它是一棵二叉排序樹，且具有以下性質：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，並且左右兩個子樹都是一棵平衡二叉樹。
㈤ 二叉鏈表存儲二叉樹的先序遍歷演算法
二叉鏈表存儲二叉樹的先序遍歷演算法，通常採用遞歸的演算法實現。首先訪問二叉樹的根節點，然後遞歸遍歷它的左子樹，最後，遞歸遍歷他的右子樹。
㈥ 二叉鏈表作存儲結構
//偶爾看到提問，翻了翻以前的課程設計，大部分功能類似...就直接復制上來啦，不知道能幫上忙不...都這么久了
//vc++ 6.0
#include "iostream.h"
#include "stdlib.h"
#include "stdio.h"
#define OK 1
#define NULL 0
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef char ElemType;//定義二叉樹結點值的類型為字元型
const int MaxLength=10;//結點個數不超過10個
typedef struct BTNode{
ElemType data;
struct BTNode *lchild,*rchild;
}BTNode,* BiTree;
void CreateBiTree(BiTree &T){//按先序次序輸入，構造二叉鏈表表示的二叉樹T，空格表示空樹
char ch;
ch=getchar(); //不能用cin來輸入，在cin中不能識別空格。
if(ch==' ') T=NULL;
else
{
if(!(T=(BTNode *)malloc(sizeof(BTNode)))) cout<<"malloc fail!";
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}
void PreOrderTraverse(BiTree T){//先序遍歷
if(T){
cout<<T->data<<' ';
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
void InOrderTraverse(BiTree T){ //中序遍歷
if(T){
InOrderTraverse(T->lchild);
cout<<T->data<<' ';
InOrderTraverse(T->rchild);
}
}
void PostOrderTraverse(BiTree T){ //後序遍歷
if(T){
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
cout<<T->data<<' ';
}
}
void LevelOrderTraverse(BiTree T){ //層序遍歷
BiTree Q[MaxLength];
int front=0,rear=0;
BiTree p;
if(T){ //根結點入隊
Q[rear]=T;
rear=(rear+1)%MaxLength;
}
while(front!=rear){
p=Q[front]; //隊頭元素出隊
front=(front+1)%MaxLength;
cout<<p->data<<' ';
if(p->lchild){ //左孩子不為空，入隊
Q[rear]=p->lchild;
rear=(rear+1)%MaxLength;
}
if(p->rchild){ //右孩子不為空，入隊
Q[rear]=p->rchild;
rear=(rear+1)%MaxLength;
}
}
}
int BTDepth(BiTree T){ //二叉樹的深度
if(!T) return 0;
else{
int h1=BTDepth(T->lchild);
int h2=BTDepth(T->rchild);
if(h1>h2) return h1+1;
else return h2+1;
}
}
int Leaf(BiTree T){ //二叉樹的葉子數
if(!T)
return 0;
else if(!T->lchild&&!T->rchild)
return 1;
else
return(Leaf(T->lchild)+Leaf(T->rchild));
}
int NodeCount(BiTree T){ //二叉樹的結點總數
if(!T)
return 0;
else
return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
}
int Initbitree (BiTree T) //空樹
{
T=NULL;
return FALSE;
}
int Isempty(BiTree T) //判斷為空否
{
if(T!=NULL)
return FALSE;
else
return TRUE;
}
int Destroy (BiTree &T) //銷毀
{
if( T != NULL )
{ if(T->lchild!=NULL)
Destroy ( T->lchild );
if(T->rchild!=NULL)
Destroy ( T->rchild );
free(T);
T=NULL;
}
return 1;
}
char Root(BiTree T) //返回根節點
{
if(T==NULL)
return NULL;
else
return T->data;
}
ElemType Value(BiTree &p)
{//返回P所指結點的值
return p->data;
}
ElemType Assign(BiTree p,ElemType value)
{ //給P的結點賦新值
return p->data=value;
}
BiTree Parent(BiTree T, BiTree p)//返回父節點
{
if(T!=NULL)
{
if(T->lchild->data==p->data)
{return T;}
if(T->rchild->data==p->data)
return T;
if(T->lchild)
return Parent(T->lchild,p);
if(T->rchild)
return Parent(T->rchild,p);
}
else return NULL;
}
char LeftChild(BiTree p) //返回p的左孩子的值
{
if(p->lchild) //若p存在左孩子
return p->lchild->data;
if(p->lchild==NULL)
return NULL;
}
char RightChild(BiTree p) // 返回p的右孩子的值
{
if(p->rchild)
return p->rchild->data;
if(p->rchild==NULL)
return NULL;
}
int Deletelchild(BiTree p) //刪除此二叉樹中p節點的左子樹
{
if(p)
{
Destroy(p->lchild);
return OK;
}
return ERROR;
}
int Deleterchild(BiTree p) //刪除此二叉樹中p節點的右子樹
{
if(p)
{
Destroy(p->rchild);
return OK;
}
return ERROR;
}
void search(BiTree T,char h,BiTree &p)//查詢節點
{
if(T==NULL)
return ;
else{
if(T->data==h)p=T;
search(T->lchild,h,p);
search(T->rchild,h,p);
}
}
void main()
{
BiTree T;
BiTree p;
BiTree q;
char ch;
T=NULL;
int select;
while(1){
cout<<"\n\n";
cout<<"**********************************\n";
cout<<"1.創建二叉樹\n";
cout<<"2.前序遞歸遍歷序列\n";
cout<<" 中序遞歸遍歷序列\n";
cout<<" 後序遞歸遍歷序列\n";
cout<<"3.層次遍歷序列\n";
cout<<"4.二叉樹的深度\n";
cout<<"5.葉子結點數目\n";
cout<<"6.求結點總數目\n";
cout<<"7.返回樹根節點\n";
cout<<"8.返回節點p的左孩子\n";
cout<<" 返回節點p的右孩子\n";
cout<<" 返回節點p的 雙親\n";
cout<<"9.判斷是否為空(是返回1，否返回0)\n";
cout<<"10.刪除p節點的左子樹\n";
cout<<"11.刪除p節點的右子樹\n";
cout<<"12.銷毀樹!\n";
cout<<"0.退出\n";
cout<<"**********************************\n";
cout<<"\n請選擇要執行的操作(選擇數字0-12):";
cin>>select;
switch(select){
case 0:
cout<<"退出!";
return;
case 1:
cout<<"請按先序次序輸入各結點的值，以空格表示空節點:"<<endl;
CreateBiTree(T);
cout<<"成功！";
break;
case 2:
if(!T) cout<<"未建立樹，請先建樹！";
else{
cout<<"\n先序遍歷:\n";
PreOrderTraverse(T);
cout<<"\n中序遍歷:\n";
InOrderTraverse(T);
cout<<"\n後序遍歷:\n";
PostOrderTraverse(T);
}
break;
case 3:
if(!T) cout<<"未建立樹，請先建樹！";
else{
cout<<"\n層序遍歷:\n";
LevelOrderTraverse(T);
}
break;
case 4:
cout<<"二叉樹的深度為:\n";
cout<<BTDepth(T);
break;
case 5:
cout<<"\n葉子節點數:\n";
cout<<Leaf(T);
break;
case 6:
cout<<"總節點數:\n";
cout<<NodeCount(T);
break;
case 7:
cout<<"返回根節點："<<Root(T);
break;
case 8:
cout<<"\n請輸入要查詢的節點p值：";
cin>>ch;
search(T,ch,p);
cout<<ch<<"的左孩子是："<<LeftChild(p)<<endl;
cout<<ch<<"的右孩子是："<<RightChild(p)<<endl;
q=Parent(T,p);
cout<<ch<<"的父親是："<<Value(q)<<endl;
break;
case 9:
cout<<"判斷是否為空(是為1，否為0：)"<<Isempty(T);
break;
case 10:
cout<<"\n請輸入節點p值：";
cin>>ch;
search(T,ch,p);
cout<<Deletelchild( p);
cout<<"刪除了"<<ch<<"的左孩子";
break;
case 11:
cout<<"\n請輸入節點p值：";
cin>>ch;
search(T,ch,p);
cout<<Deleterchild( p);
cout<<"刪除了"<<ch<<"的右孩子";
break;
case 12:
cout<<"銷毀樹!"<<Destroy(T);
break;
default:
cout<<"請確認選擇項為數字1-12!\n";
}
}
}
㈦ 二叉樹只能採用二又鏈表來存儲.，這個是否正確，為什麼
不是的.
二叉鏈表只是最直觀的一種存儲方式.而事實上,大部分的情況都不會使用二叉鏈表.除了一些動態調整樹的演算法比如平衡樹.
更為普遍的存儲方式是用線性表來儲存二叉樹.這種方式下,線性表N存儲的節點是N div 2的兒子節點.
㈧ 利用二叉鏈表存儲樹，則根節點的右指針是空的，這是為什麼呢，謝謝
二叉鏈表存儲樹結構，那麼任意節點的左孩子指向該結點的孩子結點，右孩子指針指向該節點的兄弟節點，因為這里是樹，不是森林，所以樹的根節點沒有兄弟結點，則右指針是空。
㈨ 建立任意二叉樹的二叉鏈表存儲，並對其進行先序、中序、後序遍歷，怎麼做
建立任意二叉樹的二叉鏈表存儲，並對其進行先序、中序、後序遍歷，程序操作如下:
#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;}
}
}