|
目錄 1、二叉排序樹的定義 2、二叉排序樹的查找 3、二叉排序樹的插入與刪除 4、二叉排序樹的構(gòu)造 5、二叉排序樹的刪除 ? 定義 二叉排序樹（Binary Sort Tree）又稱為二叉查找樹（Binary Search Tree）、二叉搜索樹。 它是特殊的二叉樹：對于二叉樹，假設(shè)x為二叉樹中的任意一個結(jié)點，x節(jié)點包含關(guān)鍵字key，節(jié)點x的key值記為key[x]。如果y是x的左子樹中的一個結(jié)點，則key[y]<=key[x]；如果y是x的右子樹的一個結(jié)點，則key[y]>=key[x]。那么，這棵樹就是二叉查找樹。
? 二叉查找樹是先對待查找的數(shù)據(jù)進行生成樹，確保樹的左分支的值小于右分支的值，然后再就行和每個節(jié)點的父節(jié)點比較大小，查找最合適的范圍。這個算法的效率查找效率很高，但是如果使用這種查找方法要首先創(chuàng)建樹。 ? 它或者是一顆空樹，或者是具有下列性質(zhì)的二叉樹：
二叉查找樹的性質(zhì)：對二叉查找樹進行中序遍歷，即可得到有序的數(shù)列。 構(gòu)造一顆二叉排序樹的目的，其實并不是為了排序，而是為了提高查找和插入刪除關(guān)鍵字的速度。不管怎么說，在一個有序數(shù)據(jù)集上的查找，速度總是要快于無序的數(shù)據(jù)集的，而二叉排序樹這樣的非線性結(jié)構(gòu)，也有利于插入和排序的實現(xiàn)。 二叉查找樹的高度決定了二叉查找樹的查找效率。 ? 查找在二叉查找樹中查找x的過程如下：
復雜度分析，它和二分查找一樣，插入和查找的時間復雜度均為O(logn)，但是在最壞的情況下仍然會有O(n)的時間復雜度。原因在于插入和刪除元素的時候，樹沒有保持平衡。 根據(jù)上述的步驟，寫出其查找操作的代碼： c語言實現(xiàn)： 
?/*二叉樹的查找，非遞歸*/
BiSTNode *BST_Search1(BiSTree t, KeyType kx , BiSTNode **parent)
{ /*在二叉排序樹t上查找關(guān)鍵字為kx的元素，若找到，返回所在結(jié)點的地址，否則返回空指針，通過形參parent返回待查找結(jié)點kx的父結(jié)點地址*/
BiSTNode *p = t, *q = NULL;
while(p) { /*從根結(jié)點開始查找*/
if (kx == p->data.key) { /*查找成功*/
*parent = q;
return(p);
}
q = p;
if(kx < p->data.key)
p = p->lchild; /*kx小于p的關(guān)鍵字，在左子樹查找*/
else
p = p->rchild; /*kx大于p的關(guān)鍵字，在右子樹查找*/
}
*parent = q;
return p; /*查找失敗*/
}
View Code
/*二叉樹的查找，遞歸算法*/
BiSTNode *BST_Search2 (BiSTree t, KeyType kx)
{ /*在二叉排序樹t上查找關(guān)鍵字為kx的元素，若找到，返回所在結(jié)點的地址，否則返回空指針*/
if (t == NULL || t->data.key == kx)
return(t); /*若樹空或根結(jié)點等于kx*/
else if(kx < t ->data.key)
BST_Search2(t->lchild, kx);
else
BST_Search2(t->rchild, kx);
}
View Code
Java實現(xiàn)：
public boolean contains(T t)
{
return contains(t, rootTree);
}
/**從某個結(jié)點出開始查找元素*/
public boolean contains(T t, BinaryNode<T> node)
{
if(node==null)
return false;//結(jié)點為空，查找失敗
int result = t.compareTo(node.data);
if(result>0)
return contains(t,node.right);//遞歸查詢右子樹
else if(result<0)
return contains(t, node.left);//遞歸查詢左子樹
else
return true;
}
/**
這里我提供一個對二叉樹最大值
最小值的搜索*/
/**找到二叉查找樹中的最小值*/
public T findMin()
{
if(isEmpty())
{
System.out.println("二叉樹為空");
return null;
}else
return findMin(rootTree).data;
}
/**找到二叉查找樹中的最大值*/
public T findMax()
{
if(isEmpty())
{
System.out.println("二叉樹為空");
return null;
}else
return findMax(rootTree).data;
}
/**查詢出最小元素所在的結(jié)點*/
public BinaryNode<T> findMin(BinaryNode<T> node)
{
if(node==null)
return null;
else if(node.left==null)
return node;
return findMin(node.left);//遞歸查找
}
/**查詢出最大元素所在的結(jié)點*/
public BinaryNode<T> findMax(BinaryNode<T> node)
{
if(node!=null)
{
while(node.right!=null)
node=node.right;
}
return node;
}
View Code
? 插入 插入：從根結(jié)點開始逐個與關(guān)鍵字進行對比，小了去左邊，大了去右邊，碰到子樹為空的情況就將新的節(jié)點連接。二叉查找樹的插入過程如下：
c語言實現(xiàn)： ?
BiSTree BST_InsertNode (BiSTree t, KeyType kx)
{ /*在二叉排序樹上插入關(guān)鍵字為kx的結(jié)點*/
BiSTNode *f, *p, *s;
p = t;
while(p) { /*尋找插入位置*/
if (kx == p->data.key) {
printf("kx已存在,不需插入");
return(t);
} else {
f = p; /*結(jié)點f指向結(jié)點p的雙親*/
if(kx < p->data.key)
p = p->lchild;
else
p = p->rchild;
}
}
s = ( BiSTNode *)malloc(sizeof(BiSTNode)); /*申請并填裝結(jié)點*/
s->data.key = kx; s->lchild = NULL; s->rchild = NULL;
if (!t) t = s; /*向空樹中插入時*/
else if(kx < f->data.key)
f->lchild = s; /*插入結(jié)點s為結(jié)點f的右孩子*/
else
f->rchild = s; /*插入結(jié)點s為結(jié)點f的左孩子*/
return(t);
}
View Code
? Java實現(xiàn)：
/**插入元素*/
public void insert(T t)
{
rootTree = insert(t, rootTree);
}
/**在某個位置開始判斷插入元素*/
public BinaryNode<T> insert(T t,BinaryNode<T> node)
{
if(node==null)
{
//新構(gòu)造一個二叉查找樹
return new BinaryNode<T>(t, null, null);
}
int result = t.compareTo(node.data);
if(result<0)
node.left= insert(t,node.left);
else if(result>0)
node.right= insert(t,node.right);
else
;//doNothing
return node;
}
View Code
? ? 刪除如果要刪除的節(jié)點是葉子，直接刪；如果只有左子樹或只有右子樹，則刪除節(jié)點后，將子樹連接到父節(jié)點即可；如果同時有左右子樹，則可以將二叉排序樹進行中序遍歷，取將要被刪除的節(jié)點的前驅(qū)或者后繼節(jié)點替代這個被刪除的節(jié)點的位置。 二叉查找樹的刪除，分三種情況進行處理：
? ? ? ? ? ? ?
? /**刪除元素*/
public void remove(T t)
{
rootTree = remove(t,rootTree);
} /**在某個位置開始判斷刪除某個結(jié)點*/
public BinaryNode<T> remove(T t,BinaryNode<T> node)
{
if(node == null)
return node;//沒有找到,doNothing
int result = t.compareTo(node.data);
if(result>0)
node.right = remove(t,node.right);
else if(result<0)
node.left = remove(t,node.left);
else if(node.left!=null&&node.right!=null)
{
node.data = findMin(node.right).data;
node.right = remove(node.data,node.right);
}
else
node = (node.left!=null)?node.left:node.right;
return node;
}
? 二叉排序樹的查找分析 1) 二叉排序樹上查找某關(guān)鍵字等于給定值的結(jié)點過程，其實就是走了一條從根到該結(jié)點的路徑。 比較的關(guān)鍵字次數(shù)＝此結(jié)點的層次數(shù); 最多的比較次數(shù)＝樹的深度（或高度），即 ?log2 n? 1 2) 一棵二叉排序樹的平均查找長度為：
其中： ni 是每層結(jié)點個數(shù)； Ci 是結(jié)點所在層次數(shù)； m 為樹深。 ? 最壞情況：即插入的n個元素從一開始就有序， ——變成單支樹的形態(tài)！ 此時樹的深度為n ; ASL= (n 1)/2 此時查找效率與順序查找情況相同。 最好情況：即：與折半查找中的判定樹相同（形態(tài)比較均衡） 樹的深度為：?log 2n ? 1 ； ASL=log 2(n 1) –1 ；與折半查找相同。 ? 來源：http://www./content-1-203951.html |
|
|
