欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

C++(二叉树的实现)

程序员文章站 2022-07-07 22:27:13
这里我分享下一段二叉树的代码,有详细注释。 #ifndef Node_h_ #define Node_h_ class Node { public: N...

这里我分享下一段二叉树的代码,有详细注释。

#ifndef Node_h_
#define Node_h_

class Node
{
public:
    Node();
    Node* SearchNode(int nodeIndex);
    void DeleteNode();
    void PreorderTraversal();
    void InorderTraversal();
    void PostorderTraversal();
    int index;
    int data;
    Node* pLChild;
    Node* pRChild;
    Node* pParent;


};
#endif
#include "Node.h"

#include
using namespace std;


Node::Node()
{
    index = 0;
    data = 0;
    pLChild =NULL;
    pRChild = NULL;
    pParent = NULL;
}

/*
函数名称:寻找节点
函数功能:寻找指定索引下标的节点,为增加加点,删除节点等函数做辅助。
*/
Node* Node::SearchNode(int nodeIndex)
{
    Node* temp=NULL;
    if (this->index == nodeIndex)//这里用到了this指针,这个指针其实就是调用SearchNode()函数的对象的地址。
    {
        return this;//如果要寻找的索引就是这个调用这个函数对象的索引,返回就是这个对象地址。
    }
    if (this->pLChild != NULL)//上面if不成立,就调用这个函数对象,就去寻找对象节点的左孩子。
    {
        if (this->pLChild->index == nodeIndex)//判断左孩子索引是不是要寻找节点索引。
        {
            return this->pLChild;//是就返回左孩子地址。
        }   
        else//这里用else表示继续向下寻找
        {

            temp=this->pLChild->SearchNode(nodeIndex);//这里用来递归调用思想,不断循环调用SearchNode()函数,将后面
                                                                        //每个节点都要找到,找到后,要有一个返回值,于是要有一个Node*型变量存储。
            if (temp != NULL)
            {
                return temp;
            }
        }
    }
    if (this->pRChild != NULL)//同上面的左孩子寻找方式
    {
        if (this->pRChild->index == nodeIndex)
        {
            return this->pRChild;
        }
        else
        {
            temp=this->pRChild->SearchNode(nodeIndex);//同上
            if (temp != NULL)
            {
                return temp;
            }
        }
    }
    return NULL;
}
/*
函数名称:删除节点
函数功能:从调用这个DeleteNode()函数的对象节点开始删除,把后面的节点全部删完 
*/
void Node::DeleteNode()
{
    if (this->pLChild != NULL)
    {
        this->pLChild->DeleteNode();//将左孩子及左孩子后面的节点删除,其实顺序是从最后一个节点开始
    }
    if (this->pRChild != NULL)
    { 
        this->pRChild->DeleteNode();//将右孩子及右孩子后面的节点删除,其顺序也是从最后一个节点开始往上删除
    }   
    if (this->pParent != NULL)
    {
        if (this->pParent->pLChild == this)
        {
            this->pParent->pLChild = NULL;
        }
        if (this->pParent->pRChild == this)
        {
            this->pParent->pRChild = NULL;
        }
    }
    delete this;
}

/*
函数名称:前序遍历(中左右)//(中在哪里就是什么遍历)
函数功能:按中左右顺序遍历一棵二叉树
*/
void Node::PreorderTraversal()
{
    cout << this->index << ":" << this->data << endl;
    if (this->pLChild != NULL)
    {
        this->pLChild->PreorderTraversal();//这里遍历用了迭代的思想
    }
    if (this->pRChild != NULL)
    {
        this->pRChild->PreorderTraversal();
    }

}

/*
函数名称:中序遍历(左中右)
函数功能:按左中右顺序遍历一棵二叉树
*/
void Node::InorderTraversal()
{

    if (this->pLChild != NULL)
    {
        this->pLChild->InorderTraversal();
    }
    cout << this->index << ":" << this->data << endl;
    if (this->pRChild != NULL)
    {
        this->pRChild->InorderTraversal();
    }
}
/*
函数名称:后序遍历(左右中)
函数功能:按左右中顺序遍历一棵二叉树
*/
void Node::PostorderTraversal()
{
    if (this->pLChild != NULL)
    {
        this->pLChild->PostorderTraversal();
    }

    if (this->pRChild != NULL)
    {
        this->pRChild->PostorderTraversal();
    }

    cout << this->index << ":" << this->data << endl;
}
#ifndef Tree_h_
#define Tree_h_

