摘要：

   it人员无论是使用哪种高级语言开发东东，想要更高效有层次的开发程序的话都躲不开三件套：数据结构，算法和设计模式。数据结构是相互之间存在一种或多种特定关系的数据元素的集合，即带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系，分为逻辑结构和存储结构。

   此系列专注讲解数据结构数组、链表、队列、栈、树、哈希表、图，通过介绍概念以及提及一些可能适用的场景，并以C++代码简易实现，多方面认识数据结构，最后为避免重复造轮子会浅提对应的STL容器。本文介绍的是树Tree。

（开发环境：VScode，C++17）

关键词： C++，数据结构，树，Tree

声明：本文作者原创，转载请附上文章出处与本文链接。

(文章目录：)

正文：

介绍：

   数据结构中的“树”是一种非常重要的非线性数据结构，由n（n≥0）个有限节点组成一个具有层次关系的集合。之所以被称为“树”，是因为它看起来像一棵倒挂的树，即根朝上，叶朝下。树的结构特点是：

• 每个节点有零个或多个子节点；
• 没有父节点的节点称为根节点；
• 每一个非根节点有且只有一个父节点；
• 除了根节点外，每个子节点可以分为多个不相交的子树。

其中红黑树和二叉树最为常用。

树的术语：

• 节点：树中的每个元素。
• 根节点：没有父节点的节点。
• 子节点：一个节点含有的子树的根节点。
• 父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点。
• 兄弟节点：具有相同父节点的节点。
• 树的度：一棵树中，最大的节点的度。
• 树的深度或高度：树中节点的最大层次。
• 叶子节点或终端节点：度为0的节点。
• 非叶子节点或分支节点：度不为0的节点。
• 森林：由n棵互不相交的树的集合称为森林。

特性：

• 层次结构：树具有清晰的层次结构，每个节点都位于一个特定的层次上。根节点位于第一层，其子节点位于第二层，依此类推。这种层次结构使得树能够表示具有层次关系的数据。

• 无环性：在树中，从一个节点出发，沿着父节点-子节点的关系向下（或向上）遍历，不可能回到原点，除非整个遍历过程已经完成。换句话说，树中不存在环路或循环。

• 根节点唯一：树中只有一个根节点，它是树的起点。所有的其他节点都直接或间接地连接到根节点。

• 遍历性：树支持多种遍历方式，如先序遍历（根-左-右）、中序遍历（左-根-右）和后序遍历（左-右-根）。这些遍历方式对于实现各种算法和数据结构操作非常重要。

应用：

• 利用树型结构可以求解集合的幂集问题，如集合{1，2，…，n}的幂集问题。
• 在计算机科学中，树被广泛应用于各种算法和数据结构中，如二叉搜索树、AVL树、红黑树等，用于实现高效的查找、插入和删除操作。
• 树被广泛应用于各种场景，如文件夹目录、公司组织关系、编译器设计、数据库索引、网络路由协议等。

代码实现：

#ctree.h
#ifndef CTREE_H
#define CTREE_H
#include<iostream>
using namespace std;

// 树节点
template<class T>
class TreeNode
{
public:
  int index;                    // 坐标
  T data;                       // 数据
  TreeNode<T> *pLChild;         // 左节点
  TreeNode<T> *pRChild;         // 右节点
  TreeNode<T> *pParent;         // 父节点

public:
    TreeNode():index(0),data('0'),pLChild(NULL),pRChild(NULL),pParent(NULL) {}
    TreeNode(int iNodeIndex, T val):index(iNodeIndex),data(val),pLChild(NULL),pRChild(NULL),pParent(NULL) {}
    ~TreeNode(){}

    TreeNode<T>* SearchNode(int iNodeIndex);    // 通过序号坐标搜寻对应的节点
    void DeleteNode();                          // 删除此树节点
    void PreOrderTraversal();                   // 先序遍历 根左右
    void InOrderTraversal();                    // 中序遍历 左根右
    void PostOrderTraversal();                  // 后序遍历 左右根

private:
    // 禁止拷贝、赋值
    TreeNode(const TreeNode<T>& node);
    TreeNode& operator=(const TreeNode<T>& node);
};

template <class T>
inline TreeNode<T>* TreeNode<T>::SearchNode(int iNodeIndex)
{
    if (index == iNodeIndex){
        return this;
    }
    TreeNode<T> *temp = NULL;
    if (pLChild){
        if (pLChild->index == iNodeIndex){
            return pLChild;
        }
        else{
            temp = pLChild->SearchNode(iNodeIndex);
            if (temp){
                return temp;
            }
        }
    }
    if (pRChild){
        if (pRChild->index == iNodeIndex){
            return pRChild;
        }
        else{
            temp = pRChild->SearchNode(iNodeIndex);
            if (temp){
                return temp;
            }
        }
    }
    return NULL;
}

