C语言版本

（此处补程序）

C++版本

包含三部分

（此处补图）

BiTreeNode.h:

#ifndef _BITREENODE_H
#define _BITREENODE_H
#include<iostream>
using namespace std;


template <typename T>
class BiTreeNode
{
public:
    BiTreeNode(int index,T data);
    virtual ~BiTreeNode();
    //get data
    int getIndex();
    T getData();
    BiTreeNode *getParent();
    BiTreeNode *getLChild();
    BiTreeNode *getRChild();
    //set data
    void setIndex(int index);
    void setData(T data);
    void setParenet(BiTreeNode *Node);
    void setLChild(BiTreeNode *Node);
    void setRChild(BiTreeNode *Node);
    //else
    BiTreeNode *NodeSearch(int index);                    //通过索引搜索节点（以本节点作为根寻找树的某个节点）
    int NodeLeavesStatistics(int leaves = 0);            //统计叶子数
    int NodeChildrenNodeHeigh();                        //统计子节点的最大高度（包含本节点）/（以本节点作为根求树的高度）
    int NodeChildrenStatistics();                        //统计子节点数(包含本节点)
    int NodeDelete();                                    //删除节点
    //traversal
    void NodePreorderTraversal();
    void NodeInorderTraversal();
    void NodeSubsequentTraversal();
private:
    int m_iIndex;
    T m_tData;
    BiTreeNode *m_pParent;
    BiTreeNode *m_pLeftChild;
    BiTreeNode *m_pRightChild;

    //struct NodeWidth<T> stNodeWidth;
};

template <typename T>
BiTreeNode<T>::BiTreeNode(int index,T data)
{
    m_iIndex = index;
    m_tData = data;
    m_pParent = NULL;
    m_pLeftChild = NULL;
    m_pRightChild = NULL;
}

template <typename T>
BiTreeNode<T>::~BiTreeNode()
{
    if(m_pLeftChild != NULL)
    {
        m_pLeftChild->NodeDelete();
        m_pLeftChild = NULL;
    }
    if(m_pRightChild != NULL)
    {
        m_pRightChild->NodeDelete();
        m_pRightChild = NULL;
    }
    m_pParent = NULL;
}
/*-----------------------getdata------------------------*/
template <typename T>
int BiTreeNode<T>::getIndex()
{
    return m_iIndex;
}


template <typename T>
T BiTreeNode<T>::getData()
{
    return m_tData;
}

template <typename T>
BiTreeNode<T> *BiTreeNode<T>::getParent()
{
    return m_pParent;
}

template <typename T>
BiTreeNode<T> *BiTreeNode<T>::getLChild()
{
    return m_pLeftChild;
}

template <typename T>
BiTreeNode<T> *BiTreeNode<T>::getRChild()
{
    return m_pRightChild;
}

/*-----------------------setdata------------------------*/
template <typename T>
void setIndex(int index)
{
    m_iIndex = index;
}
template <typename T>
void setData(T data)
{
    m_tData = data;
}
template <typename T>
void BiTreeNode<T>::setParenet(BiTreeNode *Node)
{
    m_pParent = Node;
}

template <typename T>
void BiTreeNode<T>::setLChild(BiTreeNode *Node)
{
    m_pLeftChild = Node;
}

template <typename T>
void BiTreeNode<T>::setRChild(BiTreeNode *Node)
{
    m_pRightChild = Node;
}

/*-----------------------else------------------------*/
template <typename T>
BiTreeNode<T> *BiTreeNode<T>::NodeSearch(int index)
{
    BiTreeNode<T> *tempNode = NULL;
    if(m_iIndex == index)
    {
        return this;
    }
    if(m_pLeftChild != NULL)
    {
        tempNode = m_pLeftChild->NodeSearch(index);
        if(tempNode != NULL)//match
        {
            return tempNode;
        }
    }

    if(m_pRightChild !=NULL)
    {
        tempNode = m_pRightChild->NodeSearch(index);
        if(tempNode != NULL)// match
        {
            return tempNode;
        }
    }


    return NULL;
}

/*statistcal children node heigh(includding me)*/
template <typename T>
int BiTreeNode<T>::NodeChildrenNodeHeigh()
{
    int heightLeft =0 ;
    int heightRight =0; 
    if(m_pLeftChild != NULL)
    {
        heightLeft += m_pLeftChild->NodeChildrenNodeHeigh();    
    }
    if(m_pRightChild != NULL)
    {
        heightRight += m_pRightChild->NodeChildrenNodeHeigh();
    }
    if(heightRight > heightLeft)
    {
        return ++heightRight;
    }
    else
    {
        return ++heightLeft;
    }
}

