数据结构与算法—二叉树数组表示（ArrayBinTree）、二叉树的链式表示（LinkedBinTree）的基于C++模板代码实现-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构与算法—二叉树数组表示（ArrayBinTree）、二叉树的链式表示（LinkedBinTree）的基于C++模板代码实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1、二叉树的顺序表示：ArrayBinTree.h

二叉树的顺序表示法操作方便，但缺点是容易造成存储空间浪费。

#ifndef DATA_STRUCTURE_ARRAYBINTREE_H
#define DATA_STRUCTURE_ARRAYBINTREE_H

#include<iostream>
#include <cassert>

using namespace std;

template<class T>
class ArrayBinTree{
public:
    ArrayBinTree(int nDepth);   //创建空二叉树
    ~ArrayBinTree();     //删除二叉树
    void CreateToot(const T&x);
    void Clear();

    bool InsertLeftChild(int nIndex,const T&x);   //将一个结点作为指定的左孩子插入
    bool InsertRightChild(int nIndex,const T&x);   //将一个结点作为指定结点的右孩子插入
    void DeleteSubTree(int nIndex);   //删除指定结点为根的子树
    void LevelOrderTraverse();   //逐层遍历

private:
    bool *m_pbUsed;    //一维动态数组，保存每个结点中是否有值
    int m_nMaxSize;   //树的最大结点数
    T *m_pElement;    //一维动态数组，保存每个结点的值
};

//实现构造函数
template<class T>
ArrayBinTree<T>::ArrayBinTree(int nDepth) {
    int nI;
    assert(nDepth>0);   //树的深度必须大于0
    m_nMaxSize =1;
    for(nI=0;nI<nDepth;nI++){     //根据树的深度计算最大结点数
        m_nMaxSize *= 2;
    }
    //根据最大结点数分配内存空间
    m_pElement = new T[m_nMaxSize];
    assert(m_pElement);
    m_pbUsed = new bool[m_nMaxSize];
    assert(m_pbUsed);
    //初始化时所有结点没有值，即为一颗空树
    for(nI=0;nI<m_nMaxSize;nI++){
        m_pbUsed[nI] = false;
    }
}

//实现析构函数
template<class T>
ArrayBinTree<T>::~ArrayBinTree(){
    //释放内存
    if(m_pElement)
        delete []m_pElement;
    if(m_pbUsed)
        delete []m_pbUsed;
}

//实现指定元素值创建根结点
template<class T>
void ArrayBinTree<T>::CreateToot(const T&x){
    m_pElement[1] = x;
    m_pbUsed[1] = true;
}

//实现清空二叉树
template<class T>
void ArrayBinTree<T>::Clear(){
    int nI;
    for(nI=1;nI<m_nMaxSize;nI++){    //将所有结点设置为没有值的状态
        m_pbUsed[nI] = false;
    }
}

//实现将一个结点作为指定结点的左孩子插入
template<class T>
bool ArrayBinTree<T>::InsertLeftChild(int nIndex,const T&x){
    int nChildIndex = 2*nIndex;   //计算左孩子结点在数组中的位置
    if(nChildIndex>=m_nMaxSize){    //右孩子结点所在位置不超过最大结点数
        return false;
    }
    m_pElement[nChildIndex] = x;      //插入左孩子结点
    m_pbUsed[nChildIndex] = true;
    return true;
}

//实现将一个结点作为指定结点的右孩子插入
template<class T>
bool ArrayBinTree<T>::InsertRightChild(int nIndex,const T&x){
    int nChildIndex = 2*nIndex + 1;   //计算右孩子结点在数组中的位置
    if(nChildIndex>=m_nMaxSize){    //右孩子结点所在位置不超过最大结点数
        return false;
    }
    m_pElement[nChildIndex] = x;      //插入右孩子结点
    m_pbUsed[nChildIndex] = true;
    return true;
}

//实现删除以指定结点为根的子树
template<class T>
void ArrayBinTree<T>::DeleteSubTree(int nIndex){
    int nLeftChildIndex = 2*nIndex;         //过去左孩子结点在数组中的位置
    int nRightChildIndex = nLeftChildIndex +1;   //过去右孩子结点在数组中的位置
    assert(nIndex>0 && nIndex<m_nMaxSize);    //待删除子树根结点必须在有效位置上
    m_pbUsed[nIndex] = false;                //将根结点置为没有值的状态
    if(nLeftChildIndex<m_nMaxSize){          //递归删除左子树
        DeleteSubTree(nLeftChildIndex);
    }
    if(nRightChildIndex<m_nMaxSize){        //递归删除右子树
        DeleteSubTree(nRightChildIndex);
    }
}