template <class T>
inline void TreeNode<T>::DeleteNode()
{
    if (pLChild != NULL){
        pLChild->DeleteNode();
    }
    if (pRChild != NULL){
        pRChild->DeleteNode();
    }
    if (pParent != NULL){
        if (this == pParent->pLChild)
            pParent->pLChild = NULL;
        if (this == pParent->pRChild)
            pParent->pRChild = NULL;
    }
    delete this;
}

template <class T>
inline void TreeNode<T>::PreOrderTraversal()
{
    cout << data << " ";
    if (pLChild){
        pLChild->PreOrderTraversal();
    }
    if (pRChild){
        pRChild->PreOrderTraversal();
    }
}

template <class T>
inline void TreeNode<T>::InOrderTraversal()
{
    if (pLChild){
        pLChild->InOrderTraversal();
    }
    cout << data << " ";
    if (pRChild){
        pRChild->InOrderTraversal();
    }
}

template <class T>
void TreeNode<T>::PostOrderTraversal()
{
    if (pLChild){
        pLChild->PostOrderTraversal();
    }
    if (pRChild){
        pRChild->PostOrderTraversal();
    }
    cout << data << " ";
}


// 基于链表的二叉树基本实现和遍历
template <class T>
class CTree
{
public:
    CTree(TreeNode<T> *pNode = NULL);
    ~CTree(){ m_pRoot->DeleteNode(); }
    TreeNode<T>* SearchNode(int index){ return m_pRoot->SearchNode(index); }

    bool AddNode(int index, int direction, TreeNode<T> *pNode);
    bool DeleteNode(int index, TreeNode<T> *pNode);
    // 先序遍历-递归
    void Recursive_PreOrderTraversal(){ m_pRoot->PreOrderTraversal(); }
    // 中序遍历-递归
    void Recursive_InOrderTraversal(){ m_pRoot->InOrderTraversal(); }
    // 后序遍历-递归
    void Recursive_PostOrderTraversal(){ m_pRoot->PostOrderTraversal(); }
    // 先序遍历-非递归
    void PreOrderTraversal();
    //中序遍历-非递归
    void InOrderTraversal();
    //后序遍历-非递归
    void PostOrderTraversal();

private:
    TreeNode<T> *m_pRoot; //根节点
};

template <class T>
inline CTree<T>::CTree(TreeNode<T> *pNode)
{
    // 创建树默认先创建根节点
    m_pRoot = new TreeNode<T>();
    if (!m_pRoot){
      throw "根节点申请内存失败";
      return;
    }
    if (pNode){
        m_pRoot->index = 0;
        m_pRoot->data = pNode->data;
    }
    else{
        m_pRoot->index = 0;
        m_pRoot->data = '0';
    }
}

template <class T>
inline bool CTree<T>::AddNode(int index, int direction, TreeNode<T> *pNode)
{
    if (!pNode){
        cout << "插入失败！新增的节点值为空。" << endl;
        return false;
    }
    TreeNode<T> *temp = SearchNode(index);
    if (!temp){
        cout << pNode->data << "插入失败！找不到传入下标对应的父节点。" << endl;
        return false;
    }

    TreeNode<T> *node = new TreeNode<T>();
    if (!node){
        cout << pNode->data << "插入失败！新的节点申请内存失败。" << endl;
        return false;
    }

    node->index = pNode->index;
    node->data = pNode->data;
    node->pParent = temp;

    if (1 == direction){
        temp->pLChild = node;
    }
    else if (2 == direction){
        temp->pRChild = node;
    }
    else{
        cout << pNode->data << "插入失败！direction参数错误：1为左节点，2为右节点" << endl;
    }
    return true;
}

template <class T>
inline bool CTree<T>::DeleteNode(int index, TreeNode<T> *pNode)
{
    TreeNode<T> *temp = SearchNode(index);
    if (!temp){
        cout << "删除失败！找不到传入下标对应的节点。" << endl;
        return false;
    }
    if (pNode){
        pNode->index = temp->index;
        pNode->data = temp->data;
    }
    temp->DeleteNode();
    return true;
}

