c++二叉搜索树算法

完成二叉搜索树的结构，使用整型13,15,6,20,14,5,7,18测试，中序输出。搜索14，21两数结果，搜索长度分别多长，分析该树搜索成功与不成功的长度。测试删除20，15结果。
要c++代码。有选项，数字均为键盘输入！！附上运行截图，运行中提示语句用中文

shb8845369 · 2018-4-30 01:59:02

#include聽
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;聽idata聽=聽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聽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

c++二叉搜索树算法

1 个回复