二叉查找樹算法

#include iostreamusing 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; iarrLength; 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"存在二叉樹中,查找長度為: "endllengthendl; return true; }else if(data pCurrentNode-data) { length ++; pCurrentNode = pCurrentNode-pLeftPtr; }else{ length ++; pCurrentNode = pCurrentNode-pRightPtr; } } *searchLength = length; cout"數字"data"不在二叉樹中,查找長度為: "endllengthendl; 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); coutpRoot-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; i8; i++) cindata[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(); coutendl; 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(); coutendl; tree.Delete(15); cout"刪除數字15后的二叉樹結果: "endl; tree.MidOutput(); coutendl;}

網站建設哪家好，找成都創新互聯公司！專注于網頁設計、網站建設、微信開發、微信小程序開發、集團企業網站建設等服務項目。為回饋新老客戶創新互聯還提供了增城免費建站歡迎大家使用！

二叉搜索樹

哈哈，居然有人來提問了，城院的

我剛奮斗了2小時做了下，你看看對不？

Test5.cpp:

#include iostream.h

#include stdlib.h

typedef double ElemType;

#define Maxsize 100

#include "BSTree.h"

void main()

{

int i,n;

ElemType x;

ElemType a[Maxsize];

BTreeNode *bst;

InitBSTree(bst);

cout"請輸入你所要測試的二叉搜索樹的結點的個數:";

cinn;

cout"請輸入你要測試的二叉搜索樹:"endl;

for(i=0;in;i++){

cina[i];

}

CreateBSTree(bst,a,n);

cout"你輸入的二叉搜索樹的廣義表形式為:";

PrintBSTree(bst);

coutendl;

cout"輸入一個待插入結點的整數值:";

cinx;

Insert(bst,x);

cout"插入結點后的二叉搜索樹的廣義表形式為:";

PrintBSTree(bst);

coutendl;

cout"輸入一個待刪除結點的值:";

cinx;

if(Delete(bst,x)) cout"刪除元素"x"成功!"endl;

else cout"刪除元素"x"失敗!"endl;

PrintBSTree(bst);

coutendl;

cout"該二叉搜索樹中的最大值為:"MaxBSTree(bst)endl;

}

BSTree.h:

struct BTreeNode{

ElemType data;

ElemType count;

BTreeNode *left;

BTreeNode *right;

};

void InitBSTree(BTreeNode *bst) //初始化二叉搜索樹

{

bst=NULL;

}

void PrintBSTree(BTreeNode *bst) //以廣義表形式輸出二叉搜索樹

{

if(bst!=NULL){

coutbst-data;

cout'['bst-count']';

if(bst-left!=NULL||bst-right!=NULL){

cout'(';

PrintBSTree(bst-left);

if(bst-right!=NULL)

cout',';

PrintBSTree(bst-right);

cout')';

}

}

}

void Insert (BTreeNode *bst, ElemType item)

{

BTreeNode*t=bst,*parent=NULL;

while(t!=NULL){

parent=t;

if(itemt-data) t=t-left;

else if(itemt-data) t=t-right;

else{

t-count++;

break;

}

}

if((t==NULL)||item!=parent-data){

BTreeNode*p=new BTreeNode;

p-data=item;

p-count=1;

p-left=p-right=NULL;

if(parent==NULL) bst=p;

else if(itemparent-data) parent-left=p;

else parent-right=p;

}

}

void CreateBSTree(BTreeNode *bst, ElemType a[], int n) //建立二叉搜索樹（用非遞歸算法實現)

{

bst=NULL;

for(int i=0;in;i++)

Insert(bst,a[i]);

}

bool Delete (BTreeNode *bst , ElemType item)

{

BTreeNode *t=bst,*parent=NULL,*m,*n;

while((t!=NULL)(t-data!=item)){

if(item==t-data) break;

else{

if(itemt-data){

parent=t;

t=t-left;

}

else{

parent=t;

t=t-right;

}

}

}

if(t-count1){

t-count--;

return true;

}

else if(t==NULL){

cout"沒有找到待刪除結點!"endl;

return false;

}

else{

if((t-left==NULL)(t-right==NULL)){

if(t==bst)

bst=NULL;

else{

if(t==parent-left)

parent-left=NULL;

else

parent-right=NULL;

}

}

else if((t-left==NULL)||(t-right==NULL)){

if(t==bst){

if(t-left==NULL)

bst=t-right;

else

bst=t-left;

}

else{

if((t==parent-left)(t-left!=NULL))

parent-left=t-left;

else if((t==parent-left)(t-right!=NULL))

parent-left=t-right;

else if((t==parent-right)(t-left!=NULL))

parent-right=t-left;

else if((t==parent-right)(t-right!=NULL))

parent-right=t-right;

}

}

else{

if((t-left!=NULL)(t-right!=NULL)){

m=t;

n=t-left;

while(n-right!=NULL){

m=n;

n=n-right;

}

t-data=n-data;

if(m==t)

t-left=n-left;

else

m-right=n-left;

t=n;

}

}

free(t);

return true;

}

}

ElemType MaxBSTree(BTreeNode *bst) //求二叉搜索樹的最大結點值（用非遞歸算法實現）

{

ElemType max;

if(bst==NULL){

cout"該二叉搜索樹為空！"endl;

exit(1);

}

max=bst-data;

while(bst!=NULL){

if(maxbst-data)

max=bst-data;

bst=bst-right;

}

return max;

}

你試試吧，應該對的，選我做答案哈~

二叉搜索樹的基本操作

你可以用二叉排序樹！

比如查找：

首先判斷根節點是否為空，如果為空，則返回，否則判斷所查找的數和根節點的大小，如果查找的數小于根節點的，則遞歸左子樹，否則遞歸右子樹，直到到了空節點或者是找到結果兩張情況！！