【慕课-数据结构-C++语言】树篇

2018-04-25 本文已影响36人苍云横渡

原文地址：https://www.cloudcrossing.xyz/post/31/

树的定义

树（tree）是包含n（n>0）个结点的有穷集，其中：

（1）每个元素称为结点（node）；
（2）有一个特定的结点被称为根结点或树根（root）。
（3）除根结点之外的其余数据元素被分为m（m≥0）个互不相交的集合T1，T2，……Tm-1，其中每一个集合Ti（1<=i<=m）本身也是一棵树，被称作原树的子树（subtree）。

种类：

无序树：树中任意节点的子结点之间没有顺序关系，这种树称为无序树,也称为自由树;
有序树：树中任意节点的子结点之间有顺序关系，这种树称为有序树；
二叉树：每个节点最多含有两个子树的树称为二叉树；
完全二叉树
满二叉树
霍夫曼树：带权路径最短的二叉树称为哈夫曼树或最优二叉树；

二叉树的遍历有三种：先序遍历、中序遍历、后序遍历。

用数组表示二叉树

新建Tree.h和Tree.cpp

#Tree.h
#ifndef TREE_H
#define TREE_H

class Tree
{
public:
    Tree(int size, int *pRoot);                                         //创建树
    ~Tree();                                                //销毁树
    int *SearchNode(int nodeIndex);                         //根据索引寻找节点
    bool AddNode(int nodeIndex, int direction, int *pNode); //添加节点
    bool DeleteNode(int nodeIndex, int *pNode);             //删除节点
    void TreeTraverse();                                    //遍历节点
private:
    int *m_pTree;
    int m_iSize;
};

#endif TREE_H

#Tree.cpp
#include "stdafx.h"
#include "iostream"
#include "Tree.h"
using namespace std;

Tree::Tree(int size, int *pRoot)
{
    m_iSize = size;
    m_pTree = new int[size];
    for (int i = 0; i < m_iSize; i++)
    {
        m_pTree[i] = 0;
    }
    m_pTree[0] = *pRoot;
}

Tree::~Tree()
{
    delete[]m_pTree;
    m_pTree = NULL;
}

int *Tree::SearchNode(int nodeIndex)
{
    if (nodeIndex < 0 || nodeIndex >= m_iSize)
    {
        return NULL;
    }
    if (m_pTree[nodeIndex] == 0)
    {
        return NULL;
    }
    return &m_pTree[nodeIndex];
}

bool Tree::AddNode(int nodeIndex, int direction, int *pNode)
{
    if (nodeIndex < 0 || nodeIndex >= m_iSize)
    {
        return false;
    }
    if (m_pTree[nodeIndex] == 0)
    {
        return false;
    }

    if (direction == 0) //左边
    {
        if (nodeIndex * 2 + 1 >= m_iSize)
        {
            return false;
        }
        if (m_pTree[nodeIndex * 2 + 1] != 0) //要插入的节点是否为空
        {
            return false;
        }
        m_pTree[nodeIndex * 2 + 1] = *pNode;
    }

    if (direction == 1) //右边
    {
        if (nodeIndex * 2 + 2 >= m_iSize)
        {
            return false;
        }
        if (m_pTree[nodeIndex * 2 + 2] != 0) //要插入的节点是否为空
        {
            return false;
        }
        m_pTree[nodeIndex * 2 + 2] = *pNode;
    }
    return true;
}

bool Tree::DeleteNode(int nodeIndex, int *pNode)
{
    if (nodeIndex < 0 || nodeIndex >= m_iSize)
    {
        return false;
    }
    if (m_pTree[nodeIndex] == 0)
    {
        return false;
    }

    *pNode = m_pTree[nodeIndex];
    m_pTree[nodeIndex] = 0;

    int temp;
    DeleteNode(nodeIndex * 2, &temp);
    DeleteNode(nodeIndex * 2 + 1, &temp);
    return true;
}

void Tree::TreeTraverse()
{
    for (int i = 0; i < m_iSize; i++)
    {
        cout << m_pTree[i] << " ";
    }
}