//实现逐层遍历(即从根结点开始按照自上向下，从左往右的顺序访问结点)
template<class T>
void ArrayBinTree<T>::LevelOrderTraverse(){
    int nI,nNodeNum=0;
    for(nI=1;nI<m_nMaxSize;nI++){
        if(m_pbUsed[nI]){
            cout<<nI<<":"<<m_pElement[nI]<<endl;
            nNodeNum++;
        }
    }
    //若二叉树中没有结点，则输出空二叉树
    if(nNodeNum==0){
        cout<<"空二叉树"<<endl;
    }
}
#endif //DATA_STRUCTURE_ARRAYBINTREE_H

这是一个用数组实现的二叉树类模板。它可以创建一个空树，也可以在指定的位置插入结点并设置结点的值，可以删除子树，并支持逐层遍历。使用该类时，需要提供一个元素类型T。

ArrayBinTree类有以下公共成员函数：

构造函数：使用给定的深度创建空树。

析构函数：释放内存空间。

CreateRoot：用给定的元素值创建根结点。

Clear：将所有结点置为空树。

InsertLeftChild：在指定位置插入左孩子结点，并设置结点的值。

InsertRightChild：在指定位置插入右孩子结点，并设置结点的值。

DeleteSubTree：删除以指定结点为根的子树。

LevelOrderTraverse：逐层遍历结点。
该类的底层实现使用了一个动态分配的一维数组。在数组中，树的每个结点都用一个元素来表示，数组的索引值表示树结点的位置。为了表示一个空结点，每个元素都用一个布尔值来标记是否有值。

2、二叉树的链式表示：LinkedBinTree.h

与顺序表示相比，链式表示通常具有更高的空间利用率，因此在实际应用中一般会使用链式表示存储二叉树。

本程序中同时使用栈和队列(之前写的一篇博客)，为了区分栈和队列的结点类，将栈和队列的结点类分别重新命名为StackNode和QueueNode

#ifndef DATA_STRUCTURE_LINKEDBINTREE_H
#define DATA_STRUCTURE_LINKEDBINTREE_H
#include "LinkQueue.h"
#include "LinkStack.h"
#include <cassert>
#include <iostream>
using namespace std;

//结点模板类
template<class T>
class LinkedNode{
    template<class U>
            friend class LinkedBinTree;
public:
    LinkedNode(){
        m_pLeftChild=m_pRightChild= nullptr;
    }
    LinkedNode(const T&x){
        m_pLeftChild=m_pRightChild=nullptr;
        m_data = x;
    }
private:
    T m_data;
    LinkedNode<T>* m_pLeftChild,*m_pRightChild;
};

//二叉树的二叉链表表示类模板
template<class T>
class LinkedBinTree{
public:
    LinkedBinTree();    //创建二叉树
    ~LinkedBinTree();   //删除二叉树
    bool IsEmpty();     //判断二叉树是否为空
    LinkedNode<T>* GetRoot();   //获取根结点
    LinkedNode<T>* CreateRoot(const T& x);   //以指定元素创建根结点
    void Clear();     //清空二叉树

    LinkedNode<T>* InsertLeftChild(LinkedNode<T>* pNode,const T& x);    //将一个结点作为指定的左孩子插入
    LinkedNode<T>* InsertRightChild(LinkedNode<T>* pNode,const T& x);    //将一个结点作为指定的左右子插入

    bool ModifyNodeValue(LinkedNode<T>* pNode,const T& x);      //修改指定结点的元素值
    bool GetNodeValue(LinkedNode<T>* pNode,const T& x);     //获取指定结点的元素值
    LinkedNode<T>* GetLeftChild(LinkedNode<T>* pNode);     //获取指定结点的左孩子结点
    LinkedNode<T>* GetRightChild(LinkedNode<T>* pNode);   //获取指定结点的右孩子结点

    void PreOrderTraverse(LinkedNode<T>* pNode);      //按递归方式先序遍历
    void InOrederTraverse(LinkedNode<T>* pNode);      //按递归方式中序遍历
    void PostOrderTraverse(LinkedNode<T>* pNode);     //按递归方式后序遍历

    void PreOrderTraverse();      //按非递归方式先序遍历
    void InOrederTraverse();      //按非递归方式中序遍历
    void PostOrderTraverse();     //按非递归方式后序遍历
    void LevelOrederTraverse();   //按非递归方式逐层遍历

