二叉查找樹查找演算法
Ⅰ 二叉樹查找樹演算法實現
#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
typedef int ElemType;
typedef int Status;
typedef struct TElemType{
int key;
int num;
}TElemType;
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
Status SearchBST(BiTree T,int key,BiTree f,BiTree &p){
if(!T) { p=f; return ERROR;}
else if(EQ(T->data.key,key)) { p=T; return OK; }
else if(LT(key,T->data.key))
return SearchBST(T->lchild,key,T,p);
else return SearchBST(T->rchild,key,T,p);
}
Status SearchBST1(BiTree T,int key,BiTree f,BiTree &p){
if(!T) { p=f; return ERROR;}
else if(EQ(T->data.key,key)) {
printf("%d %d",p->data.key,p->data.num);
p=T; return OK; }
else if(LT(key,T->data.key))
return SearchBST(T->lchild,key,T,p);
else return SearchBST(T->rchild,key,T,p);
}
Status InsertBST(BiTree &T,TElemType e){
BiTree s,p;
if(!SearchBST(T,e.key,NULL,p)){
s=(BiTree)malloc(sizeof(BiTNode));
s->data=e;
s->lchild=s->rchild=NULL;
if(!p) T=s;
else if(LT(e.key,p->data.key)) p->lchild=s;
else p->rchild=s;
return OK;
}
}
Status Output(TElemType e){
printf("%d ",e.key);
printf("%d\n",e.num);
}
Status PreOrderTraver( BiTree T){//二叉樹先序遍歷
if(T==NULL) return ERROR;
else{
Output(T->data);
PreOrderTraver(T->lchild);
PreOrderTraver(T->rchild);}
return OK;
}
int main()
{
BiTree T,f=NULL,q;
TElemType a;
int i,n,b;
printf("請輸入你要創建的二叉排序樹的結點個數:\n");
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d",a.key);
scanf("%d",a.num);
InsertBST(T,a);
}
printf("請輸入你要查找的關鍵字: ");{
scanf("%d",b);
if(SearchBST1(T,b,f,q)) printf("查找成功！\n");
else printf("查找失敗！\n");}
printf("二叉樹的先序遍歷:\n");
PreOrderTraver(T);
system("pause");
return 0;
}
這個就是！希望可以幫助你！
Ⅱ 二叉排序樹的構造和查找方法是什麼
二叉排序樹的構造過程：按照給定序列，以此將結點插入二叉排序樹中，在二叉排序樹中插入新結點，要保證插入後的二叉樹仍符合二叉排序樹的定義。
插入過程：若二叉排序樹為空，則待插入結點*S作為根結點插入到空樹中；
當非空時，將待插結點關鍵字S->key和樹根關鍵字t->key進行比較，
若s->key = t->key,則無須插入，若s->key< t->key,則插入到根的左子樹中，
若s->key> t->key,則插入到根的右子樹中。而子樹中的插入過程和在樹中的插入過程相同，
如此進行下去，直到把結點*s作為一個新的樹葉插入到二叉排序樹中，或者直到發現樹已有相同關鍵字的結點為止。
說明：
① 每次插入的新結點都是二叉排序樹上新的葉子結點。
② 由不同順序的關鍵字序列，會得到不同二叉排序樹。
③ 對於一個任意的關鍵字序列構造一棵二叉排序樹，其實質上對關鍵字進行排序。
查找的過程類似，從根結點開始進行比較，小於根結點的在左子樹上，大於根結點的在右子樹上，以此查找下去，直到查找成功或不成功（比較到葉子結點）。
Ⅲ 數據結構與演算法-二叉樹(Binary Tree)
名詞解釋
節點: 每個元素
父子關系: 用來連線相鄰節點之間的關系
父節點: A節點就是B節點的父節點
子節點: B節點就是A節點的子節點
兄弟節點: B、C、D這三個節點的父節點是同一個節點
根結點: 沒有父節點的節點
葉子結點: 沒有子節點的節點
節點的高度: 節點到葉子結點到最長路徑(邊數) (計數起點為0, 從下往上)
節點的深度: 根節點到這個節點經歷過的邊個數 (計數起點為0, 從上往下)
節點的層數: 節點到深度 + 1 (計數起點為1)
樹的高度: 根節點的高度
特點
最常用的樹數據結構
每個節點最多有兩個子節點(左子節點、右子節點)
滿二叉樹: 葉子節點全都在最底層，除了葉子節點之外，每個節點都有左右兩個子節點
完全二叉樹: 葉子節點都在最底下兩層，最後一層的葉子節點都 靠左排列 ，並且除了最後一層，其他層的節點個數都要達到最大
二叉樹存儲方式
數組順序存儲法
通過數組下標來順序存儲數據 (i表示當前節點深度,從0開始)
根節點: i = 1，左節點:2 * i，右節點: 2 * i + 1，父節點: i / 2
完全二叉樹採用此方式節省內存空間
鏈式存儲法
每個節點需要存儲三分數據:當前節點數據、左節點指針、右節點指針,比較佔用空間
遍歷
常用方式
前序遍歷: 樹任意節點，先列印當前節點，再列印它的左子樹，最後列印它的右子樹
中序遍歷: 樹任意節點，先列印它的左子樹，再列印當前節點，最後列印它的右子樹
後序遍歷: 樹任意節點，先列印它的左子樹，再列印它的右子樹，最後列印當前節點
二叉樹的前、中、後序遍歷就是一個遞歸的過程
時間復雜度是O(n)
每個節點最多被訪問兩次，遍歷操作的時間復雜度跟節點的個數n成正比
特點
二叉查找樹為實現快速查找而生，支持快速查找一個數據、快速插入、快速刪除一個數據
特殊結構: 其左子樹每個節點的值 < 樹的任意一個節點的值 < 其右子樹每個節點的值
先取根節點，如果它等於要查找的數據，那就返回。
如果要查找的數據比根節點的值小，那就在左子樹中遞歸查找；
如果要查找的數據比根節點的值大，那就在右子樹中遞歸查找
一般插入的數據在葉子節點上，從根節點開始依次比較要插入的數據和節點的大小關系
如果插入數據比節點的數值大，並且節點的右子樹為空，將新數據插到右子節點位置；
如果不為空，就再遞歸遍歷右子樹，查找插入位置。
如果插入數據比節點的數值小，並且節點的左子樹為空，將新數據插到左子節點位置；
如果不為空，就再遞歸遍歷左子樹，查找插入位置。
針對要刪除節點的子節點個數的不同，需分三種情況來處理
1.如果要刪除的節點沒有子節點，步驟如下: (如圖中的刪除節點55)
只需將父節點中指向要刪除節點的指針置為null
2.如果要刪除的節點只有一個子節點，步驟如下: (如圖中刪除節點13)
只需將父節點中指向要刪除節點的指針，讓它指向要刪除節點的子節點即可
3.如果要刪除的節點有兩個子節點，步驟如下: (如圖中的刪除節點18)
首先，需要找到這個節點的右子樹中的最小節點，把它替換到要刪除的節點上；
然後，再刪除掉這個最小節點，因為最小節點肯定沒有左子節點
刪除操作，有個優化方案: 就是單純將要刪除的節點標記為「已刪除」，
這種方案刪除操作就變簡單很多，但是比較浪費內存空間
支持快速地查找最大節點和最小節點、前驅節點和後繼節點
另外一種重要特性:
中序遍歷二叉查找樹，可以輸出有序的數據序列，時間復雜度為O(n)
因此，二叉查找樹也叫作二叉排序樹
以上幾種操作都默認樹中節點存儲的都是數字，而且都是不存在鍵值相同的情況
實際應用場景中採用對象的某個欄位作為鍵值來構建二叉查找樹，其他欄位稱為衛星數據
如果存儲的兩個對象鍵值相同，兩種解決方案
1.把值相同的數據都存儲在同一個節點(採用鏈表或支持動態擴容的數組等數據結構)
2.每個節點只存儲一個數據，把這個新插入的數據當作大於這個節點的值來處理，如下圖:
查找操作
當查找數據時遇到值相同的節點，繼續在右子樹中查找，直到遇到葉子節點才停止。
這樣就把鍵值等於要查找值的所有節點都查找出來
刪除操作
先查找到每個要刪除的節點，然後再按前面講的刪除操作的方法，依次刪除
對於同一組數據可構造不同二叉查找樹。查找、插入、刪除操作的執行效率都不一樣
圖最左邊樹，根節點的左右子樹極度不平衡，退化成鏈表，查找時間復雜度為O(n)
最理想的情況，二叉查找樹是一棵完全二叉樹（或滿二叉樹）
時間復雜度都跟樹的高度成正比，也就是O(height)
樹的高度就等於最大層數減一，為了方便計算，我們轉換成層來表示
滿二叉樹: 下一層節點個數是上一層的2倍，第K層包含節點個數就是2^(K-1)
完全二叉樹: 假設最大層數是L，總的節點個數n，它包含的節點個數在1個到2^(L-1)個之間
L的范圍是[ , +1]，完全二叉樹的高度小於等於
極度不平衡的二叉查找樹，它的查找性能肯定不能滿足我們的需求
平衡二叉查找樹: 樹的高度接近logn，時間復雜度較穩定為O(logn)
1.排序對比
散列表中的數據是無序存儲的，如果要輸出有序的數據，需要先進行排序
二叉查找樹只需要中序遍歷，就可以在O(n)的時間復雜度內，輸出有序的數據序列
2.性能穩定性對比
散列表擴容耗時很多，而且當遇到散列沖突時，性能不穩定
最常用的平衡二叉查找樹的性能非常穩定，時間復雜度穩定在O(logn)
3.時間復雜度對比
散列表查找等操作時間復雜度是常量級，因存在哈希沖突，這個常量不一定比logn小
另外加上哈希函數的耗時，也不一定就比平衡二叉查找樹的效率高
4.結構設計對比
散列表構造比較復雜，需要考慮:散列函數設計、沖突解決辦法、擴容、縮容等
平衡二叉查找樹只需要考慮平衡性，而且目前這個的解決方案較成熟、固定
5.空間復雜度
散列表: 避免過多散列沖突，裝載因子不能太大，特別基於開放定址法，否則浪費太多空間
Ⅳ 二叉排序樹查找的二叉排序樹查找的程序實現:
5. 二叉排序樹的刪除:
假設被刪結點是*p，其雙親是*f，不失一般性，設*p是*f的左孩子，下面分三種情況討論：
⑴ 若結點*p是葉子結點，則只需修改其雙親結點*f的指針即可。
⑵ 若結點*p只有左子樹PL或者只有右子樹PR，則只要使PL或PR 成為其雙親結點的左子樹即可。
⑶ 若結點*p的左、右子樹均非空，先找到*p的中序前趨結點*s（注意*s是*p的左子樹中的最右下的結點，它的右鏈域為空），然後有兩種做法：
① 令*p的左子樹直接鏈到*p的雙親結點*f的左鏈上,而*p的右子樹鏈到*p的中序前趨結點*s的右鏈上。
② 以*p的中序前趨結點*s代替*p（即把*s的數據復制到*p中），將*s的左子樹鏈到*s的雙親結點*q的左（或右）鏈上。
6. 刪除演算法演示 :
7. 二叉排序樹的查找:
在二叉排序樹中進行查找的過程和二分查找類似，也是一個逐步縮小查找范圍的過程。若查找成功，則是走了一條從根結點到待查結點的路徑；若查找失敗，則是走了一條根結點到某個葉子結點的路徑。因此，查找過程中和關鍵字比較的次數不超過樹的深度。
由於含有n個結點的二叉排序樹不唯一，形態和深度可能不同。故含有n個結點的二叉排序樹的平均查找長度和樹的形態有關。
最好的情況是： 二叉排序樹和二叉判定樹形態相同。
最壞的情況是： 二叉排序樹為單支樹，這時的平均查找長度和順序查找時相同。
最壞情況示例
就平均性能而言，二叉排序樹上的查找和二分查找相差不大，並且二叉排序樹上的插入和刪除結點十分方便，無須大量移動結點。
Ⅳ 二叉樹演算法是什麼
二叉樹的每個結點至多隻有二棵子樹(不存在度大於2的結點)，二叉樹的子樹有左右之分，次序不能顛倒。
二叉樹的第i層至多有2^（i 1）個結點；深度為k的二叉樹至多有2^k 1個結點；對任何一棵二叉樹T，如果其終端結點數為n0，度為2的結點數為n2，則n0 = n2 + 1。二叉樹演算法常被用於實現二叉查找樹和二叉堆。
二叉樹是每個節點最多有兩個子樹的有序樹。通常子樹被稱作「左子樹」(left subtree)和「右子樹」(right subtree)。二叉樹常被用於實現二叉查找樹和二叉堆。
(5)二叉查找樹查找演算法擴展閱讀：
二叉樹也是遞歸定義的，其結點有左右子樹之分，邏輯上二叉樹演算法有五種基本形態：
1、空二叉樹——(a)
2、只有一個根結點的二叉樹——(b);
3、右子樹為空的二叉樹——(c);
4、左子樹為空的二叉樹——(d);
5、完全二叉樹——(e)
注意：盡管二叉樹與樹有許多相似之處，但二叉樹不是樹的特殊情形。
Ⅵ C語言數據結構（二叉排序樹的創建及查找演算法）
int BSTInsert(BTNode *&T,int k)//修改此處，理由：引用型操作
Ⅶ 二叉樹演算法是什麼
二叉樹是每個節點最多有兩個子樹的有序樹。通常子樹被稱作「左子樹」(left subtree)和「右子樹」(right subtree)。二叉樹常被用於實現二叉查找樹和二叉堆。
性質
1、在二叉樹中，第i層的結點總數不超過2^(i-1)。
2、深度為h的二叉樹最多有2^h-1個結點（h>=1)，最少有h個結點。
3、對於任意一棵二叉樹，如果其葉結點數為N0，而度數為2的結點總數為N2，則N0=N2+1。
Ⅷ 二叉樹查找法
是錯誤的
二叉樹是一種很有用的非線性結構，具有以下兩個特點：
①非空二叉樹只有一個根結點；
②每一個結點最多有兩棵子樹，且分別稱為該結點的左子樹和右子樹。
由以上特點可以看出，在二叉樹中，每一個結點的度最大為2，即所有子樹（左子樹或右子樹）也均為二叉樹，而樹結構中的每一個結點的度可以是任意的。另外，二叉樹中的每個結點的子樹被明顯地分為左子樹和右子樹。在二叉樹中，一個結點可以只有左子樹而沒有右子樹，也可以只有右子樹而沒有左子樹。當一個結點既沒有左子樹也沒有右子樹時，該結點即為葉子結點。
（2）二叉樹的基本性質
二叉樹具有以下幾個性質：
性質1：在二叉樹的第k層上，最多有2k-1（k≥1）個結點；
性質2：深度為m的二叉樹最多有2m-1個結點；
性質3：在任意一棵二叉樹中，度為0的結點（即葉子結點）總是比度為2的結點多一個。
性質4：具有n個結點的二叉樹，其深度至少為〔log2n〕+1，其中〔log2n〕表示取log2n的整數部分。
Ⅸ 二叉查找樹演算法
#include <iostream>using namespace std;typedef struct _node{ int data; struct _node *pLeftPtr; struct _node *pRightPtr;}BTreeNode;class BinarySearchTree{public: BinarySearchTree(); ~BinarySearchTree(); bool Create(int* pIntArray,int arrLength); bool Insert(int data); // 查找節點，searchLength為搜索長度，返回值為true表示指定的數據存在，否則不存在 bool Find(int data, int* searchLength); // 中序輸出二叉樹 void MidOutput(); // 釋放內存 void Destroy(); void Delete(int data);protected: bool Insert(BTreeNode* pRoot, int data); bool Find(BTreeNode* pRoot,int data, int *searchLength); void Delete(BTreeNode* &pRoot, int data); void MidOutput(BTreeNode* pRoot); void Destroy(BTreeNode* pRoot);private: BTreeNode* m_pRoot; //二叉搜索樹根節點};BinarySearchTree::BinarySearchTree(){ m_pRoot = NULL;}BinarySearchTree::~BinarySearchTree(){ Destroy();}bool BinarySearchTree::Create(int* pIntArray,int arrLength){ for(int i=0; i<arrLength; i++) { if(!Insert(*(pIntArray+i))) return false; } return true;}bool BinarySearchTree::Insert(BTreeNode* pRoot, int data){ BTreeNode* pNewNode = new BTreeNode; if(pNewNode == NULL) return false; pNewNode->data = data; pNewNode->pLeftPtr = NULL; pNewNode->pRightPtr = NULL; BTreeNode* pCurrentNode = pRoot; BTreeNode* pParentNode = pCurrentNode;// 保存父節點的指針 int flag = 0;// 標記插入節點的位置 if(pCurrentNode == NULL) { m_pRoot = pNewNode; }else{ while(pCurrentNode) { if(data < pCurrentNode->data) { pParentNode = pCurrentNode; pCurrentNode = pCurrentNode->pLeftPtr; flag = 0; }else if(data > pCurrentNode->data){ pParentNode = pCurrentNode; pCurrentNode = pCurrentNode->pRightPtr; flag = 1; } } if(flag == 0) { pParentNode->pLeftPtr = pNewNode; }else{ pParentNode->pRightPtr = pNewNode; } } return true; }bool BinarySearchTree::Insert(int data){ return Insert(m_pRoot,data);}bool BinarySearchTree::Find(BTreeNode* pRoot,int data, int *searchLength){ if(pRoot == NULL) { *searchLength = 0; return false; } BTreeNode* pCurrentNode = pRoot; static int length = 0; while(pCurrentNode != NULL) { if(data == pCurrentNode->data) { *searchLength = length; cout<<"數字"<<data<<"存在二叉樹中,查找長度為: "<<endl<<length<<endl; return true; }else if(data < pCurrentNode->data) { length ++; pCurrentNode = pCurrentNode->pLeftPtr; }else{ length ++; pCurrentNode = pCurrentNode->pRightPtr; } } *searchLength = length; cout<<"數字"<<data<<"不在二叉樹中,查找長度為: "<<endl<<length<<endl; length = 0; // 每次查找結束，重新賦值為0 return false;}bool BinarySearchTree::Find(int data, int* searchLength){ return Find(m_pRoot,data,searchLength);}void BinarySearchTree::Destroy(BTreeNode* pRoot){ BTreeNode* pCurrentNode = pRoot; if(pCurrentNode == NULL) return; Destroy(pCurrentNode->pLeftPtr); Destroy(pCurrentNode->pRightPtr); delete pCurrentNode; m_pRoot = NULL;}void BinarySearchTree::Destroy(){ Destroy(m_pRoot);}void BinarySearchTree::MidOutput(BTreeNode* pRoot){ if(pRoot) { MidOutput(pRoot->pLeftPtr); cout<<pRoot->data <<" "; MidOutput(pRoot->pRightPtr); }}void BinarySearchTree::MidOutput(){ MidOutput(m_pRoot);}void BinarySearchTree::Delete(int data){ Delete(m_pRoot,data);}void BinarySearchTree::Delete(BTreeNode* &pRoot, int data){ if(!pRoot) return; else if(data == pRoot->data){ if(pRoot->pLeftPtr == NULL && pRoot->pRightPtr == NULL) // 葉子節點 { delete pRoot; pRoot = NULL; }else if(pRoot->pLeftPtr != NULL && pRoot->pRightPtr == NULL){ // 只有左子樹 BTreeNode* pNode = pRoot->pLeftPtr; delete pRoot; pRoot = pNode; }else if(pRoot->pLeftPtr == NULL && pRoot->pRightPtr != NULL){ // 只有右子樹 BTreeNode* pNode = pRoot->pRightPtr; delete pRoot; pRoot = pNode; }else{ // 有左右子樹 // 找到左子樹的最大節點 BTreeNode* pCurrentNode = pRoot->pLeftPtr; BTreeNode* pParentNode = NULL; while(pCurrentNode->pRightPtr != NULL) { pParentNode = pCurrentNode; pCurrentNode = pCurrentNode->pRightPtr; } pRoot->data = pCurrentNode->data; if(pParentNode) { pParentNode->pRightPtr = pCurrentNode->pLeftPtr; }else{ pRoot->pLeftPtr= pCurrentNode->pLeftPtr; } delete pCurrentNode; } }else if(data < pRoot->data) Delete(pRoot->pLeftPtr, data); else Delete(pRoot->pRightPtr, data);}void main(){ int data[8]; cout<<"請輸入整形數據, 數據用空格隔開, 回車鍵結束輸入"<<endl; for(int i=0; i<8; i++) cin>>data[i]; // int data[8] = {13,15,6,20,14,5,7,18}; BinarySearchTree tree; tree.Create(data,sizeof(data)/sizeof(data[0])); cout<<"插入數據後的二叉樹為: "<<endl; tree.MidOutput(); cout<<endl; int len_1=0; int len_2=0; tree.Find(14,&len_1); tree.Find(21,&len_2); tree.Delete(20); cout<<"刪除數字20後的二叉樹結果: "<<endl; tree.MidOutput(); cout<<endl; tree.Delete(15); cout<<"刪除數字15後的二叉樹結果: "<<endl; tree.MidOutput(); cout<<endl;}
Ⅹ 二叉樹查找和二分查找是同一演算法嗎
兩者的演算法思路其實很像：比中間的小就在剩下的左邊，大就在剩下的右邊找
但是：
二叉樹查找一般習慣是在鏈式存儲上進行，為一個樹形結構
二分查找一定在順序存儲上進行