PS：记住，删除节点的时候，该节点的左右孩子也要删除。

编写一个简单的测试demo.cpp

#demo.cpp
#include "stdafx.h"
#include "stdlib.h"
#include "iostream"
#include "Tree.h"
using namespace std;

int main(void)
{
    int root = 3;
    Tree *pTree = new Tree(10, &root);
    int node1 = 5;
    int node2 = 8;
    pTree->AddNode(0, 0, &node1);
    pTree->AddNode(0, 1, &node2);

    int node3 = 2;
    int node4 = 6;
    pTree->AddNode(1, 0, &node3);
    pTree->AddNode(1, 1, &node4);

    int node5 = 9;
    int node6 = 7;
    pTree->AddNode(2, 0, &node5);
    pTree->AddNode(2, 1, &node6);

    int node = 0;
    pTree->DeleteNode(1, &node);
    cout << "delete_node = " << node << endl;

    pTree->TreeTraverse();

    int *p = pTree->SearchNode(2);
    cout << endl << "node = " << *p << endl;

    delete pTree;

    system("pause");
    return 0;
}

运行结果：

用链表表示二叉树

节点的定义与方法

新建Node.cpp和Node.h

#Node.h
#ifndef NODE_H
#define NODE_H

class Node
{
public:
    Node();
    Node *SearchNode(int nodeIndex);
    void DeleteNode();
    void PreorderTraverse();
    void InorderTraverse();           
    void PostorderTraverse();
    int index;
    int data;
    Node *pLChild;
    Node *pRChild;
    Node *pParent;
};

#endif // NODE_H

#Node.cpp
#include "stdafx.h"
#include "iostream"
#include "Node.h"
using namespace std;


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

Node *Node::SearchNode(int nodeIndex)
{
    if (this->index == nodeIndex)
    {
        return this;
    }

    Node *temp = NULL;
    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);
            if (temp != NULL)
            {
                return temp;
            }
        }
    }

    /*
    if (this->pLChild != NULL) {

        temp = pLChild->SearchNode(nodeIndex);

        if (temp != NULL) {

            return temp;

        }

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

        temp = this->pRChild->SearchNode(nodeIndex);

        if (temp != NULL) {

            return temp;

        }

    }*/

    return NULL;
}

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::PreorderTraverse()
{
    cout << this->index << "  " << this->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 << this->index << "  " << this->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 << this->index << "  " << this->data << endl;
}

对于链表树的寻找、删除以及遍历操作，也许有人会问为什么要在node层级上实现，不在tree层级上实现？

以上的操作，实际上可以看做是对树的对象中的元素进行的操作，即是对node的操作。

在tree类中定义的操作，应该是对整个类的操作，如果将d以上操作设为tree的函数，那么还需要通过类的对象再调用这个对象的元素，相当于多增加了一步操作。通过在node中实现，可以简化步骤，便于理解。

首先来说说节点类的构造函数，节点类一共有五个成员变量：index（序号）、data（数据）、pLChild（左孩子节点类指针）、pRChild（右孩子节点类指针）、pParent（父节点类指针）。这里我们定义初始值分别为0和NULL。

接着来讲讲前序遍历函数 ，因为我们将前序遍历函数从节点类层面转移到树类层面进行编写，所以我们只需考虑单个节点的遍历以及迭代即可。前序遍历的顺序是头左右，所以先打印父节点，然后打印左节点，最后打印右节点。在打印左节点的过程中，我们使用迭代函数打印左子树，右节点同理。

中序遍历函数和后序遍历函数同上，顺序分别为左头右和左右头。

然后我们来讲一下删除节点函数，首先判断当前节点的左右节点是否为空，如果不为空，则使用迭代删除当前节点的左子树和右子树。然后再来判断当前节点的父节点是否为空，如果不为空，则继续判断当前节点是否为父节点的左子树或者右子树，如果是，则将父节点的左孩子指针或者有孩子指针指向NULL。最后释放当前节点。（其中，对父节点的判空是为了防止当前节点是根节点，对空指针进行操作；其次对删除节点的判空是因为存在节点递归删除，空节点的pLchild、pRchild都是不存在的，若不判空就会报错）