    LinkedNode<T>* GetParent(LinkedNode<T>* pNode);   //按非递归方式获取指定结点的双亲结点
    void DeleteSubTree(LinkedNode<T>* pNode);
    void DeleteSubTreeNode(LinkedNode<T>* pNode);
    LinkedNode<T>* SearchByKey(const T& x);

private:
    LinkedNode<T>* m_pRoot;    //指向根结点的指针
};

//实现创建二叉树
template<class T>
LinkedBinTree<T>::LinkedBinTree(){
    m_pRoot = nullptr;    //将指向根结点的指针置为空
}

//实现析构函数
template<class T>
LinkedBinTree<T>::~LinkedBinTree(){
    Clear();
}

//实现判断二叉树是否为空
template<class T>
bool LinkedBinTree<T>::IsEmpty(){
    if(m_pRoot==nullptr){
        return true;
    }
    return false;
}

//获取根结点
template<class T>
LinkedNode<T>* LinkedBinTree<T>::GetRoot(){
    return m_pRoot;
}

//实现以指定元素创建根结点
template<class T>
LinkedNode<T>* LinkedBinTree<T>::CreateRoot(const T& x){
    if(m_pRoot != nullptr){     //如果二叉树原来存在根结点，则直接将根结点的值置为x
        m_pRoot->m_data = x;
    } else{
        m_pRoot = new LinkedNode<T>(x);     //否则，创建一个新结点作为根节点
    }
    return m_pRoot;
}


//实现清空二叉树
template<class T>
void LinkedBinTree<T>::Clear(){
    DeleteSubTree(m_pRoot);
}

//实现将一个结点作为指定的左孩子插入
template<class T>
LinkedNode<T>* LinkedBinTree<T>::InsertLeftChild(LinkedNode<T>* pNode,const T& x){
    LinkedNode<T>* pNewNode;
    if(pNode == nullptr){    //对传入的参数进行有效性判断
        return nullptr;
    }
    //串建一个新节点
    pNewNode = new LinkedNode<T>(x);
    if(pNewNode==nullptr){    //若分配内存失败
        return nullptr;
    }
    pNode->m_pLeftChild = pNewNode;    //将新结点作为pNode的左孩子(即将结点中的左孩子指针指向新节点)
    return pNewNode;
}

//实现将一个结点作为指定的右孩子插入
template<class T>
LinkedNode<T>* LinkedBinTree<T>::InsertRightChild(LinkedNode<T>* pNode,const T& x){
    LinkedNode<T>* pNewNode;
    if(pNode == nullptr){    //对传入的参数进行有效性判断
        return nullptr;
    }
    //串建一个新节点
    pNewNode = new LinkedNode<T>(x);
    if(pNewNode==nullptr){    //若分配内存失败
        return nullptr;
    }
    pNode->m_pRightChild = pNewNode;    //将新结点作为pNode的左孩子(即将结点中的左孩子指针指向新节点)
    return pNewNode;
}

//修改指定结点的元素值
template<class T>
bool LinkedBinTree<T>::ModifyNodeValue(LinkedNode<T>* pNode,const T& x){
    if(pNode == nullptr){
        return false;
    }
    pNode->m_data = x;
    return true;
}

//获取指定结点的元素值
template<class T>
bool LinkedBinTree<T>::GetNodeValue(LinkedNode<T>* pNode,const T& x){
    if(pNode ==nullptr){
        return false;
    }
    x = pNode->m_data;
    return true;
}

//获取指定结点的左孩子结点
template<class T>
LinkedNode<T>* LinkedBinTree<T>::GetLeftChild(LinkedNode<T>* pNode){
    if(pNode==nullptr){
        return false;
    }
    return pNode->m_pLeftChild;
}

//获取指定结点的右孩子结点
template<class T>
LinkedNode<T>* LinkedBinTree<T>::GetRightChild(LinkedNode<T>* pNode){
    if(pNode==nullptr){
        return false;
    }
    return pNode->m_pRightChild;
}


//按递归方式先序遍历
template<class T>
void LinkedBinTree<T>::PreOrderTraverse(LinkedNode<T>* pNode){
    if(pNode == nullptr){
        return;
    }
    //先访问pNode
    cout<<pNode->m_data<<' ';
    //再以先序遍历的方式访问pNode的左子树
    PreOrderTraverse(pNode->m_pLeftChild);
    //最后以先序遍历的方式访问pNode的右子树
    PreOrderTraverse(pNode->m_pRightChild);
}

