文档章节

二叉查找树

 悠米海
发布于 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
博文 94
码字总数 37254
作品 0
浦东
程序员
私信 提问
二叉排序树(Binary Sort Tree)

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

野渡书生
2016/04/28
96
0
算法知识梳理(10) - 二叉查找树

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

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

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

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

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

嗜学如命的小蚂蚁
2016/02/07
112
0
数据结构-二叉搜索树的实现

定义 二叉搜索树(Binary Search Tree,BST),也称为二叉排序树或二叉查找树。 相较于普通的二叉树,非空的二叉搜索树有如下性质: 非空左子树的所有键值小于其根结点的键值; 非空右子树的所有...

IAM四十二
2017/10/27
0
0

没有更多内容

加载失败,请刷新页面

加载更多

docker部署springboot项目

安装docker 菜鸟教程 springboot项目 maven依赖 <?xml version="1.0" encoding="UTF-8"?><project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001......

yimingkeji
43分钟前
4
0
ios多个target

1.建立3个target,分别为heroone,heroone test,heroone dev;分别为正式环境,test环境,dev环境 2.注意取消掉autocreate以防止名字不对,分别以Duplicate的方式建立另外两个scheme 3.创建...

HeroHY
今天
5
0
php获取客户端IP

php获取客户端IP 首先先阅读关于IP真实性安全的文章:如何正確的取得使用者 IP? 「任何從客戶端取得的資料都是不可信任的!」 HTTP_CLIENT_IP头是有的,但未成标准,不一定服务器都实现。 ...

DrChenXX
昨天
0
0
. The valid characters are defined in RFC 7230 and RFC 问题

通过这里的回答,我们可以知道: Tomcat在 7.0.73, 8.0.39, 8.5.7 版本后,添加了对于http头的验证。 具体来说,就是添加了些规则去限制HTTP头的规范性 参考这里 具体来说: org.apache.tom...

west_coast
昨天
1
0
刷leetcode第704题-二分查找

今天双十一买的算法书到货了,路上刷到有人说的这个题,借(chao)鉴(xi)一下别人的思路,这个是C++标准库里面的经典方法,思路精巧,优雅好品味 int search(int* nums, int numsSize, in...

锟斤拷烫烫烫
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部