最后来将下Node *Node::SearchNode(int nodeIndex)函数，函数传入一个参数：指定节点的数据返回的是节点类指针（因为要返回指定节点的位置）。首先判断当前节点是否为指定节点。如果不是，则创建一个临时节点类指针temp赋值为空。然后先判断左孩子是否为空，不为空则判断左孩子是否为指定节点。如果不是指定节点则对左孩子进行迭代查找，迭代完毕后判断temp是否为空。如果不为空则表示在找到了指定节点，返回。同样，对右孩子进行同样的操作。最后左右孩子的树都找不到指定节点，返回NULL。

树的定义与方法

新建Tree_list.h和Tree_list.cpp

#Tree_list.h
#ifndef TREE_LIST_H
#define  TREE_LIST_H

#include "stdafx.h"
#include "Node.h"

class Tree_list
{
public:
    Tree_list();                                            //创建树
    ~Tree_list();                                           //销毁树
    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 // TREE_LIST_H

#Tree_list.cpp
#include "stdafx.h"
#include "iostream"
#include "Tree_list.h"
using namespace std;


Tree_list::Tree_list()
{
    m_pRoot = new Node();
}

Tree_list::~Tree_list()
{
    //DeleteNode(0, NULL);
    m_pRoot->DeleteNode();
}

Node *Tree_list::SearchNode(int nodeIndex)
{
    return m_pRoot->SearchNode(nodeIndex);
}

bool Tree_list::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;

    if (direction == 0)
    {
        temp->pLChild = node;
    }
    if (direction == 1)
    {
        temp->pRChild = node;
    }
    return true;
}

bool Tree_list::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_list::PreorderTraverse()
{
    m_pRoot->PreorderTraverse();
}

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

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

首先说说树类的构造函数，树类的实例化实质就是创建树的根节点m_pRoot，所以我们只要m_pRoot = new Node()就可以了。

接着讲遍历函数，直接调用我们前边写好的节点的遍历函数即可。查找函数也类似，直接调用写好的节点的查找函数即可。

然后来讲讲添加节点函数，传入的参数有三个，第一个是传入的位序（从0开始，根节点是0），第二个是方向（0为左，1为右），第三个为指定的节点指针。首先创建一个临时节点类指针temp，将查找指定位序结果赋值给temp。接着判断temp是否为NULL，如果为NULL说明找不到指定的位序返回False。如果不为NULL，new一个节点类指针node，将指定节点pNode赋值给node，再把node的父节点指针指向temp（在指定位序的节点）。最后判断要插入的是右节点还是左节点，如果direction为0则将node挂载到temp的左节点，如果direction为1则将node挂载到temp的右节点。

不能直接把pNode挂载到树中，要先将其数据拷贝出来， pNode作为一个外边传过来的数据，如果被外边的函数或者其他语句修改，那么它的完整性就不存在了，对于树来说影响很大，往往会造成致命错误
如果直接将pNode这个节点挂载到树中，因为pNode是一个临时节点所以用根节点的孩子指针指向它没有什么意义，在addNode这个函数执行完之后，pNode申请的内存就会被回收。

接着说说删除函数，传入的参数为指定的位序和一个用来存储要删除的节点的节点类指针pNode。和添加节点类似，首先需要先找到指定的位序并判断是否为NULL。然后判断pNode是否为NULL，如果不是，则说明要将删除的节点取出来保存，pNode->data = temp->data。最后释放指定位序的节点。

最后说一下析构函数，其实质就是释放树的所有节点，包括根节点，所以我们只需要调用根节点的删除节点函数就可以了。

本次笔记代码已上传到 github

【慕课-数据结构-C++语言】树篇

树的定义

相关术语

用数组表示二叉树

用链表表示二叉树

节点的定义与方法

树的定义与方法

猜你喜欢

热点阅读