//按递归方式中序遍历
template<class T>
void LinkedBinTree<T>::InOrederTraverse(LinkedNode<T>* pNode){
    if(pNode == nullptr){
        return;
    }
    //先以中序遍历的方式访问pNode的左子树
    InOrederTraverse(pNode->m_pLeftChild);
    //再访问pNode
    cout<<pNode->m_data<<' ';
    //最后以中序遍历的方式访问pNode的右子树
    InOrederTraverse(pNode->m_pRightChild);
}

//按递归方式后序遍历
template<class T>
void LinkedBinTree<T>::PostOrderTraverse(LinkedNode<T>* pNode){
    if(pNode == nullptr){
        return;
    }
    //先以后序遍历的方式访问pNode的左子树
    PostOrderTraverse(pNode->m_pLeftChild);
    //再以后序遍历的方式访问pNode的右子树
    PostOrderTraverse(pNode->m_pRightChild);
    //最后访问pNode
    cout<<pNode->m_data<<' ';
}

//按非递归方式先序遍历
template<class T>
void LinkedBinTree<T>::PreOrderTraverse(){
    LinkStack<LinkedNode<T>*> s;    //声明一个栈
    LinkedNode<T> *pNode = nullptr;   //工作指针
    if(m_pRoot== nullptr){   //空树
        return;
    }
    //将根节点入栈
    s.Push(m_pRoot);
    while (!s.IsEmpty()){
        //栈顶元素出栈并访问
        s.Pop(pNode);
        cout<<pNode->m_data<<" ";
        //若结点存在右子树，则将右子树根根节点入栈
        if(pNode->m_pRightChild){
            s.Push(pNode->m_pRightChild);
        }
        //若结点存在右子树，则将右子树根根节点入栈
        if(pNode->m_pLeftChild){
            s.Push(pNode->m_pLeftChild);
        }
    }
}

//按非递归方式中序遍历
template<class T>
void LinkedBinTree<T>::InOrederTraverse(){
    LinkStack<LinkedNode<T>*> s;
    LinkedNode<T>* pNode = m_pRoot;
    //pNode不为空是循环
    while(pNode){
        //当pNode不为空时，将其入栈，并令pNode指向其左孩子
        while (pNode){
            s.Push(pNode);
            pNode=pNode->m_pLeftChild;
        }
        //栈不为空，则栈顶结点出栈并被访问，令pNode指向取出栈顶结点的右孩子
        while(!s.IsEmpty()){
            s.Pop(pNode);
            cout<<pNode->m_data<<" ";
            pNode=pNode->m_pRightChild;
            if(pNode){    //若栈顶结点有右孩子树，则访问其右子树
                break;
            }
        }
    }
}

//按非递归方式后序遍历
template<class T>
void LinkedBinTree<T>::PostOrderTraverse(){
    LinkStack<LinkedNode<T>*> s;
    LinkedNode<T> *pNode=m_pRoot, *pPreVisitNode = nullptr;
    //pNode不为空时循环
    while(pNode){
        //当pNode不为空时，将其入栈，并令pNode指向其左孩子
        while (pNode){
            s.Push(pNode);
            pNode=pNode->m_pLeftChild;
        }
        while (!s.IsEmpty()){
            //当栈顶元素不为空时，取出栈顶元素
            s.Top(pNode);
            //若栈顶元素的右孩子为空或已被访问，则访问当前栈顶元素，并将栈顶元素出栈
            if(pNode->m_pRightChild== nullptr || pNode->m_pRightChild==pPreVisitNode){
                cout<<pNode->m_data<<" ";
                s.Pop(pNode);
                pPreVisitNode = pNode;  //设置pNode为前一个访问的结点
                //设置pNode为空，表示pNode及其左右子树均已访问完毕，访问下一个栈中元素
                pNode= nullptr;
            } else{  //否则，应先访问栈顶元素的右孩子
                pNode = pNode->m_pRightChild;
                break;
            }
        }
    }
}

