文档章节

二叉查找树

 悠米海
发布于 2015/02/13 16:23
字数 367
阅读 106
收藏 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;
}



上一篇: 几种常见算法
粉丝 13
博文 97
码字总数 37819
作品 0
浦东
程序员
私信 提问
加载中
请先登录后再评论。
Flappy Bird(安卓版)逆向分析(一)

更改每过一关的增长分数 反编译的步骤就不介绍了,我们直接来看反编译得到的文件夹 方法1:在smali目录下,我们看到org/andengine/,可以知晓游戏是由andengine引擎开发的。打开/res/raw/at...

enimey
2014/03/04
6.2K
18
C++模板库--C++ B-tree

这是一个google开源的C++模板库,实现了基于B-tree数据结构的有序内存容器。类似于STL的map、set、multimap和multiset模板,C++ B-tree也提供了btreemap、btreeset、btreemultimap和btreemu...

匿名
2013/02/05
3.4K
1
树软辅助设计工具--MTC-2008

树软辅助设计工具不仅是一个软件开发平台,而且是一个设计树形软件的CAD。 树型软件工程方法(简称树软法)以崭新的观念丰富和发展了软件工程方法。树软法定义了系统、事件、任务、作业和语句...

Treesoft
2012/12/06
4K
0
NoSQL 数据服务器--Reveldb

reveldb 一个基于 google leveldb 的 NoSQL 数据服务器,网络连接采用了 libevent 的 HTTP 接口,因此 reveldb 天生就适合处理 HTTP 请求。但更确切地说,reveldb 并没有直接采用 libevent 的...

大卷卷
2013/01/04
1.3K
0
脚本语言--Gui4Cli

Gui4Cli 是一种易学的脚本语言,可以让任何人,不管是编程熟手还是 菜鸟 都可以在几分钟内编写一个界面。你所要做的就是使用 Gui4Cli 语言 (简单易学)编写一个脚本(普通的文本文件)然后运...

匿名
2013/05/08
2.4K
0

没有更多内容

加载失败,请刷新页面

加载更多

红队之windows用户和组

目录 0x01 用户账户和组策略 0x02 Windows中的访问控制 0x03 安全标识符SID 0x04 用户账户控制(UAC) 用户帐户 用户帐户是对计算机用户身份的标识,本地用户帐户、密码存在本地计算机上,只...

黑白天安全团队
昨天
15
0
厉害了!百度智能云NIRO Pro智能机器人半年内连获三项产品设计大奖

短短半年内,百度智能云NIRO Pro智能机器人连获三项产品设计大奖,其中包括有“设计界奥斯卡”之称的德国红点奖,成功引领了全球助理机器人的工业设计和发展趋势风向标。红点奖评委这样评价,...

百度智能云
2019/12/04
5
0
StringBuider 在什么条件下、如何使用效率更高?

作者:后青春期的Keats cnblogs.com/keatsCoder/p/13212289.html 引言 都说 StringBuilder 在处理字符串拼接上效率要强于 String,但有时候我们的理解可能会存在一定的偏差。最近我在测试数据...

Object_Man
今天
11
0
发布更新|腾讯云 Serverless 产品动态 20200813

一、云函数 SCF + Ckafka 联合转储方案正式发布 发布时间: 2020-08-06 产品背景: SCF + Ckafka 联合转储方案可以帮忙用户节省使用与开发成本,用户可以将 Ckafka 消息转储同步转储至消息队...

腾讯云Serverless
44分钟前
5
0
如何正确强制执行Git推送? - How do I properly force a Git push?

问题: I've set up a remote non-bare "main" repo and cloned it to my computer. 我已经建立了一个远程的非裸露的“主”仓库,并将其克隆到我的计算机上。 I made some local changes, u......

javail
46分钟前
14
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部