C++（二叉树的实现）

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

#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;
}