查看: 100|回复: 0

二叉树(1)二叉树基本操作通用接口

[复制链接]
发表于 2020-2-16 04:54:06 | 显示全部楼层 |阅读模式
封装二叉树的基本操纵,为 二叉查找(搜索、排序)树,二叉平衡树(AVL 树),红黑树 等提供基础接口。
定义的布局体内里必须至少包含以下名称的成员:
  "key"、"left"、"right"、"parent"。
封装文件名:BinaryTreeOperations.h;名称空间:BTO。
基础接口如下:
  一、遍历操纵:
    ① 先序、中序、后序遍历递归版:
      void preorderTraversal(_Node*, const _Func&);
      void inorderTraversal(_Node*, const _Func&);
      void postorderTraversal(_Node*, const _Func&);
    ② 先序、中序、后序遍历非递归版:
      void iterativePreorderTraversal(_Node*, const _Func&);
      void iterativeInorderTraversal(_Node*, const _Func&);
      void iterativePostorderTraversal(_Node*, const _Func&);
    ③ 层序遍历:
      oid levelTraversal(_Node*, const _Func&);
     阐明:_Func 是函数对象,担当一个 _Node* 参数,更广泛的支持对数据的操纵。

  二、查找操纵:
    ① 查找指定键值的节点 迭代和非迭代版:
      _Node* find(_Node*, const _Ty&);
      _Node* iterativeFind(_Node*, const _Ty&);
    ② 查找最大最小键值的节点:
      _Node* findMaximum(_Node*);
      _Node* findMinimum(_Node*);
    ③ 获取二叉树的深度(层数):
       size_t getLevel(_Node*);

  三、插入操纵:
    std::pair insert(_Node*&, const _Ty&);
    阐明:该操纵不答应插入已经存在的键值,用 std:pair 返回插入情况:乐成则返回 指向插入节点的指针 和 true,失败则返回 nullptr 和 false

  四、拷贝操纵 迭代和非迭代版:
    _Node* copy(_Node*, _Node* _ret = nullptr);
    _Node* iterativeCopy(_Node*, _Node* _ret = nullptr);
    阐明:第一个参数是待拷贝的二叉树、用 ret 返回拷贝后的根节点,调用时 ret 必须指向 nullptr。

  五、清空操纵 递归:
    void clear(_Node*&);

  六、单旋转操纵:
    ① 左旋:_Node* leftRotate(_Node*);
    ② 右旋:_Node* rightRotate(_Node*);
    阐明:伸展树、AVL 树、红黑树 等都需要使用旋转功能,因此提供旋转操纵。
      返回旋转后子树的根节点,以便 AVL 树调解平衡因子 和 红黑树变色 等需求。

测试代码 main.cpp:
  1. #include #include "BinaryTreeOperations.h"using std::cout;using std::endl;templatestruct Node{    _Ty key;    Node* left = nullptr;    Node* right = nullptr;    Node* parent = nullptr;    Node(const _Ty& _key) :key(_key) {}};int main(){    Node* root = nullptr;    auto il = { 5,3,7,4,8,1,0,9,2,6 };    for (auto& x : il) BTO::insert(root, x);    cout left);    clear(_node->right);    delete _node;    _node = nullptr;}/* Rotate operation */template_Node* BTO::leftRotate(_Node* _node){    _Node* rightNode = _node->right;    if (_node->parent != nullptr)    {        if (_node->parent->right == _node) _node->parent->right = rightNode;        else _node->parent->left = rightNode;    }    rightNode->parent = _node->parent;    _node->right = rightNode->left;    if (rightNode->left != nullptr) rightNode->left->parent = _node;    _node->parent = rightNode;    rightNode->left = _node;    return rightNode;}template_Node* BTO::rightRotate(_Node* _node){    _Node* leftNode = _node->left;    if (_node->parent != nullptr)    {        if (_node->parent->left == _node) _node->parent->left = leftNode;        else _node->parent->right = leftNode;    }    leftNode->parent = _node->parent;    _node->left = leftNode->right;    if (leftNode->right != nullptr) leftNode->right->parent = _node;    _node->parent = leftNode;    leftNode->right = _node;    return leftNode;}#endif // !__BINARY_TREE_OPERATIONS_H__
复制代码

相关技术服务需求,请联系管理员和客服QQ:2753533861或QQ:619920289
您需要登录后才可以回帖 登录 | 用户注册

本版积分规则

帖子推荐:
客服咨询

QQ:2753533861

服务时间 9:00-22:00

快速回复 返回顶部 返回列表