文档章节

二叉查找树

 悠米海
发布于 2015/02/13 16:23
字数 367
阅读 100
收藏 3
点赞 0
评论 0
#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
博文 92
码字总数 37069
作品 0
浦东
程序员

暂无相关文章

如何解决s权限位引发postfix及crontab异常

一、问题现象 业务反馈某台应用服务器,普通用户使用mutt程序发送邮件时,提示“postdrop warning: mail_queue_enter: create file maildrop/713410.6065: Permission denied”,而且普通用法...

问题终结者 ⋅ 31分钟前 ⋅ 0

Unable to load database on disk

由于磁盘空间满了以后,导致zookeeper异常退出,清理磁盘空间后,zk启动报错,信息如下: 2018-06-25 17:18:46,904 INFO org.apache.zookeeper.server.quorum.QuorumPeerConfig: Reading co...

刀锋 ⋅ 50分钟前 ⋅ 0

css3 box-sizing:border-box 实现div一行多列

<!DOCTYPE html><html><head><style> div.container{ background:green; padding:10px 10px;}div.box{box-sizing:border-box;-moz-box-sizing:border-box; /* Fir......

qimh ⋅ 55分钟前 ⋅ 0

Homebrew简介和基本使用

一、Homebrew是什么 Homebrew是一款Mac OS平台下的软件包管理工具,拥有安装、卸载、更新、查看、搜索等很多实用的功能。简单的一条指令,就可以实现包管理,而不用你关心各种依赖和文件路径...

说回答 ⋅ 今天 ⋅ 0

文件压缩和打包zip、tar

第六章 文件压缩和打包 6.5 zip压缩工具 zip命令可以用来解压缩文件,或者对文件进行打包操作。zip是个使用广泛的压缩程序,文件经它压缩后会另外产生具有“.zip”扩展名的压缩文件。 注意:...

弓正 ⋅ 今天 ⋅ 0

vuex

一、状态对象如何赋值给内部对象。三种方式: 1、使用computed赋值,一定要写this,不然找不到$store。 computed:{ count(){ return this.$store.state.count; }} 2、通...

大美琴 ⋅ 今天 ⋅ 0

javaScript 设计模式

1、构造函数模式 ` /** 构造一个动物的函数 */ function Animal(name, color){ this.name = name; this.color = color; this.getName = function(){ return this.name; } } // 实例一个对象 ......

fangPeng_ ⋅ 今天 ⋅ 0

日常嘚瑟:TeamCity构建中解压和打包tar

要弄一个新的构建,很简单,从两个构建的tar格式Artifact中分别取一部分,重新打一个tar。 所以,我去写个脚本用curl下载两个依赖的Artifact,然后解压移动重新打个tar? 开什么玩笑,我的技...

谷永权 ⋅ 今天 ⋅ 0

Istio官方文档中文版

阅读目录 Istio官方文档中文版 回到目录 Istio官方文档中文版 http://istio.doczh.cn/ https://istio.io/docs/concepts/what-is-istio/goals.html 为什么要使用Istio? 在从单体应用程序向分...

xiaomin0322 ⋅ 今天 ⋅ 0

CentOS 7 Omnibus 包安装 GitLab 并汉化记录

系统环境 操作系统:CentOS 7GitLab:gitlab-ce-10.8.4-ce.0.el7.x86_64.rpm 下载Omnibus安装包 使用国内镜像加速下载地址 # wget https://mirrors.tuna.tsinghua.edu.cn/gitlab-ce/yum/el......

admin_qing ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部