二叉樹鏈表存儲的定義

『壹』 若二叉樹採用二叉鏈表結構存儲，請寫出二叉樹的結點類型定義，並編寫

template

T
search(BSTNode
*
tree,
const
T&
elemt)
{
stack
*>
travStack;
BSTNode

*p
=
root;
//遍歷指針
BSTNode

*q
=
root;
//層數看守
int
num
=
1;
If(p
!=
NULL)
travStack.push(p);
while(!travStack.empty())
{
p
=
travStack.pop();
if(p->data
!=
elemt)
if(p
==
q)
{
if(q->right
!=
NULL)
{
q
=
q->right;
}
q
=
q->left;
num+=1;
}
else
{
cout<<"The
number
of
piles
is
"<
left
!=
NULL)
travStack.push(p->left);
if(p->right
!=
NULL)
travStack.push(p->right);
}
}
這個是C++實現的，效率不高。主要運用的是前序遍歷的方式,存取方式用的是隊列；
思想：設置層數看守,看守始終在該層的最右端；按層次遍歷，將該層元素從左向右加入到隊列中；找到要求值就停止；

『貳』 簡述二叉鏈表的類型定義

二叉鏈表是樹的二叉鏈表實現方式。
樹的二叉鏈表實現方式
（孩子兄弟表示法）
以二叉鏈表作為樹的存儲結構。鏈表中結點的兩個鏈域分別指向該結點的第一個孩子結點和它的下一個兄弟結點。
typedefstruct CSNode{
ElemType data；
struct CSNode *firstchild ， *netsibling；
} CSNode，* CSTree；
由於二叉樹的存儲結構比較簡單，處理起來也比較方便，所以有時需要把復雜的樹，轉換為簡單的二叉樹後再作處理。

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

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

}

『肆』 二叉樹鏈表定義 不明白

這是一種連寫的方式,注意前面有個typedef 這個關鍵字是吧整個的結構體定義為一個符號,所以,大括弧後面的兩個東西就變成了對應的類型 BTNODE就是這種結構體類型 BINTREE是這這種結構體類型的指針 比如: BINTREE p = NULL; 就相當於 BTNODE *p = NULL; 也相當於 btnode *p = NULL 而BTNODE node; 相當於 btnode node; 實際上前面那個btnode可以不要

『伍』 完全二叉樹的定義，性質和詳細的解釋

完全二叉樹定義完全二叉樹(Complete Binary Tree)若設二叉樹的深度為h，除第 h 層外，其它各層 (1～h-1) 的結點數都達到最大個數，第 h 層所有的結點都連續集中在最左邊，這就是完全二叉樹。完全二叉樹是由滿二叉樹而引出來的。對於深度為K的，有N個結點的二叉樹，當且僅當其每一個結點都與深度為K的滿二叉樹中編號從1至n的結點一一對應時稱之為完全二叉樹。若一棵二叉樹至多隻有最下面的兩層上的結點的度數可以小於2，並且最下層上的結點都集中在該層最左邊的若干位置上，則此二叉樹成為完全二叉樹。完全二叉樹特點葉子結點只可能在最大的兩層上出現,對任意結點，若其右分支下的子孫最大層次為L，則其左分支下的子孫的最大層次必為L 或 L+1；出於簡便起見,完全二叉樹通常採用數組而不是鏈表存儲,其存儲結構如下:var tree:array[1..n]of longint;{n:integer;n>=1}對於tree[i]，有如下特點：（1）若i為奇數且i>1，那麼tree的左兄弟為tree[i-1]；（2）若i為偶數且i<n，那麼tree的右兄弟為tree[i+1]；（3）若i>1，tree的雙親為tree[i div 2]；（4）若2*i<=n，那麼tree的左孩子為tree[2*i]；若2*i+1<=n，那麼tree的右孩子為tree[2*i+1]；（5）若i>n div 2,那麼tree[i]為葉子結點（對應於（3））；（6）若i<(n-1) div 2.那麼tree[i]必有兩個孩子（對應於（4））。（7）滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹完全二叉樹第i層至多有2^（i-1）個節點，共i層的完全二叉樹最多有2^i-1個節點。4演算法如果一棵具有n個結點的深度為k的二叉樹，它的每一個結點都與深度為k的滿二叉樹中編號為1~n的結點一一對應，這棵二叉樹稱為完全二叉樹。可以根據公式進行推導，假設n0是度為0的結點總數（即葉子結點數），n1是度為1的結點總數，n2是度為2的結點總數，由二叉樹的性質可知：n0=n2+1，則n= n0+n1+n2（其中n為完全二叉樹的結點總數），由上述公式把n2消去得：n= 2n0+n1-1，由於完全二叉樹中度為1的結點數只有兩種可能0或1，由此得到n0=(n+1)/2或n0=n/2。總結起來，就是 n0=[n/2]，其中[]表示上取整。可根據完全二叉樹的結點總數計算出葉子結點數。

