【牛客带你学编程C++方向】项目练习第10期（截止6.29）

C++方向活动帖：【牛客带你学编程】【C++方向】0基础小白入门培养计划！

牛客带你学编程活动总贴：【牛客带你学编程】0基础小白入门培养计划！

C++项目练习：第10期

练习时间：6月15日-6月29日（2周）

活动规则：

每一期一个项目，届时会开新帖发布
学员直接将答案提交到该贴评论区即可
两周后，公布导师参考答案
导师评选出当期最佳代码（将设置为精彩回复）

奖励：牛客大礼包一份（牛客定制水杯牛客定制笔牛客定制程序员徽章滑稽抱枕）

参与方式：直接将你的代码回复到本帖评论区

----------------------------------------------------

本期题目：

C++ STL中map和set存储方式都是使用红黑树的方式，其实质都是二叉搜索树，实现二叉搜索树的数据结构。

可以参考博客：https://www.cnblogs.com/skywang12345/p/3624291.html

节点定义如下：

template <class T>
class BSTNode{
    public:
        T key;            //关键字(键值)
        BSTNode *left;    //左孩子
        BSTNode *right;    //右孩子
        BSTNode *parent;//父结点
 
        BSTNode(T value, BSTNode *p, BSTNode *l, BSTNode *r):
            key(value),parent(),left(l),right(r) {}
};
template <class T>
class BSTree {
    private:
        BSTNode<T> *mRoot;    //根结点
 
    public:
        BSTree();
        ~BSTree();
        //前序遍历"二叉树"
        void preOrder();
        //中序遍历"二叉树"
        void inOrder();
        //后序遍历"二叉树"
        void postOrder();
        // (递归实现)查找"二叉树"中键值为key的节点
        BSTNode<T>* search(T key);
        // (非递归实现)查找"二叉树"中键值为key的节点
        BSTNode<T>* iterativeSearch(T key);
        //查找最小结点：返回最小结点的键值。
        T minimum();
        //查找最大结点：返回最大结点的键值。
        T maximum();
        //找结点(x)的后继结点。即，查找"二叉树中数据值大于该结点"的"最小结点"。
        BSTNode<T>* successor(BSTNode<T> *x);
        //找结点(x)的前驱结点。即，查找"二叉树中数据值小于该结点"的"最大结点"。
        BSTNode<T>* predecessor(BSTNode<T> *x);
        //将结点(key为节点键值)插入到二叉树中
        void insert(T key);
        //删除结点(key为节点键值)
        void remove(T key);
 
        //销毁二叉树
        void destroy();
        //打印二叉树
        void print();
    private:
        //前序遍历"二叉树"
        void preOrder(BSTNode<T>* tree) const;
        //中序遍历"二叉树"
        void inOrder(BSTNode<T>* tree) const;
        //后序遍历"二叉树"
        void postOrder(BSTNode<T>* tree) const;
        // (递归实现)查找"二叉树x"中键值为key的节点
        BSTNode<T>* search(BSTNode<T>* x, T key) const;
        // (非递归实现)查找"二叉树x"中键值为key的节点
        BSTNode<T>* iterativeSearch(BSTNode<T>* x, T key) const;
        //查找最小结点：返回tree为根结点的二叉树的最小结点。
        BSTNode<T>* minimum(BSTNode<T>* tree);
        //查找最大结点：返回tree为根结点的二叉树的最大结点。
        BSTNode<T>* maximum(BSTNode<T>* tree);
        //将结点(z)插入到二叉树(tree)中
        void insert(BSTNode<T>* &tree, BSTNode<T>* z);
        //删除二叉树(tree)中的结点(z)，并返回被删除的结点
        BSTNode<T>* remove(BSTNode<T>* &tree, BSTNode<T> *z);
        //销毁二叉树
        void destroy(BSTNode<T>* &tree);
        //打印二叉树
        void print(BSTNode<T>* tree, T key, int direction);
};

参与方式：直接将你的代码回复到本帖评论区

参考答案：https://www.nowcoder.com/discuss/85581

全部评论

推荐最新楼层

cj-123

武汉科技大学 C++

