二叉樹（1）二叉樹基本操作通用介面

来源:https://www.cnblogs.com/teternity/archive/2020/02/06/BinaryTreeOperations.html
-Advertisement-
Play Games

二叉樹的基本操作，為 二叉查找（搜索、排序）樹、二叉平衡樹（AVL樹）、紅黑樹 等提供基礎介面。 名稱空間：namespace BTO 基礎介面如： ① 遍歷操作： 遞歸 和 非遞歸 版本的 先序、中序、後序 遍歷。 層序遍歷。 介面原型：void xxxTraversal(_Node*& _nod ...


封裝二叉樹的基本操作，為 二叉查找（搜索、排序）樹，二叉平衡樹（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<_Node*, bool> 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：

 

#include <iostream>
#include "BinaryTreeOperations.h"

using std::cout;
using std::endl;

template<typename _Ty>
struct Node
{
    _Ty key;
    Node* left = nullptr;
    Node* right = nullptr;
    Node* parent = nullptr;
    Node(const _Ty& _key) :key(_key) {}
};

int main()
{
    Node<int>* root = nullptr;
    auto il = { 5,3,7,4,8,1,0,9,2,6 };
    for (auto& x : il) BTO::insert(root, x);

    cout << "preorderTraversal：" << endl;
    BTO::preorderTraversal(root, [](const Node<int>* _node) { cout << _node->key << " "; });
    cout << endl;
    BTO::iterativePreorderTraversal(root, [](const Node<int>* _node) { cout << _node->key << " "; });
    cout << endl << endl;
    cout << "inorderTraversal：" << endl;
    BTO::inorderTraversal(root, [](const Node<int>* _node) { cout << _node->key << " "; });
    cout << endl;
    BTO::iterativeInorderTraversal(root, [](const Node<int>* _node) { cout << _node->key << " "; });
    cout << endl << endl;
    cout << "postorderTraversal：" << endl;
    BTO::postorderTraversal(root, [](const Node<int>* _node) { cout << _node->key << " "; });
    cout << endl;
    BTO::iterativePostorderTraversal(root, [](const Node<int>* _node) { cout << _node->key << " "; });
    cout << endl << endl;
    cout << "levelTraversal：" << endl;
    BTO::levelTraversal(root, [](const Node<int>* _node) { cout << _node->key << " "; });
    cout << endl << endl;

    cout << "BTO::find(root, 5)->key：" << endl;
    auto p5 = BTO::find(root, 5);
    if (p5 != nullptr) cout << p5->key << ", " << BTO::iterativeFind(root, 5)->key << endl;
    else cout << "nullptr" << endl;
    cout << "BTO::find(root, 11)->key：" << endl;
    auto p11 = BTO::find(root, 11);
    if (p11 != nullptr) cout << p11->key << ", " << BTO::iterativeFind(root, 11)->key << endl;
    else cout << "nullptr" << endl << endl;

    cout << "BTO::findMaximum(root)->key：" << endl;
    cout << BTO::findMaximum(root)->key << endl;
    cout << "BTO::findMinimum(root)->key：" << endl;
    cout << BTO::findMinimum(root)->key << endl << endl;

    auto root2 = BTO::copy(root);
    auto root3 = BTO::copy(root);
    cout << "BTO::getLevel(root)：" << endl;
    cout << BTO::getLevel(root) << endl;
    cout << "BTO::getLevel(root2)：" << endl;
    cout << BTO::getLevel(root2) << endl;
    cout << "BTO::getLevel(root3)：" << endl;
    cout << BTO::getLevel(root3) << endl << endl;

    BTO::clear(root);
    BTO::clear(root2);
    BTO::clear(root3);

    return 0;
}

 

頭文件 BinaryTreeOperations.h：

#pragma once
#ifndef __BINARY_TREE_OPERATIONS_H__
#define __BINARY_TREE_OPERATIONS_H__


/*
    The node must have members which are named:
        "key"、"left"、"right"、"parent"
*/


#include <stack>
#include <queue>
#include <utility>
namespace BTO
{
    /* Traversal operations */
    // Recursive operations
    template<typename _Node, typename _Func>
    void preorderTraversal(_Node*, const _Func&);
    template<typename _Node, typename _Func>
    void inorderTraversal(_Node*, const _Func&);
    template<typename _Node, typename _Func>
    void postorderTraversal(_Node*, const _Func&);
    // Iterative operations
    template<typename _Node, typename _Func>
    void iterativePreorderTraversal(_Node*, const _Func&);
    template<typename _Node, typename _Func>
    void iterativeInorderTraversal(_Node*, const _Func&);
    template<typename _Node, typename _Func>
    void iterativePostorderTraversal(_Node*, const _Func&);
    // Level traversal
    template<typename _Node, typename _Func>
    void levelTraversal(_Node*, const _Func&);

    /* Find operations */
    template<typename _Node, typename _Ty>
    _Node* find(_Node*, const _Ty&);
    template<typename _Node, typename _Ty>
    _Node* iterativeFind(_Node*, const _Ty&);
    template<typename _Node>
    _Node* findMaximum(_Node*);
    template<typename _Node>
    _Node* findMinimum(_Node*);
    template<typename _Node>
    size_t getLevel(_Node*);

    /* Inset operation */
    template<typename _Node, typename _Ty>
    std::pair<_Node*, bool> insert(_Node*&, const _Ty&);

    /* Copy operation */
    template<typename _Node>
    _Node* copy(_Node*, _Node* _ret = nullptr);
    template<typename _Node>
    _Node* iterativeCopy(_Node*, _Node* _ret = nullptr);

    /* Clear operation */
    template<typename _Node>
    void clear(_Node*&);

    /* Rotate operation */
    template<typename _Node>
    _Node* leftRotate(_Node*);
    template<typename _Node>
    _Node* rightRotate(_Node*);
}

/* Traversal operations */
template<typename _Node, typename _Func>
void BTO::preorderTraversal(_Node* _node, const _Func& _func)
{
    if (_node == nullptr) return;
    _func(_node);
    preorderTraversal(_node->left, _func);
    preorderTraversal(_node->right, _func);
}
template<typename _Node, typename _Func>
void BTO::inorderTraversal(_Node* _node, const _Func& _func)
{
    if (_node == nullptr) return;
    inorderTraversal(_node->left, _func);
    _func(_node);
    inorderTraversal(_node->right, _func);
}
template<typename _Node, typename _Func>
void BTO::postorderTraversal(_Node* _node, const _Func& _func)
{
    if (_node == nullptr) return;
    postorderTraversal(_node->left, _func);
    postorderTraversal(_node->right, _func);
    _func(_node);
}
template<typename _Node, typename _Func>
void BTO::iterativePreorderTraversal(_Node* _node, const _Func& _func)
{
    if (_node == nullptr) return;
    std::stack<_Node*> nodePointers;
    _Node* cur = _node;
    while (cur != nullptr || !nodePointers.empty())
    {
        _func(cur);
        nodePointers.push(cur);
        cur = cur->left;
        while (cur == nullptr && !nodePointers.empty())
        {
            cur = nodePointers.top()->right;
            nodePointers.pop();
        }
    }
}
template<typename _Node, typename _Func>
void BTO::iterativeInorderTraversal(_Node* _node, const _Func& _func)
{
    if (_node == nullptr) return;
    std::stack<_Node*> nodePointers;
    _Node* cur = _node;
    while (cur != nullptr || !nodePointers.empty())
    {
        if (cur->left != nullptr)
        {
            nodePointers.push(cur);
            cur = cur->left;
        }
        else
        {
            _func(cur);
            cur = cur->right;
            while (cur == nullptr && !nodePointers.empty())
            {
                cur = nodePointers.top();
                nodePointers.pop();
                _func(cur);
                cur = cur->right;
            }
        }
    }
}
template<typename _Node, typename _Func>
void BTO::iterativePostorderTraversal(_Node* _node, const _Func& _func)
{
    if (_node == nullptr) return;
    std::stack<_Node*> nodePointers;
    nodePointers.push(_node);
    _Node* last = nullptr;
    _Node* cur = nullptr;
    while (!nodePointers.empty())
    {
        cur = nodePointers.top();
        if ((cur->left == nullptr && cur->right == nullptr) || last != nullptr && (last == cur->left || last == cur->right))
        {
            _func(cur);
            nodePointers.pop();
            last = cur;
        }
        else
        {
            if (cur->right != nullptr) nodePointers.push(cur->right);
            if (cur->left != nullptr) nodePointers.push(cur->left);
        }
    }
}
template<typename _Node, typename _Func>
void BTO::levelTraversal(_Node* _node, const _Func& _func)
{
    if (_node == nullptr) return;
    std::queue<_Node*> nodePointers;
    nodePointers.push(_node);
    _Node* cur = nullptr;
    while (!nodePointers.empty())
    {
        cur = nodePointers.front();
        _func(cur);
        if (cur->left != nullptr) nodePointers.push(cur->left);
        if (cur->right != nullptr) nodePointers.push(cur->right);
        nodePointers.pop();
    }
}

/* Find operations */
template<typename _Node, typename _Ty>
_Node* BTO::find(_Node* _node, const _Ty& _key)
{
    if (_node == nullptr || _key == _node->key) return _node;
    if (_key < _node->key) return find(_node->left, _key);
    else return find(_node->right, _key);
}
template<typename _Node, typename _Ty>
_Node* BTO::iterativeFind(_Node* _node, const _Ty& _key)
{
    _Node* cur = _node;
    while (cur != nullptr && cur->key != _key)
    {
        if (_key < cur->key) cur = cur->left;
        else cur = cur->right;
    }
    return cur;
}
template<typename _Node>
_Node* BTO::findMaximum(_Node* _node)
{
    _Node* cur = _node;
    if (cur == nullptr) return cur;
    while (cur->right != nullptr)
        cur = cur->right;
    return cur;
}
template<typename _Node>
_Node* BTO::findMinimum(_Node* _node)
{
    _Node* cur = _node;
    if (cur == nullptr) return cur;
    while (cur->left != nullptr)
        cur = cur->left;
    return cur;
}
template<typename _Node>
size_t BTO::getLevel(_Node* _node)
{
    if (_node == nullptr) return 0;
    size_t n = 0;
    std::queue<_Node*> nodePointers;
    nodePointers.push(_node);
    while (!nodePointers.empty())
    {
        _Node* levelBegin = nodePointers.front();
        _Node* levelEnd = nodePointers.back();
        _Node* cur = levelBegin;
        while (true)
        {
            if (cur->left != nullptr) nodePointers.push(cur->left);
            if (cur->right != nullptr) nodePointers.push(cur->right);
            if (cur == levelEnd)
                break;
            nodePointers.pop();
            cur = nodePointers.front();
        }
        nodePointers.pop();
        ++n;
    }
    return n;
}

/* Inset operation */
template<typename _Node, typename _Ty>
std::pair<_Node*, bool> BTO::insert(_Node*& _node, const _Ty& _key)
{
    std::pair<_Node*, bool> ret(nullptr, true);
    if (_node == nullptr)
    {
        _node = new _Node(_key);
        ret.first = _node;
        return ret;
    }
    _Node* cur = _node;
    while (true)
    {
        if (_key == cur->key)
        {
            ret.second = false;
            return ret;
        }
        else if (_key < cur->key && cur->left != nullptr) cur = cur->left;
        else if (_key > cur->key&& cur->right != nullptr) cur = cur->right;
        else break;
    }
    _Node* newNode = new _Node(_key);
    if (_key < cur->key) cur->left = newNode;
    else cur->right = newNode;
    newNode->parent = cur;
    ret.first = newNode;
    newNode = nullptr;
    return ret;
}

/* Copy operation */
template<typename _Node>
_Node* BTO::copy(_Node* _node, _Node* _ret)
{
    if (_ret != nullptr) return nullptr;
    preorderTraversal(_node, [&_ret](_Node* _no) { insert(_ret, _no->key); });
    return _ret;
}
template<typename _Node>
_Node* BTO::iterativeCopy(_Node* _node, _Node* _ret)
{
    if (_ret != nullptr) return nullptr;
    iterativePreorderTraversal(_node, [&_ret](_Node* _no) { insert(_ret, _no->key); });
    return _ret;
}

/* Clear operation */
template<typename _Node>
void BTO::clear(_Node*& _node)
{
    if (_node == nullptr) return;
    clear(_node->left);
    clear(_node->right);
    delete _node;
    _node = nullptr;
}

/* Rotate operation */
template<typename _Node>
_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<typename _Node>
_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__

 


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 微信高併發搶紅包秒殺實戰案例
    前言 群里有小伙伴咨詢微信紅包的架構，對於我來說，顯然是不知道的，但是寫一個相對高併發的搶紅包案例還是完全可以的。 架構設計 業務流程 老闆發紅包，此時緩存初始化紅包個數，紅包金額(單位分)，並非同步入庫。 搶紅包，判斷緩存剩餘紅包金額，剩餘金額大於零則搶到紅包，否則手慢了，紅包派完了 拆紅包，根據 ...
  • 集群、負載均衡、微服務、分散式的概念
    集群 多台主機乾同樣的事 比如web容器，只使用一個主機： 這個主機發生故障，直接gg。 資料庫併發量大時，這個主機負擔很大 資料庫集群：使用多個主機，這些主機上都運行web容器。 某些主機發生故障，其它主機還能工作，影響不大 更好應對併發 常見的集群： web伺服器集群，比如tomcat集群 數據 ...
  • Python2 和 Python3 編碼問題
    基本存儲單元 位（bit, b）：二進位數中的一個數位，可以是0或者1，是電腦中數據的最小單位。 位元組（Byte，B）：電腦中數據的基本單位，每8位組成一個位元組。 1B = 8b 各種信息在電腦中存儲、處理，至少需要一個位元組的空間。 位元組與字元 電腦存儲的一切數據都是由一串 0 和 1 組成 ...
  • 【Game學習隨筆01】挑戰任務01
    今天是2020年2月6日，時間過得好快，以至於我在寫到時間會下意識寫成2019年…… 看來全國肺炎情況進一步升溫了，以至於我家所在的小區進行了命令封鎖通知，所以出行不再像以前那麼自由了，不管怎樣，給戰鬥在一線的抗肺炎醫生們以及相關工作人員加油打氣。 言歸正傳，今天完成了有關python學習過程中的一 ...
  • 關於pandas增加行時，索引名稱的一些問題
    學習pandas兩天了，關於這個增加行的問題一直困擾著我，測試了幾個代碼，終於搞通了一點（昨天是因為代碼敲錯了。。。） 直接上代碼： 1 dates = pd.date_range('20170101',periods=6) 2 df1 = pd.DataFrame(np.arange(24).re ...
  • 2020牛客寒假演算法基礎集訓營1 部分題解
    | A | B | C | D | E | F | G | H | I | J | | : : | : : | : : | : : | : : | : : | : : | : : | : : | : : | | $\checkmark$ | $\checkmark$ | $O$ | $\checkm ...
  • 多線程之CountDownLatch的用法及原理筆記
    前言 CountDownLatch是什麼？ CountDownLatch是具有synchronized機制的一個工具，目的是讓一個或者多個線程等待，直到其他線程的一系列操作完成。 CountDownLatch初始化的時候，需要提供一個整形數字，數字代表著線程需要調用countDown()方法的次數， ...
  • 00.簡述工廠設計模式
    這裡簡單理解:簡單工廠又叫靜態工廠;是將工廠方法的方法體加上static 問題來了,什麼是開閉原則?又有哪些設計原則呢? 開閉原則就是說對擴展開放，對修改關閉。在程式需要進行拓展的時候，不能去修改原有的代碼，實現一個熱插拔的效果。所以一句話概括就是：為了使程式的擴展性好，易於維護和升級。想要達到這樣 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類