/*statistcal leaves node(includding me)*/
template <typename T>
int BiTreeNode<T>::NodeLeavesStatistics(int leaves)
{
    if(this->m_pLeftChild != NULL)
    {
        leaves = this->m_pLeftChild->NodeLeavesStatistics(leaves);
    }
    if(this->m_pRightChild != NULL)
    {
        leaves = this->m_pRightChild->NodeLeavesStatistics(leaves);
    }
    if(this->getLChild() == NULL && this->getRChild() == NULL)
    {
        leaves ++;
    }
    return leaves;    
}
/*statistcal children node(includding me)*/
template <typename T>
int BiTreeNode<T>::NodeChildrenStatistics()
{
    int iCnt=0;
    if(this->m_pLeftChild != NULL)
    {
        iCnt+=this->m_pLeftChild->NodeChildrenStatistics();
    }
    if(this->m_pRightChild!= NULL)
    {
        iCnt+=this->m_pRightChild->NodeChildrenStatistics();
    }
    iCnt++;
    return iCnt;
}

template <typename T>
int  BiTreeNode<T>::NodeDelete()
{
    int Times=0;
    if(this->m_pLeftChild != NULL)
    {
         //delete this->getLChild();
        Times+=this->m_pLeftChild->NodeDelete();
        this->m_pLeftChild =NULL;
    }
    if(this->m_pRightChild!= NULL)
    {
        //delete this->getRChild();
        Times+=this->m_pRightChild->NodeDelete();
        this->m_pRightChild =NULL;
    }
    Times++;
    delete this;
    return Times;
}
/*-----------------------traversal------------------------*/
template <typename T>
void BiTreeNode<T>::NodePreorderTraversal()
{
    cout<<"Index:"<<this->getIndex()<<";Data:"<<this->getData()<<endl;

    if(this->getLChild() != NULL)
    {
        this->getLChild()->NodePreorderTraversal();
    }

    if(this->getRChild() != NULL)
    {
        this->getRChild()->NodePreorderTraversal();
    }
}

template <typename T>
void BiTreeNode<T>::NodeInorderTraversal()
{
    if(this->getLChild() != NULL)
    {
        this->getLChild()->NodePreorderTraversal();
    }

    cout<<"Index:"<<this->getIndex()<<";Data:"<<this->getData()<<endl;

    if(this->getRChild() != NULL)
    {
        this->getRChild()->NodePreorderTraversal();
    }
}

template <typename T>
void BiTreeNode<T>::NodeSubsequentTraversal()
{
    if(this->getLChild() != NULL)
    {
        this->getLChild()->NodePreorderTraversal();
    }

    if(this->getRChild() != NULL)
    {
        this->getRChild()->NodePreorderTraversal();
    }

    cout<<"Index:"<<this->getIndex()<<";Data:"<<this->getData()<<endl;
}

#endif

View Code

BinaryTree.h

#ifndef _BINARYTREE_H
#define _BINARYTREE_H

#include <iostream>

#include "BiTreeNode.h"
using namespace std;

template <typename T>
class BinaryTree
{
public:
    BinaryTree(int size);
    virtual ~BinaryTree();                                            
    bool IsTreeFull();                                                //树的容量是否已满
    //search    
    BiTreeNode<T> getNodeByIndex(int index);                        //通过索引搜索节点
    int getLeaves();                                                //获取树的叶子数
    int getHeight();                                                //获取树的高度(包含根节点)
    int getWidth();                                                    //获取树的宽度(包含根节点)
    int getNowSize();                                                //获取树现在的节点数（包含根节点）
    int getMaxSize();                                                //获取树的最大节点数
    //add/delete
    bool addLeftNodeByIndex(int newIndex,T data,int searchIndex);    //添加左子树（使用索引）
    bool addRightNodeByIndex(int newIndex,T data,int searchIndex);  //添加右子树（使用索引）
    bool addLeftNodeByNode(int index,T data,BiTreeNode<T> *pNode);  //添加左子树（使用节点地址）
    bool addRightNodeByNode(int index,T data,BiTreeNode<T> *pNode); //添加右子树（使用节点地址）
    bool deleteNodeByIndex(int index);                                //删除节点（使用索引）
    bool deleteNodeByNode(BiTreeNode<T> *pNode);                    //删除节点（使用地址）