『陸』 什麼是二叉樹

二叉樹

在計算機科學中，二叉樹是每個節點最多有兩個子樹的樹結構。通常子樹被稱作「左子樹」（left subtree）和「右子樹」（right subtree）。二叉樹常被用於實現二叉查找樹和二叉堆。

二叉樹的每個結點至多隻有二棵子樹(不存在度大於2的結點)，二叉樹的子樹有左右之分，次序不能顛倒。二叉樹的第i層至多有2^{i-1}個結點；深度為k的二叉樹至多有2^k-1個結點；對任何一棵二叉樹T，如果其終端結點數為n_0，度為2的結點數為n_2，則n_0=n_2+1。

一棵深度為k，且有2^k-1個節點的二叉樹，稱為滿二叉樹。這種樹的特點是每一層上的節點數都是最大節點數。而在一棵二叉樹中，除最後一層外，若其餘層都是滿的，並且最後一層或者是滿的，或者是在右邊缺少連續若干節點，則此二叉樹為完全二叉樹。具有n個節點的完全二叉樹的深度為log2n+1。深度為k的完全二叉樹，至少有2^（k-1)個節點，至多有2^k-1個節點。

一、定義

二叉樹在圖論中是這樣定義的：二叉樹是一個連通的無環圖，並且每一個頂點的度不大於3。有根二叉樹還要滿足根結點的度不大於2。有了根結點之後，每個頂點定義了唯一的父結點，和最多2個子結點。然而，沒有足夠的信息來區分左結點和右結點。如果不考慮連通性，允許圖中有多個連通分量，這樣的結構叫做森林。

二、基本概念

二叉樹是遞歸定義的，其結點有左右子樹之分，邏輯上二叉樹有五種基本形態：

(1)空二叉樹——如圖(a)；

線索二叉樹的存儲結構

在中序線索樹找結點後繼的規律是：若其右標志為1，則右鏈為線索，指示其後繼，否則遍歷其右子樹時訪問的第一個結點（右子樹最左下的結點）為其後繼；找結點前驅的規律是：若其左標志為1，則左鏈為線索，指示其前驅，否則遍歷左子樹時最後訪問的一個結點（左子樹中最右下的結點）為其前驅。

在後序線索樹中找到結點的後繼分三種情況：

若結點是二叉樹的根，則其後繼為空；若結點是其雙親的右孩子，或是其雙親的左孩子且其雙親沒有右子樹，則其後繼即為雙親結點；若結點是其雙親的左孩子，且其雙親有右子樹，則其後繼為雙親右子樹上按後序遍歷列出的第一個結點。

數據結構定義為：

/*二叉線索存儲表示*/typedefenum{Link,Thread}PointerTag;/* Link(0)：指針，Thread(1)：線索*/typedefstruct BiThrNode{ TElemType data;struct BiThrNode *lchild,*rchild;/*左右孩子指針*/PointerTag LTag,RTag;/* 左右標志 */}BiThrNode,*BiThrTree;

八、實現演示

範例二叉樹：

A

B C

D E

此樹的順序結構為：ABCD##E

intmain()
{

node*p=newnode;

node*p=head;

head=p;

stringstr;

cin>>str;

creat(p,str,0)//默認根節點在str下標0的位置

return0;

}