#include "BSTree.h" #include<iostream> using namespace std; //前序遍历二叉树 template<class T> void BSTree<T>::preOrder(BSTNode<T> *tree) const { if(tree!=nullptr) { cout<<tree->key<<" "; preOrder(tree->left); preOrder(tree->right); } } template<class T> void BSTree<T>::preOrder() { preOrder(mRoot); } //中序遍历二叉树 template<class T> void BSTree<T>::inOrder(BSTNode<T> *tree) const { if(tree!=nullptr) { inOrder(tree->left); cout<<tree->key<<" "; inOrder(tree->right); } } template<class T> void BSTree<T>::inOrder() { inOrder(mRoot); } //后序遍历二叉树 template<class T> void BSTree<T>::postOrder(BSTNode<T> *tree) const { if(tree!=nullptr) { postOrder(tree->left); postOrder(tree->right); cout<<tree->key<<" "; } } template<class T> void BSTree<T>::postOrder() { postOrder(mRoot); } //递归实现查找二叉树中键值为key的节点 template<class T> BSTNode<T>* BSTree<T>::search(BSTNode<T> *x, T key)const { if(x->key==key) return x; else if(x->key>key) return search(x->left,key); else return search(x->right,key); } template<class T> BSTNode<T>* BSTree<T>::search(T key) { return search(mRoot,key); } //非递归实现查找二叉树中键值为key的节点 template<class T> BSTNode<T>* BSTree<T>::iterativeSearch(BSTNode<T> *x, T key)const { while(x!=nullptr) { if(x->key==key) return x; else if(x->key>key) x=x->left; else x=x->right; } return x; } template<class T> BSTNode<T>* BSTree<T>::iterativeSearch(T key) { return iterativeSearch(mRoot,key); } //查找最小节点，返回最小节点 template<class T> BSTNode<T>* BSTree<T>::minimum(BSTNode<T> *tree) { while(tree->left!=nullptr) { tree=tree->left; } return tree; } template<class T> T BSTree<T>::minimum() { return minimum(mRoot)->key; } //查找最大节点，返回最大节点 template<class T> BSTNode<T>* BSTree<T>::maximum(BSTNode<T> *tree) { while(tree->right!=nullptr) { tree=tree->right; } return tree; } template<class T> T BSTree<T>::maximum() { return maximum(mRoot)->key; } //插入节点到二叉搜索树 template<class T> void BSTree<T>::insert(BSTNode<T> *&tree, BSTNode<T> *z) { if(tree==nullptr) { tree=z; return; } BSTNode<T>* p=nullptr; BSTNode<T>* tmp=tree; while(tmp) { if(tmp->key==z->key) return; p=tmp; if(tmp->key>z->key) { tmp=tmp->left; } else { tmp=tmp->right; } } if(p->key>z->key) p->left=z; else p->right=z; } template<class T> void BSTree<T>::insert(T key) { BSTNode<T>* node=new BSTNode<T>(key); insert(mRoot,node); } //删除节点 template<class T> BSTNode<T>* BSTree<T>::remove(BSTNode<T> *&tree, BSTNode<T> *z) { if(tree==nullptr) return; BSTNode<T>* pcur=tree; while(pcur!=nullptr && pcur->key!=z->key) { if(pcur->key>z->key) pcur=pcur->left; else pcur=pcur->right; } if(pcur==nullptr) return; if(!pcur->left && !pcur->right) { delete pcur; pcur=nullptr; return; } if(pcur->left && pcur->right) { BSTNode<T>* tmp=pcur->right; while(tmp->left) tmp=tmp->left; if(pcur->right=tmp) { pcur->right=tmp->right; delete tmp; tmp=nullptr; return; } BSTNode<T>* node=pcur; pcur=tmp; tmp=node; delete tmp; tmp=nullptr; return; } if(pcur->left) { BSTNode<T>* p=pcur->parent; if(p==nullptr) { tree=pcur->left; delete pcur; pcur=nullptr; return; } if(p->right==pcur) { p->right=pcur->left; } if(p->left==pcur) { p->left=pcur->left; } return; } if(pcur->right) { BSTNode<T>* p=pcur->parent; if(p==nullptr) { tree=pcur->right; delete pcur; pcur=nullptr; return; } if(p->right==pcur) { p->right=pcur->right; } if(p->left==pcur) { p->left=pcur->right; } return; } } template<class T> void BSTree<T>::remove(T key) { BSTNode<T>* node=new BSTNode<T>(key); remove(mRoot,node); } //销毁二叉树 template<class T> void BSTree<T>::destory(BSTNode<T> *&tree) { if(tree) { BSTNode<T>* l=tree->left; BSTNode<T>* r=tree->right; delete tree; destory(l); destory(r); } } template<class T> void BSTree<T>::destory() { destory(mRoot); } //查找节点x的后继节点 template<class T> BSTNode<T>* BSTree<T>::successor(BSTNode<T> *x) { if(x==nullptr || x->right==nullptr) return nullptr; BSTNode<T>* node=x->right; while(node->left) node=node->left; return node; } //查找节点x的前驱节点 template<class T> BSTNode<T>* BSTree<T>::predecessor(BSTNode<T> *x) { if(x==nullptr) return nullptr; if(x->left) { x=x->left; while(x->right) x=x->right; return x; } BSTNode<T>* p=x->parent; if(p==nullptr) return p; if(p->right==x) return p; if(p->left==x) { BSTNode<T>* q=p->parent; while(q->right!=p) { p=q; q=p->parent; } return q; } }

点赞回复分享

发布于 2018-07-05 10:58