go语言二叉搜索树算法,golang 二叉树遍历
二叉查找树算法
#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://cdiso.cn/article/hdpcjs.html