template <class T>
inline void CTree<T>::PreOrderTraversal()
{
    int stackTop = -1;
    TreeNode<T>* nodeStack[10];
    TreeNode<T>* pMove = m_pRoot;
    while (stackTop != -1 || pMove){
        while (pMove){
            cout << pMove->data << " ";
            nodeStack[++stackTop] = pMove;
            pMove = pMove->pLChild;
        }
        if (stackTop != -1){
            pMove = nodeStack[stackTop];
            stackTop--;
            pMove = pMove->pRChild;
        }
    }
}

template <class T>
inline void CTree<T>::InOrderTraversal()
{
    int stackTop = -1;
    TreeNode<T>* nodeStack[10];
    TreeNode<T>* pMove = m_pRoot;
    while (stackTop != -1 || pMove){
        while (pMove){
            nodeStack[++stackTop] = pMove;
            pMove = pMove->pLChild;
        }
        if (stackTop != -1){
            pMove = nodeStack[stackTop--];
            cout << pMove->data << " ";
            pMove = pMove->pRChild;
        }
    }
}

template <class T>
inline void CTree<T>::PostOrderTraversal()
{
    int stackTop = -1;
    TreeNode<T>* nodeStack[10];
    TreeNode<T>* pMove = m_pRoot;
    TreeNode<T>* pLastVisit = NULL;
    while (pMove){
        nodeStack[++stackTop] = pMove;
        pMove = pMove->pLChild;
    }
    while (stackTop != -1)
    {
        pMove = nodeStack[stackTop--];
        if (pMove->pRChild == NULL || pMove->pRChild == pLastVisit){
            cout << pMove->data << " ";
            pLastVisit = pMove;
        }
        else{
            nodeStack[++stackTop] = pMove;
            pMove = pMove->pRChild;
            while (pMove){
                nodeStack[++stackTop] = pMove;
                pMove = pMove->pLChild;
            }
        }
    }
}

#endif // !CTREE_H

#ctree.cpp
#include "ctree.h"
using namespace std;

int main(int argc, char**argv)
{
    TreeNode<char> nodeA(0, 'A');
    TreeNode<char> nodeB(1, 'B');
    TreeNode<char> nodeC(2, 'C');
    TreeNode<char> nodeD(3, 'D');
    TreeNode<char> nodeE(4, 'E');
    TreeNode<char> nodeF(6, 'F');
    TreeNode<char> nodeG(9, 'G');

    CTree<char> *tree = new CTree<char>(&nodeA);
    tree->AddNode(0, 1, &nodeB);
    tree->AddNode(0, 2, &nodeC);
    tree->AddNode(1, 1, &nodeD);
    tree->AddNode(1, 2, &nodeE);
    tree->AddNode(2, 2, &nodeF);
    tree->AddNode(4, 1, &nodeG);

    cout << "recursive traversal:" << endl;
    tree->Recursive_PreOrderTraversal();
    cout << endl;
    tree->Recursive_InOrderTraversal();
    cout << endl;
    tree->Recursive_PostOrderTraversal();
    cout << endl;

    cout << "non recursive traversal:" << endl;
    tree->PreOrderTraversal();
    cout << endl;
    tree->InOrderTraversal();
    cout << endl;
    tree->PostOrderTraversal();
    cout << endl;

    delete tree;

    return 0;
}

对应STL：

   set，multiset，map，multimap这四种容器的共同点是：底层使用了平衡搜索树（即红黑树），容器中的元素是一个有序的序列。

   网络上有对 map VS unordered_map 效率对比的测试，通常 map 增删元素的效率更高，unordered_map 访问元素的效率更高，另外，unordered_map 内存占用更高，因为底层的哈希表需要预分配足量的空间。其它 xxx 和 unordered_xxx 区别也一样。

基于红黑树的集合

• set：

  set 是一个关联型容器，它的底层结构是红黑树，set 是直接保存 value 的，或者说，set 中的 value 就是 key。set 中的元素必须是唯一的，不允许出现重复的元素，且元素不可更改，但可以自由插入或者删除。

• multiset：

  multiset 和 set 底层都是红黑树，multiset 相比于 set 支持保存多个相同的元素；

基于红黑树的映射

• map：

  map 是一个关联型容器，其元素类型是由 key 和 value 组成的 std::pair，实际上 map 中元素的数据类型正是 typedef pair<const Key, T> value_type;

• multimap：

  multimap 和 map 底层都是红黑树，multimap 相比于 map 支持保存多个key相同的元素。

推荐阅读

C/C++专栏：https://blog.csdn.net/weixin_45068267/category_12268204.html
（内含其它数据结构及对应STL容器使用）