#include"Node.h"
class Tree
{
public:
    Tree();
    ~Tree();
    Node* SearchNode(int nodeIndex);
    bool AddNode(int nodeIndex, int direction, Node* pNode);
    bool DeleteNode(int nodeIndex, Node* pNode);
    void PreorderTraversal();
    void InorderTraversal();
    void PostorderTraversal();

private:
    Node* m_pRoot;
};
#endif
#include"Tree.h"
#include
using namespace std;
Tree::Tree()
{
    m_pRoot = new Node();
}

Tree::~Tree()
{
    DeleteNode(0, NULL);
}
/*
函数名称:寻找指定下标节点
函数实现:主要放在Node函数下实现,讲解见Node* Node::SearchNode(int nodeIndex)
*/
Node* Tree::SearchNode(int nodeIndex)
{
    return m_pRoot->SearchNode(nodeIndex);
}
/*
函数名称:增加节点
函数实现参数:nodeIndex为挂载的父节点下标,direction可以区0或1,0代表即将挂的是左孩子,1表示即将挂的是右孩子
                      pNode表示即将挂的节点的地址,*pNode表示挂的节点。
*/
bool Tree::AddNode(int nodeIndex, int direction, Node* pNode)
{
    Node*Temp=SearchNode(nodeIndex);//寻找节点为基础,找到要挂的父节点
    if (Temp == NULL)//表示没有找到要挂载的父节点
    {
        return false;
    }
    Node* node = new Node();//堆上开辟一个内存空间,来当成挂载节点
    if (node == NULL) return false;//表示堆上没有开辟成功,几率低但还是有可能的

    node->index = pNode->index;
    node->data = pNode->data;
    node->pParent = Temp;//将node和Temp建立了关系

    if (direction == 0)
    {
        Temp->pLChild = node;
    }
    if (direction == 1)
    {
        Temp->pRChild = node;
    }
    return true;
}
/*
函数名称:删除指定索引下标的节点
函数实现:nodeIndex为要删除的节点下标,pNode要删除节点的传入地址
*/
bool Tree::DeleteNode(int nodeIndex, Node* pNode)
{
    Node*Temp = SearchNode(nodeIndex);//寻找到要删除的节点
    if (Temp == NULL)//表示没有找到指定下标节点
    {
        return false;
    }
    if (pNode != NULL)
    {
        pNode->data = Temp->data;
    }
    Temp->DeleteNode();
    return true;
}

void Tree::PreorderTraversal()
{
    m_pRoot->PreorderTraversal();
}

void Tree::InorderTraversal()
{
    m_pRoot->InorderTraversal();
}
void Tree::PostorderTraversal()
{
    m_pRoot->PostorderTraversal();
}

最后是主函数,调用上面的函数;

#include
#include
#include "Tree.h"
#include "Node.h"
using namespace std;

int main()
{
    /*
    下面是在堆上分配6个节点内存空间,每个内存空间有索引和数值
    */
    Node* node1=new Node();
    node1->index = 1;
    node1->data = 5;

    Node* node2 = new Node();
    node2->index = 2;
    node2->data = 8;

    Node* node3 = new Node();
    node3->index = 3;
    node3->data = 2;

    Node* node4 = new Node();
    node4->index = 4;
    node4->data = 6;

    Node* node5 = new Node();
    node5->index = 5;
    node5->data = 9;

    Node* node6 = new Node();
    node6->index = 6;
    node6->data = 7;

    //分配一个指针,来调用Tree类的相关函数
    Tree* pTree = new Tree();

    pTree->AddNode(0, 0,node1);
    pTree->AddNode(0, 1, node2);

    pTree->AddNode(1, 0, node3);
    pTree->AddNode(1, 1, node4);

    pTree->AddNode(2, 0, node5);
    pTree->AddNode(2, 1, node6);
    //在构造函数中产生的初始化节点后增加了6个节点
    pTree->DeleteNode(0, NULL);//删除一个节点
    pTree->PreorderTraversal();//前序遍历

    delete pTree;
    system("pause");
    return 0;
}