文档章节

二叉查找树

 悠米海
发布于 2015/02/13 16:23
字数 367
阅读 100
收藏 3
#include <iostream>
#include <string>
using namespace std;

typedef struct BiTNode
{
    int		data;
    int		flag;
    BiTNode *lchild,*rchild;
} BTNode,BTree;

//二叉排序树的查找非递归算法
//在二叉排序树T中查找关键字为key的元素,若找到返回true,
//否则返回false.
bool SearchBST(BTree *T,int key)
{
    BTree *p = T;
    while(p)
    {
        if(p->data == key)
		{
            return true;
		}
        p = (key < p->data) ? p->lchild:p->rchild;
    }
    return false;
}

//二叉排序树的查找递归算法
//在二叉排序树T中查找关键字为key的元素,若找到返回true,
//否则返回false.
bool SearchBST2(BTree *T,int key)
{
    BTree *p=T;
    if(p == NULL)
	{
        return false;
	}
    else if(p->data == key)
	{
        return true;
	}
    else if(key > p->data)
	{
        return SearchBST2(p->rchild, key);
	}
    else
	{
        return SearchBST2(p->lchild, key);
	}
}

//建立二叉排序树
//当二叉排序树T中不存在关键字为key的元素时,插入key,并返回树的根,
//否则不插入,并返回树的根。
BTree* InsertBST(BTree *T,int key)
{
    BTree *f=T,*p=T;
    while(p != NULL)
    {
        if(p->data == key)
		{
			return T;
		}
        f = p;				//用f记下查找路径上的最后一个访问的节点
        p = (key < p->data)? p->lchild:p->rchild;
    }
    p = new BTNode();
    p->data = key;
    p->lchild = p->rchild = NULL;
    if(T == NULL)
	{
        T = p;
	}
    else if(key < f->data)
	{
        f->lchild = p;
	}
    else
	{
        f->rchild = p;
	}
    return T;
}

//递归中序遍历
void InOrderDisplay(BTree *T)
{
    if(T != NULL)
    {
        InOrderDisplay(T->lchild);
        cout<<T->data<<",";
        InOrderDisplay(T->rchild);
    }
}

//test:
int main()
{
    BTree *tree = NULL;
	string strNode = "";
	int nNode = 0;
	cout<<"请输入数字,esc结束"<<endl;
	while(true)
	{
		cin>>strNode;
		if(strNode == "esc" || strNode == "ESC")
		{
			break;
		}
		nNode = atoi(strNode.c_str());
		if(nNode >= 0)
		{
			tree = InsertBST(tree,nNode);
		}
	}
    InOrderDisplay(tree);
	//SearchBST2(tree,24);
    return 0;
}



© 著作权归作者所有

共有 人打赏支持
上一篇: 几种常见算法
粉丝 12
博文 96
码字总数 37547
作品 0
浦东
程序员
私信 提问
二叉排序树(Binary Sort Tree)

1、定义 二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree)。其定义为:二叉排序树或者是空树,或者是满足如下性质的二叉树: ① 若它的左子树非空,则左子树上所有...

野渡书生
2016/04/28
96
0
算法与数据结构(五)树表的查找

树表的查找 (1)二叉排序树 (2)二叉排序树的操作——查找 (3)二叉排序树的操作——插入 (4)二叉排序树的操作——生成 (5)二叉排序树的操作——删除 (1)二叉排序树 由于线性表的查...

OrdinaryMan
2018/12/01
0
0
算法知识梳理(10) - 二叉查找树

面试算法代码知识梳理系列 算法知识梳理(1) - 排序算法 算法知识梳理(2) - 字符串算法第一部分 算法知识梳理(3) - 字符串算法第二部分 算法知识梳理(4) - 数组第一部分 算法知识梳理(5) - 数...

泽毛
2017/12/18
0
0
深入学习二叉树(四) 二叉排序树

1 前言 数据结构中,线性表分为无序线性表和有序线性表。 无序线性表的数据是杂乱无序的,所以在插入和删除时,没有什么必须遵守的规则,可以插入在数据尾部或者删除在数据尾部。但是在查找的...

进击的Hello_World
2018/05/14
0
0
小蚂蚁学习数据结构(32)——二叉排序树的概念

二叉排序树,定义: 1,若左子树非空,则左子树上所有节点的关键字均小于根节点关键字。 2,若右子树非空,则右子树上所有节点的关键字均大于根节点关键字。 3,左右子树本身又是一颗二叉树。...

嗜学如命的小蚂蚁
2016/02/07
112
0

没有更多内容

加载失败,请刷新页面

加载更多

mysql 查询当天、本周,本月,上一个月的数据

今天 select * from 表名 where to_days(时间字段名) = to_days(now()); 昨天 SELECT * FROM 表名 WHERE TO_DAYS( NOW( ) ) - TO_DAYS( 时间字段名) <= 1 近7天 SELECT * FROM 表名 wher......

BraveLN
今天
2
0
Android Multimedia框架总结(六)C++中MediaPlayer的C/S架构

前面几节中,都是通过java层调用到jni中,jni向下到c++层并未介绍 看下Java层一个方法在c++层 MediaPlayer后续过程 frameworks/av/media/libmedia/MediaPlayer.cpp 找一个我们之前熟悉的setDa...

天王盖地虎626
今天
3
0
【Linux】【MySQL】CentOS7安装最新版MySQL8.0.13(最新版MySQL从安装到运行)

1、前言   框框博客在线报时:2018-11-07 19:31:06   当前MySQL最新版本:8.0.13 (听说比5.7快2倍)   官方之前表示:MySQL 8.0 正式版 8.0.11 已发布,MySQL 8 要比 MySQL 5.7 快 2 ...

Code辉
今天
5
0
oracle dg备库重建redolog:ora-00313,ora-00312

trace文件: Errors in file /crbank/dbs/app/product/diag/rdbms/rdbs/dbs/trace/dbs_mrp0_24445130.trc: ORA-00313: open failed for members of log group 8 of thread 1 ORA-00312: onl......

hnairdb
今天
3
0
深入分析Java I/O的工作机制 (一)

1.Java的I/O类库的基本架构 先说一下什么是类库:可以说是类的集合,类库包括接口、抽象类、具体类等。 I/O是机器获取和交互信息的主要渠道。 java在I/O上也一直在做持续的优化,在1.4版开始...

java菜分享
今天
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部