//按非递归方式逐层遍历
template<class T>
void LinkedBinTree<T>::LevelOrederTraverse(){
    LinkQueue<LinkedNode<T>*> q;
    LinkedNode<T>* pNode = nullptr;
    if(m_pRoot== nullptr){
        return;
    }
    //根结点进队
    q.Insert(m_pRoot);
    //当队列不为空时循环
    while(!q.IsEmpty()){
        //队头元素出队并访问
        q.Delete(pNode);
        cout<<pNode->m_data<<" ";
        //若根结点存在左子树，则将左子树根结点入队
        if(pNode->m_pLeftChild){
            q.Insert(pNode->m_pLeftChild);
        }
        //若结点存在右子树，则将右子树根结点入队
        if(pNode->m_pRightChild){
            q.Insert(pNode->m_pRightChild);
        }
    }
}   


//按非递归方式获取指定结点的双亲结点  ---  按层次遍历找双亲
template<class T>
LinkedNode<T>* LinkedBinTree<T>::GetParent(LinkedNode<T>* pNode){
    LinkQueue<LinkedNode<T>*> q;
    LinkedNode<T>* pCurNode=nullptr;
    if(pNode == m_pRoot){   //若指定结点pNode为根指点，则返回空
        return nullptr;
    }
    if(m_pRoot==nullptr){   //若二叉树是空树，则返回空
        return nullptr;
    }
    //按非递归逐层遍历的方式搜索双亲结点
    //首先，将根结点入队
    q.Insert(m_pRoot);
    while(!q.IsEmpty()){   //当对列不为空时循环
        //将对头元素出队
        q.Delete(pCurNode);
        //如果pNode是对头元素的孩子，则返回对头元素
        if(pCurNode->m_pLeftChild==pNode || pCurNode->m_pRightChild==pNode){
            return pCurNode;
        }
        //若结点存在左子树，则将左子树根结点入队
        if(pCurNode->m_pLeftChild){
            q.Insert(pCurNode->m_pLeftChild);
        }
        //若结点存在右子树，则将右子树根结点入队
        if(pCurNode->m_pRightChild){
            q.Insert(pCurNode->m_pRightChild);
        }
    }
    return nullptr;
}

//删除以指定结点的子树
template<class T>
void LinkedBinTree<T>::DeleteSubTree(LinkedNode<T>* pNode){
    LinkedNode<T>* pParentNode =nullptr;
    //若指定结点为空，则返回
    if(pNode==nullptr){
        return;
    }
    if(pNode==m_pRoot){   //若将整颗树删除，则令根结点为空
        m_pRoot=nullptr;
    } else if((pParentNode= GetParent(pNode)) !=nullptr){    //否则，若指定结点存在双亲结点，则将双亲结点的左右指针域置为空
        if(pParentNode->m_pLeftChild == pNode){
            pParentNode->m_pLeftChild = nullptr;
        } else{
            pParentNode->m_pRightChild =nullptr;
        }
    } else{  //否则，指定结点不是二叉树的结点，直接返回
        return;
    }
    //调用DeleteSubTreeNode函数删除以pNode为根的子树
    DeleteSubTreeNode(pNode);
}

//由DeleteSubTree函数调用按非递归方式删除以指定结点为根的子树
template<class T>
void LinkedBinTree<T>::DeleteSubTreeNode(LinkedNode<T>* pNode){
    LinkQueue<LinkedNode<T>*> q;
    LinkedNode<T>* pCurNode = nullptr;
    if(pNode==nullptr){
        return;
    }
    //按非递归层次遍历的方式删除子树
    q.Insert(pNode);
    while (!q.IsEmpty()){
        q.Delete(pCurNode);
        if(pCurNode->m_pLeftChild){
            q.Insert(pCurNode->m_pLeftChild);
        }
        if(pCurNode->m_pRightChild){
            q.Insert(pCurNode->m_pRightChild);
        }
        delete pCurNode;
    }
}

//按非递归方式根据关键字查找结点
template<class T>
LinkedNode<T>* LinkedBinTree<T>::SearchByKey(const T& x){
    LinkQueue<LinkedNode<T>*> q;
    LinkedNode<T>* pMatchNode =nullptr;
    if(m_pRoot==nullptr){
        return false;
    }
    //按费递归层次遍历的方式查找结点
    q.Insert(m_pRoot);
    while (!q.IsEmpty()){
        q.Delete(pMatchNode);
        if(pMatchNode->m_data==x){
            return pMatchNode;
        }
        if(pMatchNode->m_pLeftChild){
            q.Insert(pMatchNode->m_pLeftChild);
        }
        if(pMatchNode->m_pRightChild){
            q.Insert(pMatchNode->m_pRightChild);
        }
    }
    return nullptr;
}
#endif //DATA_STRUCTURE_LINKEDBINTREE_H