C++实现的变种二分查找法(折半查找)--二叉查找树

C++实现的变种二分查找法(折半查找)--二叉查找树

转载请注明出处:http://hi.baidu.com/ipress/

基本思想：
   当静态查找表是有序表，即表中结点是按关键字有序，并采用顺序存储结构时，可用折半查找法。
   折半查找的查找的过程是：先确定待查记录所在的范围（区间），然后逐步缩小查找范围，直到找到该记录或者找不到为止。所谓"折半"的含义是指，先将给定值和所查区间中间位置的记录的关键字进行比较，若相等，则查找成功，否则，依给定值大于或小于该关键字继续在后半个区间或前半个区间中进行查找。

在这里我们要讲的则完全不同与此,采用顺序二叉树进行查找,初始化的时候已经按照二分思想插入.

头文件 stdafx.h

// 您可以自由转载该作品,但必须保留原作者声明条款:
// 来源:http://hi.baidu.com/ipress
// 作者:不知所谓 2006-09-25

//C++实现的变种二分查找法(折半查找)

#pragma once

#include <iostream>
#include <tchar.h>

// 以进对结点及树进行定义
class Tree;
class TreeNode
{
public:
friend class Tree;
private:
int data;
int itemid;//编号,按输入的顺序递增
TreeNode *leftTreeNode;
TreeNode *rightTreeNode;
TreeNode(int d=0)
{
   data = 0;
   itemid = d;
   leftTreeNode = 0;
   rightTreeNode = 0;
}
};
class Tree
{
public:
Tree();
~Tree();
int InsertNode(int value = 0);
void DeleteNode(TreeNode * node);
int SearchNode(int value);
private:
TreeNode *root; //根
int count; //记录结点总数
TreeNode *DestinationNode(int d,TreeNode *currentNode);//查找要插入的位置.
TreeNode *DestinationNode(int d);//查找要插入的位置.
};

//****************************************************cpp文件****************************************************

// 您可以自由转载该作品,但必须保留原作者声明条款:
// 来源:http://hi.baidu.com/ipress
// 作者:不知所谓 2006-09-25

//C++实现的变种二分查找法(折半查找)
// 主要是定义了结点TreeNode和树Tree,并提供对树的基本操作,包括查找,删除,插入.
// 构造树的过程描述:用户输入的第一个数所得的结点作为根结点,以后存储结点时,则按如下规则,
// 小于父结点则存放在父结点的左侧,否则在右侧
// 查找规则:从根处开始匹配,如果小于,则往左,否则往右,直到查找结束,查找到则返回该结点的节点编号(itemid),失败则返回0

#include "stdafx.h"
using namespace std;

void main(void)
{
Tree tree;
int d;
cout<<"开始建立树,循环输入10个整数:\n"<<endl;
for(int i=0;i<10;i++)
{
   scanf("%d",&d);
   tree.InsertNode(d);
}
cout<<"请输入要查找的值(如果树中存在N个相同的值,则只返回第一个):\n"<<endl;
cin>>d;

int result = tree.SearchNode(d);

if(result > 0)
{
   cout<<"查找成功,该数值位于编号为 "<<result<<" 结点上";
   //cout<<result<<endl;
}
else
{
   cout<<"查找失败."<<endl;
}

cin.get();
cin.get();
}

//插入结点到树
int Tree::InsertNode(int value)
{
count++;
TreeNode *tn = new TreeNode(value);
tn->itemid = count;
tn->data = value;

if(root == NULL)
{
   root = tn;
}
else
{
   TreeNode *ctn = DestinationNode(value);
   if (ctn != NULL)
   {
    if (ctn->data > value)
    {
     ctn ->leftTreeNode = tn;
    }
    else
    {
     ctn ->rightTreeNode = tn;
    }
   }
}
return count;
}
//从指定结点开始遍历树
TreeNode * Tree::DestinationNode(int d,TreeNode *currentNode)
{
TreeNode *tn = currentNode;

if (tn == NULL)
{
   return tn;
}

if (tn->data > d)
{
   if( tn->leftTreeNode != NULL)
    return DestinationNode(d,tn->leftTreeNode);
   else
    return tn;
}
else
{
   if( tn->rightTreeNode != NULL)
    return DestinationNode(d,tn->rightTreeNode);
   else
    return tn;
}
}
//从根点遍历树
TreeNode * Tree::DestinationNode(int d)
{
return DestinationNode(d,root);
}

//value为需要查找的值,返回值为节点的itemid值
int Tree::SearchNode(int value)
{
TreeNode *tn = root;

while (tn)
{
   if(tn->data == value)
   {
    return tn->itemid;
   }

   if(tn->data > value)
   {
    tn = tn->leftTreeNode;
   }
   else
   {
    tn = tn->rightTreeNode;
   }
}
return 0;
}
//从结点node处开始删除节点,真正的删除顺序是从叶子开始的.
void Tree::DeleteNode(TreeNode *node)
{
//cout<<"删除"<<node->itemid<<endl;
if (node != NULL)
{
   if (node->leftTreeNode != NULL)//删除左节点
    DeleteNode(node->leftTreeNode);
   if (node->rightTreeNode != NULL)//删除右节点
    DeleteNode(node->rightTreeNode);
   delete node;
   node = 0;
   count--;
}
}
Tree::Tree()
{
root = 0;
count = 0;
}
Tree::~Tree()
{
DeleteNode(root);
//cin.get();
}