二叉查找树
二叉查找树
悠米海 发表于3年前
二叉查找树
  • 发表于 3年前
  • 阅读 99
  • 收藏 3
  • 点赞 0
  • 评论 0

标题:腾讯云 新注册用户域名抢购1元起>>>   

#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
×
悠米海
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: