慕课网学习笔记之数据结构树（C++）

什么是树？——数是节点有限集合

孩子：在上图中BCD都是A的孩子，EF是B的孩子，GH是D的孩子
双亲：A是BCD的双亲，B是EF的双亲，D是GH的双亲，注意这里双亲是指一个节点而非两个。
度：节点的度等于节点的孩子数。A的度为3，B的度为2，D的度为2，CEFGH度都是0。
叶子：终端节点就是叶子。CEFGH
根：非终端节点。ABD
有序树：举例来说：如果EF不可以换顺序，则为有序树。
无序树：相对于有序树。
祖先：当前节点，一直向上所路过的所有节点直到根都是该节点祖先。
子孙：当前节点，向下的所有节点，都是该节点的子孙。
深度：节点深度为该节点所在层数；树的深度为该树的最大深度。
森林：多颗独立的树在一起就成了森林。
二叉树：所有节点的度都小于等于2。
二叉树的遍历：前序遍历，中序遍历，后序遍历。

记忆口诀：根左右、左根右、左右根。
树的应用：压缩软件、人机对战。

二叉树的实现：

1.数组实现
2.链表实现
第一种数组实现的方式较为简单

/*****************************************/
/* 二叉树（数组表示） 

    关于数据与树之间的算法转换 

    int tree[n] 3 5 8 2 6 9 7             

                    3(0)

            5(1)              8(2)

      2(3)      6(4)     9(5)         7(6)


    结论：
        父亲节点下标*2+1 为该节点左孩子的下标 
        父亲节点下标*2+2 为该节点右孩子的下标   
*/ 

当节点不存在时有些不好表达，如果用0来代表无此节点，当存放的数据就是0时便会影响树的操作。
第二种链表实现

/********************************************
    节点要素： 索引   数据  左孩子指针   右孩子指针  父节点指针 
        tree[n] 3 5 8 2 6 9 7   


                    3(0)

            5(1)              8(2)

      2(3)      6(4)     9(5)         7(6)

      下标来表示遍历顺序： 
      前序：0 1 3 4 2 5 6
      中序：3 1 4 0 5 2 6
      后序：3 4 1 5 6 2 0  
*/

tree.h文件：

#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 PreorderTraverse();                                //前序遍历
    void InorderTraverse();                                 //中序遍历 
    void PostorderTraverse();                               //后序遍历                          
private:
    Node *m_pRoot;  
};
#endif

Node.h文件：

#ifndef NODE_H
#define NODE_H

class Node
{
public :
    Node();
    Node *SearchNode(int nodeIndex); //寻找索引号所在节点，若存在返回该节点，否则返回NULL 
    void DeleteNode();               //删除节点 
    void PreorderTraverse();         //前序遍历 
    void InorderTraverse();          //中序遍历             
    void PostorderTraverse();        //后序遍历 
    int index;                       //索引号 
    int data;                        //数据 
    Node *pLChild;                   //左孩子指针 
    Node *pRChild;                   //右孩子指针 
    Node *pParent;                   //双亲指针  

};

#endif

Node.cpp文件：

#include"Node.h"
#include"stdlib.h"
#include
using namespace std; 
Node::Node()                                        //节点构造函数 
{                                                   //初始创建根节点 
    index=0;                                        // 索引初始化为0 
    data=3;                                         // 数据初始为3 
    pLChild=NULL;
    pRChild=NULL;
    pParent=NULL;
}
Node *Node::SearchNode(int nodeIndex)               
{
    if(this->index == nodeIndex)                    //找到返回 
        return this;

    Node *temp;                                     //暂存使用 
    if(this->pLChild != NULL)                       //左孩子存在 
    {   
        if(this->pLChild->index == nodeIndex) 
            return  this->pLChild;  
        else                                        //如果没找到 
        {
        temp=this->pLChild->SearchNode(nodeIndex);  //递归调用 
        if(temp != NULL)
            return temp;                            //找到则返回，否则继续向下 
        }       
    }   

    if(this->pRChild != NULL)                       //右孩子存在 
    {   
        if(this->pRChild->index == nodeIndex)
            return  this->pRChild;                  
        else                                        //未找到 
        {
        temp=this->pRChild->SearchNode(nodeIndex);  //递归调用 
            return temp;                            //直接return 出去 不需要继续找 
        }   
    }       
}

