博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
二叉搜索树(递归实现)
阅读量:6604 次
发布时间:2019-06-24

本文共 5839 字,大约阅读时间需要 19 分钟。

#include 
#include
#include
using namespace std;template
class BST{
private: struct Node{
Key key; Value value; Node *left; Node *right; Node(Key key, Value value){ this->key = key; this->value = value; this->left = this->right = NULL; } Node(Node *node){ this->key = node->key; this->value = node->value; this->left = node->left; this->right = node->right; } }; Node *root; int count;public: BST(){ root = NULL; count = 0; } ~BST(){ destroy( root ); } int size(){ return count; } bool isEmpty(){ return count == 0; }int main() { srand(time(NULL)); BST
bst = BST
(); int n = 10000; for( int i = 0 ; i < n ; i ++ ){ int key = rand()%n; // 为了后续测试方便,这里value值取和key值一样 int value = key; //cout<
<<" "; bst.insert(key,value); } // test remove // remove elements in random order int order[n]; for( int i = 0 ; i < n ; i ++ ) order[i] = i; shuffle( order , n ); for( int i = 0 ; i < n ; i ++ ) if( bst.contain( order[i] )){ bst.remove( order[i] ); cout<<"After remove "<
<<" size = "<
<

1. 插入insert

public:void insert(Key key, Value value){     root = insert(root, key, value);}private:// 向以node为根的二叉搜索树中,插入节点(key, value)// 返回插入新节点后的二叉搜索树的根Node* insert(Node *node, Key key, Value value){    if( node == NULL ){      // 如果节点为空,就在此节点处加入x信息        count ++;        return new Node(key, value);    }    if( key == node->key )          node->value = value;  //如果相等,就把频率加1    else if( key < node->key )        node->left = insert( node->left , key, value);  // 如果x小于节点的值,就继续在节点的左子树中插入x    else    // key > node->key            node->right = insert( node->right, key, value);  // 如果x大于节点的值,就继续在节点的右子树中插入x    return node;}复制代码

2. 包含contain

bool contain(Key key){    return contain(root, key);}// 查看以node为根的二叉搜索树中是否包含键值为key的节点bool contain(Node* node, Key key){    if( node == NULL )        return false;    if( key == node->key )        return true;    else if( key < node->key )        return contain( node->left , key );    else // key > node->key        return contain( node->right , key );}复制代码

3. 搜索search

Value* search(Key key){    return search( root , key );}// 在以node为根的二叉搜索树中查找key所对应的valueValue* search(Node* node, Key key){    if( node == NULL )        return NULL;    if( key == node->key )        return &(node->value);    else if( key < node->key )        return search( node->left , key );    else // key > node->key        return search( node->right, key );}复制代码

4. 遍历

  • 前序遍历preOrder
void preOrder(){    preOrder(root);}// 对以node为根的二叉搜索树进行前序遍历void preOrder(Node* node){    if( node != NULL ){        cout<
key<
left); preOrder(node->right); }}复制代码
  • 中序遍历inOrder
void inOrder(){    inOrder(root);}// 对以node为根的二叉搜索树进行中序遍历void inOrder(Node* node){    if( node != NULL ){        inOrder(node->left);        cout<
key<
right); }}复制代码
  • 后序遍历postOrder
void postOrder(){    postOrder(root);}// 对以node为根的二叉搜索树进行后序遍历void postOrder(Node* node){    if( node != NULL ){        postOrder(node->left);        postOrder(node->right);        cout<
key<
  • 层序遍历levelOrder
void levelOrder(){    queue
q; q.push(root); while( !q.empty() ){ Node *node = q.front(); q.pop(); cout<
key<
left ) q.push( node->left ); if( node->right ) q.push( node->right ); }}复制代码

5. 寻找最小/大键值

Key minimum(){    assert( count != 0 );    Node* minNode = minimum( root );    return minNode->key;}// 在以node为根的二叉搜索树中,返回最小键值的节点Node* minimum(Node* node){    if( node->left == NULL )        return node;    return minimum(node->left);}复制代码
Key maximum(){    assert( count != 0 );    Node* maxNode = maximum(root);    return maxNode->key;}// 在以node为根的二叉搜索树中,返回最大键值的节点Node* maximum(Node* node){    if( node->right == NULL )        return node;    return maximum(node->right);}复制代码

6. 从二叉树中删除最小/大值所在节点

void removeMin(){    if( root )        root = removeMin( root );}// 删除掉以node为根的二分搜索树中的最小节点// 返回删除节点后新的二分搜索树的根Node* removeMin(Node* node){    if( node->left == NULL ){        Node* rightNode = node->right;        delete node;        count --;        return rightNode;    }    node->left = removeMin(node->left);    return node;}复制代码
void removeMax(){    if( root )        root = removeMax( root );}// 删除掉以node为根的二分搜索树中的最大节点// 返回删除节点后新的二分搜索树的根Node* removeMax(Node* node){    if( node->right == NULL ){        Node* leftNode = node->left;        delete node;        count --;        return leftNode;    }    node->right = removeMax(node->right);    return node;}复制代码

7. 删除remove

void remove(Key key){    root = remove(root, key);}// 删除掉以node为根的二分搜索树中键值为key的节点// 返回删除节点后新的二分搜索树的根Node* remove(Node* node, Key key){    if( node == NULL )        return NULL;    if( key < node->key ){        node->left = remove( node->left , key );        return node;    }    else if( key > node->key ){        node->right = remove( node->right, key );        return node;    }    else{   // key == node->key        if( node->left == NULL ){            Node *rightNode = node->right;            delete node;            count --;            return rightNode;        }        if( node->right == NULL ){            Node *leftNode = node->left;            delete node;            count--;            return leftNode;        }        // node->left != NULL && node->right != NULL        Node *successor = new Node(minimum(node->right));        count ++;        successor->right = removeMin(node->right);        successor->left = node->left;        delete node;        count --;        return successor;    }}复制代码

转载地址:http://egfso.baihongyu.com/

你可能感兴趣的文章
《Java并发编程实战》第十一章 性能与可伸缩性 读书笔记
查看>>
DateTime格式大全
查看>>
no identities are available for signing
查看>>
为什么匿名内部类参数必须为final类型
查看>>
FileZilla简单介绍及运用
查看>>
建立第一个Sencha Touch应用
查看>>
Yarn的ApplicationMaster管理
查看>>
javascript 和 jquery插件开发
查看>>
数论 - 欧拉函数模板题 --- poj 2407 : Relatives
查看>>
angular学习笔记(三十)-指令(7)-compile和link(1)
查看>>
Linux Shell文件差集
查看>>
双网卡绑定-bond0
查看>>
JStack分析cpu消耗过高问题
查看>>
[solr] - IKAnalyzer 扩展分词库
查看>>
Mining 影响数据挖掘结果的 5 方面
查看>>
shell脚本执行时报"bad interpreter: Text file busy"的解决方法
查看>>
MVC4 WebAPI
查看>>
同步两台linux服务器时间同步方案
查看>>
RMSE均方根误差学习笔记
查看>>
Rhythmbox乱码的解决的方法
查看>>