转载请注明出处: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();
}
相关推荐
折半查找(二分查找)折半查找(二分查找)折半查找(二分查找)折半查找(二分查找)折半查找(二分查找)折半查找(二分查找)
二叉排序树 折半查找
顺序查找表 二分查找表 折半查找表 二叉排序树 C#源代码 注意二叉排序树只实现了查找和插入算法,使用Visual Studio 2008开发
中序遍历 二叉查找树 折半查找,适合初学者。
数据结构课程设计-综合查找算法(顺序查找、折半查找、二叉排序树、哈希表) 可以在Microsoft Visual C++ 上运行没有错误 包括论文word文档,答辩的ppt等
C++数据结构折半查找法二分查找法,算法设计新颖,有利于数据结构初学者的学习!
实验:实现顺序查找,折半查找,二叉排序树,哈希表实验原理:
代码和讲解 字符串,模式匹配,BF模式匹配,算法 查找(顺序,折半,插值,斐波那契,分块,二叉排序树,二叉平衡树,B树,散列表)代码和讲解,内容详细全面,通俗易懂,通过测试,代码可以直接使用,方便大家学习.
折半查找、二叉排序树的建立、查找与删除、链式哈希表的建立与查找: 1————建立有序表———— 2————折半查找————— 3————建立二叉排序树—— 4————二叉排序树查找—— 5————二叉排序树...
二叉查找树 C++源代码 数据结构,理论知识参见 数据结构基础 张力译版
折半查找算法,c、c++,数据结构课本中讲解的算法实现。
单链表的基本操作,二叉树的遍历,折半查找和二叉排序树,内部排序等共四个实验的实现过程。
C#实现 二分查找 折半查找 visual studio 2012开发环境 具有图形化界面
数据结构实验恢复好的好的天河体育华图教育 用途广泛沟通好的都挺好听氧化铁红有好有坏教育局规划分局依据应用统计
主要为大家详细介绍了C语言实现顺序表的顺序查找和折半查找,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
C语言是一门通用计算机编程语言,广泛应用于底层开发。C语言的设计目标是提供一种能以简易的方式编译、处理低级存储器、产生少量的机器码
查找问题(顺序查找法, 折半查找法,)基本思想:一列数放在数组a(1)---a(n)中,待查找的数放在x 中,把x与a数组中的元素从头到尾一一进行比较查找。用变量p表示a数组元素下标,p初值为1,使x与a(p)比较,如果x不等于a...
本文实例讲述了C++二分查找(折半查找)算法。分享给大家供大家参考,具体如下: 二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。 因此,折半查找...
顺序查找、二分查找、插值查找、动态查找(数组实现、链表实现)
{ /* 利用折半查找法查找合适位置*/ mid=(low+high)/2; /* 计算当前查找部分的中间位置*/ if(item[mid]) high=mid-1; /* 准备查找前半部分*/ else low=mid+1; /* 准备查找后半部分*/ } for(j=n;j>=low;j--) ...