    //traversal
    void PreorderTraversal();                                        //先序遍历
    void InorderTraversal();                                        //中序遍历
    void SubsequentTraversal();                                        //后序遍历

private:
    BiTreeNode<T> *m_pRoot;                                            //tree root
    int m_iSize;                                                    //Tree now nodes size (without root)
    int m_iMaxSize;                                                    //Tree max nodes size (without root) 
};


template <typename T>
BinaryTree<T>::BinaryTree(int size)
{
    m_pRoot = new BiTreeNode<T>(1,0);
    m_pRoot->setLChild(NULL);
    m_pRoot->setRChild(NULL);
    m_pRoot->setParenet(NULL);
    m_iSize = 0;
    m_iMaxSize = size;
}

template <typename T>
BinaryTree<T>::~BinaryTree()
{
    delete m_pRoot;
    m_pRoot=NULL;
}
template <typename T>
bool BinaryTree<T>::IsTreeFull()
{
    if(m_iSize >= m_iMaxSize)
        return true;
    return false;
}
//search
template <typename T>
BiTreeNode<T> BinaryTree<T>::getNodeByIndex(int index)
{
    return m_pRoot->NodeSearch(index);
}
template <typename T>
int BinaryTree<T>::getLeaves()
{    
    return m_pRoot->NodeLeavesStatistics();
}

template <typename T>
int BinaryTree<T>::getWidth()
{
    int maxWidth=1;                //save max width
    int parentWidth=0;            //save this width
    int childrenWidth=0;        //save next width
    queue<BiTreeNode<T>*> stdQueue;
    BiTreeNode<T> *tempNode = m_pRoot;
    if(tempNode -> getLChild() != NULL)
    {
        stdQueue.push(tempNode -> getLChild());
        parentWidth ++;
    }
    if(tempNode -> getRChild() != NULL)
    {
        stdQueue.push(tempNode ->getRChild());
        parentWidth ++;
    }

    while(!stdQueue.empty())
    {
        while(parentWidth>0)
        {
            tempNode = stdQueue.front();
            stdQueue.pop();
            if(tempNode -> getLChild() != NULL)
            {
                stdQueue.push(tempNode -> getLChild());
                childrenWidth ++;
            }
            if(tempNode -> getRChild() != NULL)
            {
                stdQueue.push(tempNode ->getRChild());
                childrenWidth ++;
            }
            parentWidth --;
        }
        parentWidth = childrenWidth;
        if(parentWidth > maxWidth)
        {
            maxWidth = parentWidth;
        }
        childrenWidth =0;
    }

//    result =  m_pRoot->NodeChildrenNodeWidth(&child);
    return maxWidth;
}


template <typename T>
int BinaryTree<T>::getHeight()
{
    return m_pRoot->NodeChildrenNodeHeigh();//include root 
}

template <typename T>
int BinaryTree<T>::getNowSize()
{
    //return m_iSize;//quickly get Size
    return m_pRoot ->NodeChildrenStatistics();//except root
}

template <typename T>
int BinaryTree<T>::getMaxSize()
{
    return m_iMaxSize ;
}

//add/delete
template <typename T>
bool BinaryTree<T>::addLeftNodeByIndex(int newIndex,T data,int searchIndex)
{
    BiTreeNode<T> *tempNode;
    tempNode = m_pRoot->NodeSearch(searchIndex);//find the Node witch is index = searchIndex
    if(tempNode!=NULL)
    {
        return addLeftNodeByNode(newIndex,data,tempNode);
    }
    return false;
}
template <typename T>
bool BinaryTree<T>::addRightNodeByIndex(int newIndex,T data,int searchIndex)
{
    BiTreeNode<T> *tempNode ;
    tempNode = m_pRoot->NodeSearch(searchIndex);
    if(tempNode!=NULL)
    {
        return addRightNodeByNode(newIndex,data,tempNode);
    }
    return false;
}
template <typename T>
bool BinaryTree<T>::addLeftNodeByNode(int index,T data,BiTreeNode<T> *pNode)
{
    BiTreeNode<T> *pNodeCopy = pNode;//make a copy of pNode to protect the pNode being changed by accidentally
    if(IsTreeFull())
    {
        return false ;
    }
    if(pNodeCopy -> getLChild() == NULL)
    {
        BiTreeNode<T> *newNode = new BiTreeNode<T>(index,data);
        pNodeCopy->setLChild(newNode);
        newNode->setParenet(pNodeCopy);
    }
    else 
    {
        return false ;
    }

    m_iSize++;
    return true;
}