//p為樹的根節點（已開辟動態內存）,str為二叉樹的順序存儲數組ABCD##E或其他順序存儲數組，r當前結點所在順序存儲數組位置.

intmain()

{

node*p=newnode;

node*p=head;

head=p;

stringstr;

cin>>str;

creat(p,str,0)//默認根節點在str下標0的位置

return0;

}

//p為樹的根節點（已開辟動態內存）,str為二叉樹的順序存儲數組ABCD##E或其他順序存儲數組，r當前結點所在順序存儲數組位置。

voidcreat(node*p,stringstr,intr)

{

p->data=str[r];

if(str[r*2+1]=='#'||r*2+1>str.size()-1)p->lch=NULL;

else

{

p->lch=newnode;

creat(p->lch,str,r*2+1);

}

if(str[r*2+2]=='#'||r*2+2>str.size()-1)p->rch=NULL;

else

{

p->rch=newnode;

creat(p->rch,str,r*2+2);

}

}

『柒』 二叉樹是什麼

二叉樹 (binary tree) 是另一種樹型結構，它的特點是每個結點至多隻有二棵子 樹 (即二叉樹中不存在度大於 2的結點 )，並且，二叉樹的子樹有左右之分，其次序不能任意顛倒 . 二叉樹是一種數據結構 :

Binary_tree=(D,R)

其中： D是具有相同特性的數據元素的集合 ;若 D等於空 ,則 R等於空稱為空的二叉樹 ;若 D等於空則 R是 D上某個二元關系 H的集合，即 R={H}，且
(1) D 中存在唯一的稱為根的元素 r，它的關系 H下無前驅 ;
(2) 若 D-{r}不等於空，則 D-{r}={Dl,Dr}，且 Dl交 Dr等於空 ;
(3) 若 Dl不等於空 ,則在 Dl中存在唯一的元素 xl,〈 r,xl〉屬於 H，且存在 Dl上的關系 Hl屬於 H； 若 Dr不等於空 ,則在 Dr中存在唯一的元素 xr,〈 r,xr〉 >屬於 H, 且存 Dr上的關 系 Hr屬於 H； H={r,xl,＜ r,xr＞ ,Hl, Hr};
(4) (Dl, Hl) 是一棵合本定義的二叉樹，稱為根 r的左子樹 ,(Dr,Hr)是一棵符合定義的二叉樹，稱為根的右子樹。

其中，圖 6.2 是各種形態的二叉樹 .

(1) 為空二叉樹 (2)只有一個根結點的二叉樹 (3)右子樹為空的二叉樹 (4)左子樹為空的二叉樹 (5)完全二叉樹

二叉樹的基本操作：

(1)INITIATE(BT ） 初始化操作。置 BT為空樹。

(2)ROOT(BT)\ROOT(x) 求根函數。求二叉樹 BT的根結點或求結點 x所在二叉樹的根結點。
若 BT是空樹或 x不在任何二叉樹上，則函數值為 「空 」。

(3)PARENT(BT,x) 求雙親函數。求二叉樹 BT中結點 x的雙親結點。若結點 x是二叉樹 BT 的根結點
或二叉樹 BT中無 x結點，則函數值為 「空 」。

(4)LCHILD(BT,x) 和 RCHILD(BT,x) 求孩子結點函數。分別求二叉樹 BT中結點 x的左孩 子和右孩子結點。
若結點 x為葉子結點或不在二叉樹 BT中，則函數值為 「空 」。

(5)LSIBLING(BT,x) 和 RSIBING(BT,x) 求兄弟函數。分別求二叉樹 BT中結點 x的左兄弟和右兄弟結點。
若結點 x是根結點或不在 BT中或是其雙親的左 /右子樹根 ,則函樹值 為 「空 」。

(6)CRT_BT(x,LBT,RBT) 建樹操作。生成一棵以結點 x為根，二叉樹 LBT和 RBT分別為左， 右子樹的二叉樹。

(7)INS_LCHILD(BT,y,x) 和 INS_RCHILD(BT,x) 插入子樹操作。將以結點 x為根且右子樹為空的二叉樹
分別置為二叉樹 BT中結點 y的左子樹和右子樹。若結點 y有左子樹 /右子樹，則插入後是結點 x的右子樹。

(8)DEL_LCHILD(BT,x) 和 DEL-RCHILD(BT,x) 刪除子樹操作。分別刪除二叉樹 BT中以結點 x為根的左子樹或右子樹。
若 x無左子樹或右子樹，則空操作。

(9)TRAVERSE(BT) 遍歷操作。按某個次序依此訪問二叉樹中各個結點，並使每個結點只被訪問一次。

(10)CLEAR(BT) 清除結構操作。將二叉樹 BT置為空樹。

5.2.2 二叉樹的存儲結構

一 、順序存儲結構
連續的存儲單元存儲二叉樹的數據元素。例如圖 6.4(b)的完全二叉樹 , 可以向量 (一維數組 ) bt(1:6)作它的存儲結構，將二叉樹中編號為 i的結點的數據元素存放在分量 bt[i]中 ,如圖 6.6(a) 所示。但這種順序存儲結構僅適合於完全二叉樹 ,而一般二叉樹也按這種形式來存儲 ,這將造成存 貯浪費。如和圖 6.4(c)的二叉樹相應的存儲結構圖 6.6(b)所示，圖中以 「0」表示不存在此結點 .

二、 鏈式存儲結構
由二叉樹的定義得知二叉樹的結點由一個數據元素和分別指向左右子樹的兩個分支構成 ,則表 示二叉樹的鏈表中的結點至少包含三個域 :數據域和左右指針域 ,如圖 (b)所示。有時 ,為了便於找 到結點的雙親 ,則還可在結點結構中增加一個指向其雙親受的指針域，如圖 6.7(c)所示。

5.3 遍歷二叉樹

遍歷二叉樹 (traversing binary tree)的問題， 即如何按某條搜索路徑巡訪樹中每個結點，使得每個結點均被訪問一次，而且僅被訪問一次。 其中常見的有三種情況：分別稱之為先 (根 )序遍歷，中 (根 )序遍歷和後 (根 )序遍歷。

5.3.1 前序遍歷

前序遍歷運算：即先訪問根結點，再前序遍歷左子樹，最後再前序遍歷右子樹。前序遍歷運算訪問二叉樹各結點是以根、左、右的順序進行訪問的。例如：

按前序遍歷此二叉樹的結果為： Hello!How are you?

proc preorder(bt:bitreprtr)
if (bt<>null)[
print(bt^);
preorder(bt^.lchild);
preorder(bt^.rchild);]
end;

5.3.2 中序遍歷

中序遍歷運算：即先中前序遍歷左子樹，然後再訪問根結點，最後再中序遍歷右子樹。中序遍歷運算訪問二叉樹各結點是以左、根、右的順序進行訪問的。例如：

按中序遍歷此二叉樹的結果為： a*b-c

proc inorder(bt:bitreprtr)
if (bt<>null)[
inorder(bt^.lchild);
print(bt^);
niorder(bt^.rchild);]
end;

5.3.3 後序遍歷

後序遍歷運算：即先後序遍歷左子樹，然後再後序遍歷右子樹，最後訪問根結點。後序遍歷運算訪問二叉樹各結點是以左、右、根的順序進行訪問的。例如：

按後序遍歷此二叉樹的結果為： Welecome to use it!

proc postorder(bt:bitreprtr)
if (bt<>null)[
postorder(bt^.lchild);
postorder(bt^.rchild);]
print(bt^);
end;

五、例：
1.用順序存儲方式建立一棵有31個結點的滿二叉樹，並對其進行先序遍歷。
2.用鏈表存儲方式建立一棵如圖三、4所示的二叉樹，並對其進行先序遍歷。
3.給出一組數據：R={10.18,3,8,12,2,7,3}，試編程序，先構造一棵二叉樹，然後以中序遍歷訪問所得到的二叉樹，並輸出遍歷結果。
4.給出八枚金幣a,b,c,d,e,f,g,h，編程以稱最少的次數，判定它們蹭是否有假幣，如果有，請找出這枚假幣，並判定這枚假幣是重了還是輕了。

中山紀念中學三鑫雙語學校信息學競賽組編寫 2004.7.15