void Node::DeleteNode()                             
{
    if(this->pLChild !=NULL)                        //左孩子存在 
        this->pLChild->DeleteNode();                //递归调用 
    if(this->pRChild !=NULL)
        this->pRChild->DeleteNode();                //递归调用 
    if(this->pParent !=NULL)                        //判断自己是双亲的左孩子or右孩子 
    {
        if(this->pParent->pLChild == this)
            this->pParent->pLChild=NULL;            
        if(this->pParent->pRChild == this)
            this->pParent->pRChild=NULL;            //判断出来使双亲该孩子指为NULL 
    }       
    delete this;                                    //自己的子孙杀完，双亲对自己指向空，可以自杀了 
}
void Node::PreorderTraverse()                       //前序遍历，递归调用 
{
    cout<index<<"          "<data << endl;//打印根 
    if(this->pLChild !=NULL)                            //左 
        this->pLChild->PreorderTraverse();              //递归 
    if(this->pRChild != NULL)                           //右 
        this->pRChild->PreorderTraverse();              //递归 
}
            /**中序遍历和后序遍历同理，只需要更改程序执行顺序**/ 
void Node::InorderTraverse()
{

    if(this->pLChild !=NULL)
         this->pLChild->InorderTraverse();
    cout<index<<"          "<data << endl;
    if(this->pRChild != NULL)
        this->pRChild->InorderTraverse();   
}                       
void Node::PostorderTraverse()
{

    if(this->pLChild !=NULL)
        this->pLChild->PostorderTraverse();
    if(this->pRChild != NULL)
        this->pRChild->PostorderTraverse(); 
    cout<index<<"         "<data << endl;
}

tree.cpp文件：

#include"stdlib.h"
Tree::Tree()
{
    m_pRoot = new Node();                                   //申请内存 
}

Tree::~Tree()
{
//  DeleteNode(0,NULL);                                     //这种方式也能实现销毁树 
    m_pRoot->DeleteNode();
}

Node *Tree::SearchNode(int nodeIndex)
{
    return m_pRoot->SearchNode(nodeIndex);                  //根节点调用查找 
}

bool Tree::AddNode(int nodeIndex,int direction,Node *pNode) // 索引号，左（0）右（1）孩子 ，要插入的节点 
{
    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;                   //这很关键，涉及到删除的成功与否 ，指出插入的节点双亲是谁 
    if(0==direction)
        temp->pLChild = node;
    if(1==direction)
        temp->pRChild = node;

    return true;        
}

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();                                 //调用Node.cpp中的删除方法 
    return true;        
}
/**以下是三种遍历，实现在Node.cpp里定义**/ 
void Tree::PreorderTraverse()
{
    m_pRoot->PreorderTraverse();
}

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

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

domo.cpp文件（用于验证）：

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

int main()  
{ 
    Node node1;
    node1.index=1;
    node1.data = 5;

    Node node2;
    node2.index=2;
    node2.data = 8;

    Node node3;
    node3.index=3;
    node3.data = 2;

    Node node4;
    node4.index=4;
    node4.data = 6;

    Node node5;
    node5.index=5;
    node5.data = 9;

    Node node6;
    node6.index=6;
    node6.data = 7;

    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);

    cout<<"PreorderTraverse: "  <PreorderTraverse();

    cout<<"InorderTraverse: "   <InorderTraverse();

    cout<<"PostorderTraverse: " <PostorderTraverse();

    pTree->DeleteNode(6,NULL);
    cout<<"PreorderTraverse: "  <PreorderTraverse();
    delete pTree;
    pTree= NULL;
    return 0;
}

运行结果：