bsttree.cpp

来自「此代码运行于visual c++ 6.0的环境下」· C++ 代码 · 共 67 行

// BstTree.cpp: implementation of the BstTree class.
//
//////////////////////////////////////////////////////////////////////
#include "stdafx.h"
#include "BstTree.h"


//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////


//插入一个新结点的函数
bool CBstTree::insert(const CBstTreeNode & node){
	if( root == NULL ){  //如果树为空
		root = new CBstTreeNode(node);//根等于新插入结点
		m_nTotalNodes++;//结点个数加1
		return true;
	}
	CBstTreeNode * ptr = root;//移动结点指针指向根结点
	while(1){
		if( ptr->Key.compare(node.Key) == 0 )//如果树中存在与要插入树结点的关键词相同
			return false;					 //不插入，返回	
		if( ptr->Key.compare(node.Key) > 0 ){//如果比当前的树结点的关键词小
			if(ptr->left == NULL){//如果当前结点无左子女
				ptr->left = new CBstTreeNode(node);//当前结点的左子女指向新插入结点
				m_nTotalNodes++;//结点个数加1
				return true;
			}
			ptr = ptr->left;//如果有左子女，指针指向其左子女，继续循环寻找应插入的位置
		}
		else {//如果比当前的树结点的关键词大
			if(ptr->right == NULL){//如果当前结点无右子女
				ptr->right = new CBstTreeNode(node);//当前结点的右子女指向新插入的结点
				m_nTotalNodes++;//结点个数加1
				return true;
			}
			ptr = ptr->right;//如果有右子女，指针指向其右子女，继续循环寻找应该插入的位置
		}
	}

	return false;
}


//返回关键词与参数所给的关键词相同的结点的指针，如果找不到返回NULL
CBstTreeNode * CBstTree::find(string s){
	if( root != NULL ){//如果树不为空
		CBstTreeNode * subroot = root;//移动指针指向树根结点
		while( subroot != NULL ){//当移动指针不为空时
			if( subroot->Key.compare(s) == 0 )//如果找到返回当前指针
				return subroot;
			if( subroot->Key.compare(s) < 0 )//如果比当前结点的关键词大
				subroot = subroot->right;//进入右子树继续寻找
			else subroot = subroot->left;//否则进入左子树寻找
		}
	}
	return NULL;//没找到返回NULL
}

//判断树中是否存在关键词与参数所给的关键词相同的树结点
bool CBstTree::IsExist(string s){ 
	return find(s)==NULL?false:true;
}