二叉樹bt的存儲結構
❶ 數據結構中的二叉樹題目,求大神幫忙做下,謝謝!
設二叉樹bt的一種存儲結構如表所示。其中，bt為樹根結點指針，lchild、rchild分別為結點的左、右孩子指針域，使用結點編號作為指針域值，0表示指針域值為空；data為結點的數據域。請完成：（1）畫出二叉樹bt的樹形表示。（2）寫出按先序、中序和後序遍歷二叉樹bt所得到的結點序列。
❷ 在vb中二叉樹是什麼東西，我們的書上沒有，而且二叉樹的相關知識有哪些要考，最後二叉樹的結點怎麼算。
二叉樹
在計算機科學中，二叉樹是每個結點最多有兩個子樹的有序樹。通常子樹的根被稱作「左子樹」（left subtree）和「右子樹」（right subtree）。二叉樹常被用作二叉查找樹和二叉堆。二叉樹的每個結點至多隻有二棵子樹(不存在度大於2的結點)，二叉樹的子樹有左右之分，次序不能顛倒。二叉樹的第i層至多有2的（i-1）次方個結點；深度為k的二叉樹至多有2k次 − 1個結點；對任何一棵二叉樹T，如果其終端結點數(即葉子結點數)為n0，度為2的結點數為n2，則n0 = n2 + 1。
樹和二叉樹的2個主要差別：
1. 樹中結點的最大度數沒有限制，而二叉樹結點的最大度數為2；
2. 樹的結點無左、右之分，而二叉樹的結點有左、右之分。……
樹是一種重要的非線性數據結構，直觀地看，它是數據元素（在樹中稱為結點）按分支關系組織起來的結構，很象自然界中的樹那樣。樹結構在客觀世界中廣泛存在，如人類社會的族譜和各種社會組織機構都可用樹形象表示。樹在計算機領域中也得到廣泛應用，如在編譯源程序如下時，可用樹表示源源程序如下的語法結構。又如在資料庫系統中，樹型結構也是信息的重要組織形式之一。一切具有層次關系的問題都可用樹來描述。
❸ 二叉樹的存儲方式有哪些
二叉樹的存儲方式通常有動態存儲。用結構體表示二叉樹的一個節點。用數據域保持保存節點的值，用鏈接語保存兩個孩子的指針。還有就是採用滿二叉樹的順序存儲方式。
❹ 設二叉樹的存儲結構為二叉鏈表，試寫出演算法（C函數）：將所有結點的左右子樹互換
1、以二叉鏈表作存儲結構，試編寫前序、中序、後序及層次順序遍歷二叉樹的演算法。
#define M 10
typedef int DataType;/*元素的數據類型*/
typedef struct node
{ DataType data;
struct node *lchild,*rchild;
}BitTNode,*BiTree;
int front=0,rear=0;
BitTNode *que[10];
BitTNode *creat()
{BitTNode *t;
DataType x;
scanf("%d",&x);
if(x==0) t=NULL;
else{ t=(BitTNode *)malloc(sizeof(BitTNode));
t->data=x;
t->lchild=creat();
t->rchild=creat();
}
return(t);
}/*creat*/
/* 前序遍歷二叉樹t */
void preorder(BiTree t)
{ if(t!=NULL)
{ printf("%4d",t->data);
preorder(t->lchild);
preorder(t->rchild);
}
}
/* 中序遍歷二叉樹t */
void inorder(BiTree t)
{ if(t!=NULL)
{ inorder(t->lchild);
printf("%4d",t->data);
inorder(t->rchild);
}
}
/* 後序遍歷二叉樹t */
void postorder(BiTree t)
{ if(t!=NULL)
{ postorder(t->lchild);
postorder(t->rchild);
printf("%4d",t->data);
}
}
void enqueue(BitTNode *t)
{if (front!=(rear+1)%M)
{ rear=(rear+1)%M;
que[rear]=t;
}
}/*enqueue*/
BitTNode * delqueue()
{ if(front==rear)return NULL;
{ front=(front+1)%M;
return (que[front]);
}
}/*delqueue*/
/* 按層次遍歷二叉樹t */
void levorder(BiTree t)
{ BitTNode *p;
if(t!=NULL)
{ enqueue(t);
while (front!=rear)
{ p=delqueue();
printf("%4d",p->data);
if(p->lchild!=NULL) enqueue(p->lchild);
if(p->rchild!=NULL) enqueue(p->rchild);
}
}
}/* levorder */
main()
{BitTNode *root;
root=creat();
printf("\n按先序遍歷次序生成的二叉樹");
printf("\n前序遍歷二叉樹");
preorder(root);
printf("\n中序遍歷二叉樹");
inorder(root);
printf("\n後序遍歷二叉樹");
postorder(root);
printf("\n層次順序遍歷二叉樹");
levorder(root);
}
2、以二叉鏈表作存儲結構，試編寫計算二叉樹深度、所有結點總數、葉子結點數、雙孩子結點個數、單孩子結點個數的演算法
#include <stdio.h>
#define MaxSize 100
typedef char ElemType;
typedef struct node
{
ElemType data;
struct node *left,*right;
} BTree;
BTree * createbt( )
{ BTree *q;
struct node1 *s[30];
int j,i,x;
printf("建立二叉樹，輸入結點對應的編號和值,編號和值之間用逗號隔開\n\n");
printf("i,x = ");
scanf("%d,%c",&i,&x);
while(i != 0 && x != '$')
{ q = (BTree*)malloc(sizeof(BTree)); /*建立一個新結點q*/
q->data = x; q->left = NULL; q->right = NULL;
s[i] = q; /*q新結點地址存入s指針數組中*/
if(i != 1) /*i = 1，對應的結點是根結點*/
{ j = i / 2; /*求雙親結點的編號j*/
if(i % 2 == 0)
s[j]->left = q; /*q結點編號為偶數則掛在雙親結點j的左邊*/
else
s[j]->right = q; /*q結點編號為奇數則掛在雙親結點j的右邊*/
}
printf("i,x = ");
scanf("%d,%c",&i,&x);
}
return s[1]; /*返回根結點地址*/
}
void preorder(BTree *BT)
/* 前序遍歷二叉樹t */
{ if(BT!=NULL)
{ printf("%4c", BT ->data);
preorder(BT ->left);
preorder(BT ->right);
}
}
int BTreeDepth(BTree *BT)
{
int leftdep,rightdep;
if (BT==NULL)
return(0);
else
{
leftdep=BTreeDepth(BT->left);
rightdep=BTreeDepth(BT->right);
if (leftdep>rightdep)
return(leftdep+1);
else
return(rightdep+1);
}
}
int nodecount(BTree *BT)
{
if (BT==NULL)
return(0);
else
return(nodecount(BT->left)+nodecount(BT->right)+1);
}
int leafcount(BTree *BT)
{
if (BT==NULL)
return(0);
else if (BT->left==NULL && BT->right==NULL)
return(1);
else
return(leafcount(BT->left)+leafcount(BT->right));
}
int notleafcount(BTree *BT)
{
if (BT==NULL)
return(0);
else if (BT->left==NULL && BT->right==NULL)
return(0);
else
return(notleafcount(BT->left)+notleafcount(BT->right)+1);
}
int onesoncount(BTree *BT)
{
if (BT==NULL)
return(0);
else if ((BT->left==NULL && BT->right!=NULL) ||
(BT->left!=NULL && BT->right==NULL))
return(onesoncount(BT->left)+onesoncount(BT->right)+1);
else
return(onesoncount(BT->left)+onesoncount(BT->right));
}
int twosoncount(BTree *BT)
{
if (BT==NULL)
return(0);
else if (BT->left==NULL || BT->right==NULL)
return(twosoncount(BT->left)+twosoncount(BT->right));
else if (BT->left!=NULL && BT->right!=NULL)
return(twosoncount(BT->left)+twosoncount(BT->right)+1);
}
main()
{
BTree *B;
B=creatree();
printf("\n按先序遍歷次序生成的二叉樹");
preorder(B);
printf("\n二叉樹深度:%d\n",BTreeDepth(B));
printf("總結點個數:%d\n",nodecount(B));
printf("葉子結點個數:%d\n",leafcount(B));
printf("非葉子結點個數:%d\n",notleafcount(B));
printf("具有雙孩子結點個數:%d\n",twosoncount(B));
printf("具有單孩子結點個數:%d\n",onesoncount(B));
}
如果還沒解決你的問題，可以加我網路HI賬號。
❺ 分析題： 5 對於一個棧，給出輸入項A、B、C、。如果輸入項序列由A，B，C所組成，試給出全部可能的輸出
輸入項序列是ABC，ACB，BAC。若序列的項屬於一個偏序集，則單調遞增序列就是其中每個項都大於等於之前的項；
若每個項都嚴格大於之前的項，這個序列就是嚴格單調遞增的。類似可定義單調遞減序列。單調序列是單調函數的一個特例。
(5)二叉樹bt的存儲結構擴展閱讀：
一個相對正式的定義：其項屬於集合S的有限序列是一個從 {1,2,...,n} 到S的函數，這里n≥0。屬於S的無限序列是從 {1,2,...}（自然數集合）到S的函數。
有限序列也稱作 n 元組。一個從所有整數到到集合的函數有時也稱作雙無限序列，這里將以負整數索引的序列認為是另一個以正整數索引的序列。
❻ 計算機軟體基礎一，二叉鏈存儲結構存儲，求二叉樹深度的問題
1
BTnodeDepth、lchilddep、BTNode、rchilddep、lchild和rchild 這些都是變數
其中BTnodeDepth是函數名，BTNode結構體，其他都是簡單類型變數
2
因為遍歷到當層的話，發現如果還有左子樹或者右子樹，就要加1遍歷下一層。。
❼ 二叉樹相關知識
二叉樹 (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，編程以稱最少的次數，判定它們蹭是否有假幣，如果有，請找出這枚假幣，並判定這枚假幣是重了還是輕了。
❽ 設二叉樹bt存儲結構如下
字元a是根結點,a的左分支是b,而a沒有右分支.
二叉樹示意圖:
a
/
b
/
cd
//
efg
//
hi
/
j
二叉樹的(鏈式)邏輯結構示意圖:
#a^
/
#b#
/
#c^#d#
//
^e^#f^#g^
//
^h^#i^
/
^j^
上述示意圖,符號#表示指針域,符號^表示NULL(空指針)
先序遍歷序列:abcedfhgij
中序遍歷序列:ecbhfdjiga
後序遍歷序列:echfjigdba
//C語言測試程序
#include"stdio.h"
#include"stdlib.h"
structtree
{
chardata;
structtree*left;
structtree*right;
};
typedefstructtreetreenode;
typedeftreenode*btree;
btreecreatebtree(char*data,intpos,intmaxPos)//遞歸創建法
{
btreenewnode;
if(data[pos]==0||pos>maxPos)
{
returnNULL;
}
else
{
newnode=(btree)malloc(sizeof(treenode));
newnode->data=data[pos];
newnode->left=createbtree(data,2*pos,maxPos);
newnode->right=createbtree(data,2*pos+1,maxPos);
returnnewnode;
}
}
voidpreorder(btreeptr)//先序遍歷(遞歸法)
{
if(ptr!=NULL)
{
printf("%C",ptr->data);
preorder(ptr->left);
preorder(ptr->right);
}
}
voidinorder(btreeptr)//中序遍歷(遞歸法)
{
if(ptr!=NULL)
{
inorder(ptr->left);
printf("%C",ptr->data);
inorder(ptr->right);
}
}
voidpostorder(btreeptr)//後序遍歷(遞歸法)
{
if(ptr!=NULL)
{
postorder(ptr->left);
postorder(ptr->right);
printf("%C",ptr->data);
}
}
intmain()
{
btreeroot=NULL;
inti;
chardata[64]={0,'a','b',0,'c','d',0,0,
'e',0,'f','g',0,0,0,0,
0,0,0,0,'h',0,'i',0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,'j',0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0};
root=createbtree(data,1,63);
printf("二叉樹的順序存儲內容:");
for(i=1;i<64;i++)
{
if(data[i]==0)
{
printf("^");
}
else
{
printf("%c",data[i]);
}
}
printf(" 二叉樹的先序遍歷序列:");
preorder(root);
printf(" 二叉樹的中序遍歷序列:");
inorder(root);
printf(" 二叉樹的後序遍歷序列:");
postorder(root);
printf(" ");
return0;
}
❾ 急！二叉樹的存儲結構，並完成：建立、查找、計算結點數、求高度、三種遍歷方式
public class BinaryTree<E> //二叉樹類
{
protected BinaryNode<E> root; //根結點
public BinaryTree() //構造空二叉樹
{
root=null;
}
public BinaryTree(BinaryNode<E> root) //構造指定根結點的二叉樹
{
this.root=root;
}
public boolean isEmpty() //判斷是否空二叉樹
{
return this.root==null;
}
public BinaryNode<E> getRoot() //返回二叉樹的根結點
{
return this.root;
}
//6.3.3 二叉樹的遍歷
public void preOrder() //先根次序遍歷二叉樹
{
System.out.print("\n先根序列： ");
preOrder(root);
}
private void preOrder(BinaryNode<E> p) //先根次序遍歷以p結點為根的子二叉樹
{
if(p!=null) //若二叉樹不空
{
System.out.print(p.data+" "); //訪問當前結點
preOrder(p.left); //按先根次序遍歷當前結點的左子樹
preOrder(p.right); //按先根次序遍歷當前結點的右子樹
}
}
public void inOrder() //中根次序遍歷二叉樹
{
System.out.print("\n中根序列： ");
inOrder(root);
}
private void inOrder(BinaryNode<E> p) //中根次序遍歷以p結點為根的子二叉樹
{
if (p!=null)
{
inOrder(p.left); //中根次序遍歷左子樹
System.out.print(p.data+" ");
inOrder(p.right); //中根次序遍歷右子樹
}
}
public void postOrder() //後根次序遍歷二叉樹
{
System.out.print("\n後根序列： ");
postOrder(root);
}
private void postOrder(BinaryNode<E> p) //後根次序遍歷以p結點為根的子二叉樹
{
if (p!=null)
{
postOrder(p.left);
postOrder(p.right);
System.out.print(p.data+" ");
}
}
//【例6.1】 構造並遍歷二叉樹。
//3. 基於遍歷的操作
public int count() //求一棵二叉樹中所有結點個數
{
return count(root);
}
public int count(BinaryNode<E> p) //求以p結點為根的子樹的結點個數
{
if (p!=null)
return 1+count(p.left)+count(p.right);
else
return 0;
}
public int depth() //求二叉樹的深度
{
return depth(root);
}
public int depth(BinaryNode<E> p) //求以p結點為根的子樹的深度，後根次序遍歷
{
if (p!=null)
{
int ld = depth(p.left); //求左子樹的深度
int rd = depth(p.right);
return (ld>=rd) ? ld+1 : rd+1;
}
return 0;
}
public BinaryNode<E> search(E value) //查找值為value的結點
{
return search(root, value);
}
public BinaryNode<E> search(BinaryNode<E> p, E value) //在以p為根的子樹中查找值為value的結點
{ //先根次序遍歷，返回查找到結點，若未找到返回null
BinaryNode<E> find=null; //記載找到結點
if (p!=null && value!=null)
{
if (p.data.equals(value))
find = p; //查找成功
else
{
find = search(p.left, value); //在左子樹中查找
if (find==null)
find=search(p.right, value); //若左子樹中未找到，則繼續在右子樹中查找
}
}
return find; //返回找到結點
}
public BinaryNode<E> getParent(BinaryNode<E> node) //返回指定結點node的父母結點
{ //若空樹、未找到或node為根，返回null
if (root==null || node==null || node==root)
return null;
return getParent(root, node);
}
public BinaryNode<E> getParent(BinaryNode<E> p, BinaryNode<E> node)
{ //在以p為根的子樹中查找並返回node結點的父母結點
BinaryNode<E> find=null; //記載找到結點
if (p!=null)
{
if (p.left==node || p.right==node)
find = p; //查找成功
else
{
find = getParent(p.left, node); //在左子樹中查找
if (find==null)
find = getParent(p.right, node); //若左子樹中未找到，則繼續在右子樹中查找
}
}
return find; //返回找到的父母結點
}
//6.3.4 構造二叉樹
// 1、以先根、中根次序遍歷序列建立二叉樹
public BinaryTree(String prestr,String instr) //1、以先根、中根次序遍歷序列建立二叉樹
{
root=create(prestr,instr);
//root=create2(prestr,instr);
}
public BinaryNode create(String prestr, String instr)
{
BinaryNode<String> p=null;
int k,n;
String first,presub,insub;
n=prestr.length();
if(n>0)
{
System.out.print("prestr="+prestr+"\t instr="+instr);
first=prestr.substring(0,1);
p=new BinaryNode<String>(first);
k=instr.indexOf(first);
System.out.println("\t first="+first+"\t k="+k);
presub=prestr.substring(1,k+1);
insub=instr.substring(0,k);
p.left=create(presub,insub);
presub=prestr.substring(k+1,n);
insub=instr.substring(k+1,n);
p.right=create(presub,insub);
}
return p;
}
public BinaryNode create2(String instr, String poststr) //以中根、後根次序遍歷序列建立二叉樹
{
BinaryNode<String> p=null;
int k,n;
String last,postsub,insub;
n=poststr.length();
if(n>0)
{
System.out.print("instr="+instr+"\t poststr="+poststr);
last=poststr.substring(poststr.length()-1,poststr.length());
p=new BinaryNode<String>(last);
k=instr.indexOf(last);
System.out.println("\t last="+last+"\t k="+k);
postsub=poststr.substring(0,k);
insub=instr.substring(0,k);
p.left=create2(insub,postsub);
postsub=poststr.substring(k,n-1);
insub=instr.substring(k+1,n);
p.right=create2(insub,postsub);
}
return p;
}
// 2、以標明空子樹的先根序列構造一棵二叉樹
public BinaryTree(E[] preorder) //2、以標明空子樹的先根序列構造一棵二叉樹
{
root=create(preorder);
}
private int i=0;
private BinaryNode<E> create(E[] preorder) //創建一棵子樹，當前結點值是preorder[i]
{ //返回所創建子樹的根結點
BinaryNode<E> p = null;
if (i<preorder.length)
{
E elem=preorder[i];
i++;
if (elem!=null)
{
p = new BinaryNode<E>(elem); //建立p結點
p.left = create(preorder); //建立p的左子樹
p.right = create(preorder); //建立p的右子樹
}
}
return p;
}
// 3、以廣義表表示建立二叉樹
public BinaryTree(String GenListStr)
{
System.out.println("GenListStr="+GenListStr);
if(GenListStr.length()>0)
root=create(GenListStr); //以GenListStr的全部元素建立一棵二叉樹
}
public BinaryNode create(String GenListStr) //以GenListStr的部分元素（從i開始）建立一棵子樹
{
BinaryNode p=null;
char ch=GenListStr.charAt(i);
if(ch>='A' && ch<='Z') //大寫字母
{
p=new BinaryNode<String>(ch+""); //建立結點
i++; //跳過大寫字母
ch=GenListStr.charAt(i);
if(ch=='(')
{
i++; //跳過(
p.left=create(GenListStr); //建立左子樹
i++; //跳過#
p.right=create(GenListStr); //建立右子樹
i++; //跳過）
}
}
if(ch=='#')
i++; //跳過#
return p; //ch非大寫字母時，返回null
}
//【例6.2】 輸出二叉樹中指定結點的所有祖先結點。
//6.3.5 二叉樹的插入和刪除操作
public void insert(BinaryNode<E> p, E element, boolean leftChild) //插入元素element作為p結點的孩子
{ //若leftChild為true，插入結點作為左孩子，否則作為右孩子
if (p!=null)
{
BinaryNode<E> q = new BinaryNode<E>(element);
if (leftChild)
{
q.left = p.left; //p結點的原左孩子成為q結點的左孩子
p.left = q; //q結點作為p結點的左孩子
}
else
{
q.right = p.right; //p結點的原右孩子成為q結點的右孩子
p.right = q; //q結點作為p結點的右孩子
}
}
}
public void insert(BinaryNode<E> p, E element) //插入元素element作為p結點的左孩子
{
insert(p, element, true);
}
public void remove(BinaryNode<E> p, boolean leftChild) //刪除p結點的左/右子樹
{ //若leftChild為true，刪除左子樹，否則刪除右子樹
if (p!=null)
{
if (leftChild)
p.left = null;
else
p.right = null;
}
}
public void remove(BinaryNode<E> p) //刪除p結點的左子樹
{
remove(p, true);
}
//6.3.6 二叉樹遍歷的非遞歸演算法
public void preOrderTraverse() //先根次序遍歷二叉樹的非遞歸演算法
{
System.out.print("先根次序遍歷（非遞歸）： ");
LinkedStack<BinaryNode<E>> stack = new LinkedStack<BinaryNode<E>>(); //創建一個空棧
BinaryNode<E> p = this.root;
while(p!=null || !stack.isEmpty()) //p非空或棧非空時
if(p!=null)
{
System.out.print(p.data+" "); //訪問結點
stack.push(p); //p結點入棧
p=p.left; //進入左子樹
}
else //p為空且棧非空時
{
p=stack.pop(); //p指向出棧結點
p=p.right; //進入右子樹
}
System.out.println();
}
public void inOrderTraverse() //中根次序遍歷二叉樹的非遞歸演算法
{
System.out.print("中根次序遍歷（非遞歸）： ");
LinkedStack<BinaryNode<E>> stack = new LinkedStack<BinaryNode<E>>(); //創建一個空棧
BinaryNode<E> p = this.root;
while(p!=null || !stack.isEmpty()) //p非空或棧非空時
if(p!=null)
{
stack.push(p); //p結點入棧
p=p.left; //進入左子樹
}
else //p為空且棧非空時
{
p=stack.pop(); //p指向出棧結點
System.out.print(p.data+" "); //訪問結點
p=p.right; //進入右子樹
}
System.out.println();
}
//後根次序未寫
//6.3.7 二叉樹的層次遍歷
public void levelOrder() //按層次遍歷二叉樹
{
LinkedQueue<BinaryNode<E>> que=new LinkedQueue<BinaryNode<E>>(); //創建一個空隊列
BinaryNode<E> p=this.root;
System.out.print("層次遍歷： ");
while(p!=null)
{
System.out.print(p.data+ " ");
if(p.left!=null)
que.enqueue(p.left); //p的左孩子結點入隊
if(p.right!=null)
que.enqueue(p.right); //p的右孩子結點入隊
p = que.dequeue(); //p指向出隊結點
}
System.out.println();
}
//第6章習題
public void leaf() //遍歷輸出葉子結點
{
leaf(root);
}
private void leaf(BinaryNode<E> p) //先根次序遍歷，輸出葉子結點，3種遍歷次序結果一樣
{
if(p!=null)
{
if (p.isLeaf())
System.out.print(p.data+" ");
leaf(p.left);
leaf(p.right);
}
}
public int countLeaf() //求一棵二叉樹中所有葉子結點個數
{
return countLeaf(root);
}
private int countLeaf(BinaryNode<E> p) //求以p結點為根的子樹的葉子結點個數
{
if (p==null)
return 0;
if (p.isLeaf())
return 1;
return countLeaf(p.left)+countLeaf(p.right);
}
public BinaryTree(BinaryTree<E> bitree) //以已知的bitree構造二叉樹
{
this.root = (bitree.root);
}
private BinaryNode<E> (BinaryNode<E> p) //復制以p根的子二叉樹
{
BinaryNode<E> q = null;
if(p!=null)
{
q = new BinaryNode<E>(p.data);
q.left = (p.left); //復制左子樹
q.right = (p.right); //復制右子樹
}
return q; //返回建立子樹的根結點
}
public boolean equals(Object obj) //比較兩棵二叉樹是否相等
{
if (obj == this)
return true;
if (obj instanceof BinaryTree)
{
BinaryTree<E> bitree = (BinaryTree)obj;
return equals(this.root, bitree.root);
}
return false;
}
private boolean equals(BinaryNode<E> p, BinaryNode<E> q) //判斷以p和q結點為根的兩棵子樹是否相等
{ //遞歸方法
if(p==null && q==null)
return true;
if(p!=null && q!=null)
return (p.data.equals(q.data)) && equals(p.left, q.left) && equals(p.right, q.right);
return false;
}
public boolean replace(E old, E value) //將首次出現的值為old結點值替換為value
{
BinaryNode<E> find=search(old); //查找值為old的結點
if(find!=null)
find.data = value; //替換結點元素值
return find!=null;
}
public void replaceAll(E old, E value) //將值為old的結點全部替換為value
{
replaceAll(root, old, value);
}
private void replaceAll(BinaryNode<E> p, E old, E value) //在以p為根的子樹中實現全部替換
{
if(p!=null)
{
if(p.data.equals(old))
p.data = value;
replaceAll(p.left, old, value);
replaceAll(p.right, old, value);
}
}
public static void main(String args[])
{
String[] preorder = {"A","B","D",null,"G",null,null,null,"C","E",null,null,"F","H"};
BinaryTree<String> bitree = new BinaryTree<String>(preorder);
preorder[0]="Z";
bitree.preOrder();
bitree.inOrder();
bitree.postOrder();
System.out.println("\n結點個數： "+bitree.count());
System.out.println("高度： "+bitree.depth());
System.out.print("葉子結點： ");
bitree.leaf();
System.out.println(" , 共"+bitree.countLeaf()+"個");
BinaryTree<String> bitree2 = new BinaryTree<String>(bitree);
System.out.println("兩棵二叉樹相等? "+bitree.equals(bitree2));
System.out.println("第2棵二叉樹替換(\"D\",\"F\")： "+bitree2.replace("D","F"));
System.out.println("兩棵二叉樹相等? "+bitree.equals(bitree2));
System.out.println("第2棵二叉樹全部替換(\"F\",\"Y\") ");
bitree2.replaceAll("F","Y");
bitree2.preOrder();
BinaryNode<String> find = bitree.search("D"); //查找
bitree.insert(find, "Z");
System.out.println("插入Z作為 "+find.data+" 的左孩子\n");
bitree.levelOrder();
bitree.preOrderTraverse();
bitree.inOrderTraverse();
String[] preorder2 = {"A","B",null,null,"C"}; //標明空子樹的先根序列
BinaryTree<String> bitree3 = new BinaryTree<String>(preorder2);
bitree3.preOrder();
bitree3.inOrder();
bitree3.postOrder();
/*
BinaryTree<String> bitree4 = new BinaryTree<String>(preorder2);
bitree4.root = bitree4.create(preorder2); //錯，i越界，私有化可避免問題
bitree4.preOrder();
*/
String[] preorder3 = {"D","B","A",null,null,"C",null,null,"E"}; //二叉排序樹
BinaryTree<String> bitree5 = new BinaryTree<String>(preorder3);
bitree5.inOrder();
System.out.println("\n二叉排序樹? "+bitree5.isSorted());
}
//第8章習題
public boolean isSorted() //判斷一棵二叉樹是否為二叉排序樹
{
return isSorted(this.root);
}
public boolean isSorted(BinaryNode<E> p)
{
boolean yes = true;
if (p!=null)
{
if (!(p.data instanceof Comparable))
return false;
Comparable cmpobj = (Comparable)p.data;
if ((p.left==null || p.left!=null && cmpobj.compareTo(p.left.data)>0) &&
(p.right==null || p.right!=null && cmpobj.compareTo(p.right.data)<0))
{
yes = isSorted(p.left);
if (yes)
yes = isSorted(p.right);
}
else
yes = false;
}
return yes;
}
}
/*
程序運行結果如下：
先根序列： A B D G C E F H
中根序列： D G B A E C H F
後根序列： G D B E H F C A
結點個數： 8
高度： 4
葉子結點： G E H , 共3個
兩棵二叉樹相等? true
第2棵二叉樹替換("D","F")： true
兩棵二叉樹相等? false
第2棵二叉樹全部替換("F","Y")
先根序列： A B Y G C E Y H
第1棵二叉樹查找： D
層次遍歷： A B C D E F Z G H
先根次序遍歷（非遞歸）： A B D Z G C E F H
中根次序遍歷（非遞歸）： Z D G B A E C H F
先根序列： A B D G C E F H
中根序列： D G B A E C H F
後根序列： G D B E H F C A
中根序列： A B C D E
二叉排序樹? true
*/
這是二叉樹的所有方法 及實現實例
還有就是需要建立節點類 你應該知道怎麼建的吧
❿ 數據結構 二叉樹
先介紹一下樹：
1.樹的定義
樹是一種常見的非線性的數據結構。樹的遞歸定義如下：
樹是n(n>0)個結點的有限集，這個集合滿足以下條件：
⑴有且僅有一個結點沒有前件（父親結點），該結點稱為樹的根；
⑵除根外，其餘的每個結點都有且僅有一個前件；
⑶除根外，每一個結點都通過唯一的路徑連到根上。這條路徑由根開始，而未端就在該結點上，且除根以外，路徑上的每一個結點都是前一個結點的後件（兒子結點）；
2、結點的分類
在樹中，一個結點包含一個元素以及所有指向其子樹的分支。結點一般分成三類
⑴根結點：沒有前件的結點。在樹中有且僅有一個根結點。
⑵分支結點：除根結點外，有後件的結點稱為分支結點。分支結點亦是其子樹的根；
⑶葉結點：沒有後件的結點稱為樹葉。由樹的定義可知，樹葉本身也是其父結點的子樹。
根結點到每一個分支結點或葉結點的路徑是唯一的。
3、有關度的定義
⑴結點的度：一個結點的子樹數目稱為該結點的度。顯
然，所有樹葉的度為0。
⑵樹的度：所有結點中最大的度稱為該樹的度。4、樹的深度（高度）
樹是分層次的。結點所在的層次是從根算起的。根結點在第一層，根的後件在第二層，其餘各層依次類推。即若某個結點在第k層，則該結點的後件均處在第k+1層。圖（b）中的樹共有五層。在樹中，父結點在同一層的所有結點構成兄弟關系。樹中最大的層次稱為樹的深度，亦稱高度。
5、有序樹和無序樹
按照樹中同層結點是否保持有序性，可將樹分為有序樹和無序樹。如果樹中同層結點從左而右排列，其次序不容互換，這樣的樹稱為有序樹；如果同層結點的次序任意，這樣的樹稱為無序樹。
6、樹的表示方法
樹的表示方法一般有兩種：
⑴自然界的樹形表示法：用結點和邊表示樹，例如上圖採用的就是自然界的樹形表示法。樹形表示法一般用於分析問題。
⑵括弧表示法：先將根結點放入一對圓括弧中，然後把它的子樹按由左而右的順序放入括弧中，而對子樹也採用同樣方法處理：同層子樹與它的根結點用圓括弧括起來，同層子樹之間用逗號隔開，最後用閉括弧括起來。例如圖可寫成如下形式
（r（a（w，x（d（h），e）），b（f），c（s，t（i（m，o，n），j），u）））
7、樹的存儲結構一般有兩種
⑴靜態的記錄數組。所有結點存儲在一個數組中，數組元素為記錄類型，包括數據域和長度為n(n為樹的度)的數組，分別存儲該結點的每一個兒子的下標
⑵動態的多重鏈表。由於樹中結點可以有多個元素，所以可以用多重鏈表來描述比較方便。所謂多重鏈表，就是每個結點由數據域和n(n 為樹的度)個指針域共n+1個域組成
下面是有關二叉樹的內容：
二叉樹的概念
二叉樹是一種很重要的非線性數據結構，它的特點是每個結點最多有兩個後件，且其子樹有左右之分（次序不能任意顛倒）。
1、二叉樹的遞歸定義和基本形態
二叉樹是以結點為元素的有限集，它或者為空，或者滿足以下條件：
⑴有一個特定的結點稱為根；
⑵餘下的結點分為互不相交的子集L和R，其中R是根的左子樹；L是根的右子樹；L和R又是二叉樹；
由上述定義可以看出，二叉樹和樹是兩個不同的概念
⑴樹的每一個結點可以有任意多個後件，而二叉樹中每個結點的後件不能超過2；
⑵樹的子樹可以不分次序（除有序樹外）；而二叉樹的子樹有左右之分。我們稱二叉樹中結點的左後件為左兒子，右後件為右兒子。
2、二叉樹的兩個特殊形態
⑴滿二叉樹： 如果一棵二叉樹的任何結點，或者是樹葉，或者恰有兩棵非空子樹，則此二叉樹稱作滿二叉樹。可以驗證具有n個葉結點的滿二叉樹共有2n-1個結點。
⑵完全二叉樹：如果一棵二叉樹最多隻有最下面兩層結點度數可以小於2，並且最下面一層的結點都集中在該層最左邊的若干位置上，則稱此二叉樹為完全二叉樹
3、二叉樹的三個主要性質
性質1：在二叉樹的第i（≥1）層上，最多有2i-1個 結點
證明：我們採用數學歸納法證明：當i=1時只有一個根結點，即2i-1=20=1，結論成立。假設第k(i=k)層上最多有2k-1個結點，考慮i=k+1。由歸納假設，在二叉樹第k層上最多有2k-1個結點，而每一個結點最多有兩個子結點，因此在第k+1層上最多有2．2k-1=2(k+1)-1=2i，結論成立。綜上所述，性質1成立。
性質2：在深度為k(k≥1)的二叉樹中最多有2k-1個 結點。
證明：由性質1，在二叉樹第i層上最多有2i-1個結點，顯然，第1層¨第k層的最多結點數為 個結點。證畢。
性質3：在任何二叉樹中，葉子結點數總比度為2的結點多1。
證明：設n0為二叉樹的葉結點數；n1為二叉樹中度為1的結點數；n2為二叉樹中度為2的結點數，顯然n=n0+n1+n2 （1）
由於二叉樹中除了根結點外，其餘每個結點都有且僅有一個前件。設 b為二叉樹的前件個數，n=b+1（2）
所有這些前件同時又為度為1和度為2的結點的後件。因此又有b=n1+2n2 (3)
我們將（3）代入（2）得出n=n1+2n2+1 (4)
比較（1）和（4），得出n0=n2+1,即葉子數比度為2的結點數多1
4、普通有序樹轉換成二叉樹
普通樹為有序樹T，將其轉化成二叉樹T』的規則如下：
⑴T中的結點與T』中的結點一一對應，即T中每個結點的序號和值在T』中保持不變；
⑵T中某結點v的第一個兒子結點為v1，則在T』中v1為對應結點v的左兒子結點；
⑶T中結點v的兒子序列，在T』中被依次鏈接成一條開始於v1的右鏈；
由上述轉化規則可以看出，一棵有序樹轉化成二叉樹的根結點是沒有右子樹的，並且除保留每個結點的最左分支外，其餘分支應去掉，然後從最左的兒子開始沿右兒子方向依次鏈接該結點的全部兒子。
5、二叉樹的存儲結構
將每個結點依次存放在一維數組中，用數組下標指示結點編號，編號的方法是從根結點開始編號1，然後由左而右進行連續編號。每個結點的信息包括
⑴一個數據域（data）；
⑵三個指針域，其中有父結點編號（prt）、左兒子結點編號（lch）和右兒子結點編號（rch）。
滿二叉樹和完全二叉樹一般採用順序存儲結構
對於一般的二叉樹，通常採用鏈式分配，即用二重鏈表表示一般的二叉樹。這種鏈式分配即可以採用靜態數據結構（數組），又可以採用動態數據結構（指針）。如果二叉樹的存儲需求量超過64Kb，則採用後者。由於二叉樹中每個結點通常包括數據元素和兩個分支。因此二叉樹對應的二重鏈表中每個結點應有三個域：
⑴值域： data
⑵左指針域： lch
⑶右指針域： rch
這種鏈表也稱為二叉鏈表。二叉鏈表頭指針bt指向二叉樹的根結點
6、二叉樹的遍歷
二叉樹遍歷的定義：按照一定的規律不重復地訪問(或取出結點中的信息，或對結點作其它的處理)二叉樹中的每一個結點。
二叉樹遍歷的順序：如果用L、D、R分別表示遍歷左子樹、訪問根結點、遍歷右子樹，則對二叉樹的遍歷可以有下列六種（3!=6）組合：LDR、 LRD、 DLR、 DRL、RDL、 RLD。若再限定先左後右的次序，則只剩下三種組合：LDR（中序遍歷）、LRD（後序遍歷）、DLR（前序遍歷）。
前序遍歷的規則如下：
若二叉樹為空，則退出。否則
⑴訪問處理根結點；
⑵前序遍歷左子樹；
⑶前序遍歷右子樹；
特點：由左而右逐條訪問由根出發的樹支 （回溯法的基礎）
中序遍歷的規則：
若二叉樹為空，則退出；否則
⑴中序遍歷左子樹；
⑵訪問處理根結點；
⑶中序遍歷右子樹；
後序遍歷的規則如下：
若二叉樹為空，則退出；否則
⑴後序遍歷左子樹；
⑵後序遍歷右子樹；
⑶訪問處理根結點；
特點：可統計任一個結點為根的子樹的情況（例如子樹的權和，最優策略的選擇（博弈數））