template <typename T>
bool BinaryTree<T>::addRightNodeByNode(int index,T data,BiTreeNode<T> *pNode)
{
    BiTreeNode<T> *pNodeCopy = pNode;//make a copy of pNode to protect the pNode being changed by accidentally
    if(IsTreeFull())
    {
        return false ;
    }
    if(pNodeCopy -> getRChild() == NULL)
    {
        BiTreeNode<T> *newNode = new BiTreeNode<T>(index,data);
        pNodeCopy->setRChild(newNode);
        newNode->setParenet(pNodeCopy);
    }
    else 
    {
        return false ;
    }

    m_iSize++;
    return true;
}

template <typename T>
bool BinaryTree<T>::deleteNodeByIndex(int index)
{
    BiTreeNode<T> *deleteNode = m_pRoot->NodeSearch(index);
    if(deleteNode != NULL)
    {
        if(deleteNode == m_pRoot)
        {
            cout<<"BinaryTree<T>::deleteNodeByIndex():"<<index<<"是根节点不能删除"<<endl;
            return false;
        }
        return deleteNodeByNode(deleteNode);
    }
    return false;
}
template <typename T>
bool BinaryTree<T>::deleteNodeByNode(BiTreeNode<T> *pNode)
{
    if(pNode!=NULL)
    {
        /*clear parent Node L/RChild*/ 
        BiTreeNode<T> *parentNode = pNode->getParent();
        if(parentNode != NULL)
        {
            if(parentNode->getLChild() == pNode)
            {
                parentNode->setLChild(NULL);
            }
            else
            {
                parentNode->setRChild(NULL);
            }
        }
        /*delete node*/
        int SizeDec;//use to caculate how much Node was delete
        SizeDec = pNode->NodeDelete();
        m_iSize-=SizeDec;
        return true;
    }
    return false;
}

//traversal
template <typename T>
void BinaryTree<T>::PreorderTraversal()
{
    cout<<"PerorderTraversal:"<<endl;
    m_pRoot ->NodePreorderTraversal();
}
template <typename T>
void BinaryTree<T>::InorderTraversal()
{
    cout<<"InorderTraversal:"<<endl;
    m_pRoot ->NodeInorderTraversal();
}
template <typename T>
void BinaryTree<T>::SubsequentTraversal()
{
    cout<<"SubsequentTraversal:"<<endl;
    m_pRoot ->NodeSubsequentTraversal();
}

#endif

View Code

main.c(本部分用于测试)

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

using namespace std;


int main()
{
    //float Ldatas[11] = {0.0f,1.1f,2.2f,3.3f,4.4f,5.5f,6.6f,7.7f,8.8f,9.9f,10.1f};
    //float Rdatas[5] = {30.0f,31.1f,32.2f,33.3f,34.4f};
    int Ldatas[11] = {0,1,2,3,4,5,6,7,8,9,10};
    int Rdatas[5] = {30,31,32,33,34};
    BinaryTree<int> *tree = new BinaryTree<int>(20);

    //addLeftNodeByIndex()/addRightNodeByIndex check
    for(int i=1;i<5;i++)
    {
        tree->addLeftNodeByIndex(i+1,Ldatas[i],i);
    }
    for(int i=1;i<5;i++)
    {
        tree->addRightNodeByIndex(i+5,Rdatas[i],i);
    }
    for(int i=1;i<5;i++)
    {
        tree->addLeftNodeByIndex(i+9,Rdatas[i],i+5);
    }
    tree->PreorderTraversal();
    cout<<"tree size(except root):"<<tree->getNowSize()<<endl;

    //getLeaves() check;
    cout<<"tree leaves:"<<tree->getLeaves()<<endl;

    //getHeight() check;
    cout<<"getHeight():"<<tree->getHeight()<<endl;

    //getWidth() check;
    cout<<"getWidth():"<<tree->getWidth()<<endl;

    //preorderTraversal()/InorderTraversal()/SubsequentTraversal() check
//    tree->PreorderTraversal();
//    tree->InorderTraversal();
//    tree->SubsequentTraversal();

    //deleteNodeByIndex() check
    tree->deleteNodeByIndex(2);
    tree->PreorderTraversal();

    //getNowSize() check
    cout<<"tree size(except root):"<<tree->getNowSize()<<endl;
    delete tree;
    tree = NULL;
    system("pause");
    return 0;
}

View Code

测试结果：

数据结构-二叉树 C和C++实现

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

首页 > 代码库 > 数据结构-二叉树 C和C++实现

数据结构-二叉树 C和C++实现

C语言版本

C++版本

看完仍有疑问？有类似问题直接问程序猿