二叉查找树算法

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

}

你试试吧，应该对的，选我做答案哈~

二叉搜索树的基本操作

你可以用二叉排序树！

比如查找：

首先判断根节点是否为空，如果为空，则返回，否则判断所查找的数和根节点的大小，如果查找的数小于根节点的，则递归左子树，否则递归右子树，直到到了空节点或者是找到结果两张情况！！

分享标题：go语言二叉搜索树算法,golang 二叉树遍历
文章来源：http://scyanting.com/article/hdpcjs.html