数据结构——树

树，主要内容:用数组和线性表分别实现二叉树，线性表二叉树中包含前序遍历，中序遍历，后续遍历。文中代码均已在VS2015上测试，空指针均为nullptr（C++11）。参考来源：慕课网

树

树是节点的有限集合。

节点的度：一个节点含有的子树的个数称为该节点的度；

叶节点或终端节点：度为0的节点称为叶节点；

非终端节点或分支节点：度不为0的节点；

双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；

孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；

兄弟节点：具有相同父节点的节点互称为兄弟节点；

树的度：一棵树中，最大的节点的度称为树的度；

节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；

树的高度或深度：树中节点的最大层次；

堂兄弟节点：双亲在同一层的节点互为堂兄弟；

节点的祖先：从根到该节点所经分支上的所有节点；

子孙：以某节点为根的子树中任一节点都称为该节点的子孙；

森林：由m（m>=0）棵互不相交的树的集合称为森林。

二叉树

所有节点的度都小于等于2

遍历：前序遍历（根左右）、中序遍历（左根右）、后序遍历（左右根）。

                                0

                1                               2

        3               4               5               6

    7       8       9       10      11      12      13      14

前序遍历：0,1,3,7,8,4,9,10,2,5,11,12,6,13,14,
中序遍历：7,3,8,1,9,4,10,0,11,5,12,2,13,6,14,
后序遍历：7,8,3,9,10,4,1,11,12,5,13,14,6,2,0,

二叉树实例

数组二叉树。

下面的数字为数组下标。

节点的左孩子下标是该节点下标*2+1。

节点的左孩子下标是该节点下标*2+2。

                            0

            1                               2

    3               4               5               6

7       8       9       10      11      12      13      14

代码：

【Tree.h】

#ifndef TREE_H
#define TREE_H

【Tree.cpp】

#include "Tree.h"
#include <iostream>
using namespace std;
Tree::Tree(int size,int *pRoot)
{
    m_iSize = size;
    m_pTree = new int[m_iSize];
    for (int i = 0;i < size;i++)
    {
        m_pTree[i] = 0;
    }
    m_pTree[0] = *pRoot;
}

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

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

bool Tree::AddNode(int nodeIndex, int direction, int * pNode)
{ 
    if (nodeIndex < 0 || nodeIndex >= m_iSize)
    {
        return nullptr;
    }
    if (m_pTree[nodeIndex]==0)
    {
        return false;
    }
    if (direction == 0)//向左节点插入 nodeIndex *2 + 1
    {
        if (/*nodeIndex * 2 + 1 < 0 ||*/ 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)//向右节点插入 nodeIndex *2 + 2
    {
        if (/*nodeIndex * 2 + 2 < 0 ||*/ nodeIndex * 2 + 2 >= m_iSize)
        {
            return false;
        }
        if (m_pTree[nodeIndex * 2 + 2] != 0)
        {
            return false;
        }
        m_pTree[nodeIndex * 2 + 2] = *pNode;
    }
}

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;
    return true;
}

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

【main.cpp】

#include <iostream>
#include "Tree.h"
using namespace std;
int main(void)
{
    int root = 1;
    Tree *pTree = new Tree(10, &root);
    int node1 = 1;
    int node2 = 2;
    pTree->AddNode(0, 0, &node1);
    pTree->AddNode(0, 1, &node2);
    int node3 = 3;
    int node4 = 4;
    pTree->AddNode(1, 0, &node3);
    pTree->AddNode(1, 1, &node4);
    int node5 = 5;
    int node6 = 6;
    pTree->AddNode(2, 0, &node5);
    pTree->AddNode(2, 1, &node6);
    int node = 0;
    pTree->DeleteNode(6, &node);
    pTree->TreeTraverse();
    int *p = pTree->SearchNode(2);
    cout << *p << endl;
    delete pTree;
    pTree = nullptr;
    return 0;
}

线性表二叉树

代码：
【Node.h】

#ifndef  NODE_H
#define  NODE_H
#include <iostream>
using namespace std;
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

【Node.cpp】

#include "Node.h"

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

Node* Node::SearchNode(int nodeIndex)
{
    if (this->index==nodeIndex)
    {
        return this;
    }
    Node *temp = nullptr;
    if (this->pLChild!=nullptr)
    {
        if (this->pLChild->index==nodeIndex)
        {
            return this->pLChild;
        }
        else
        {
            temp = this->pLChild->SearchNode(nodeIndex);
            if (temp != nullptr)
            {
                return temp;
            }
        }
    }
    if (this->pRChild != nullptr)
    {
        if (this->pRChild->index == nodeIndex)
        {
            return this->pRChild;
        }
        else
        {
            temp = this->pRChild->SearchNode(nodeIndex);
            if (temp != nullptr)
            {
                return temp;
            }
        }
    }
    return nullptr;
}

void Node::DeleteNode()
{
    if (this->pLChild != nullptr)
    {
        this->pLChild->DeleteNode();
    }
    if (this->pRChild != nullptr)
    {
        this->pRChild->DeleteNode();
    }
    if (this->pParent != nullptr)
    {
        if (this->pParent->pLChild == this)
        {
            this->pParent->pLChild = nullptr;
        }
        if (this->pParent->pRChild == this)
        {
            this->pParent->pRChild = nullptr;
        }
    }
    delete this;
}

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

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

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

【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 PreorderTraversal();//前序遍历
    void InorderTraversal();//中序遍历
    void PostorderTraversal();//后序遍历
private:
    Node *m_pRoot;
};
#endif

【Tree.cpp】

#include "Tree.h"

Tree::Tree()
{
    m_pRoot = new Node();
    m_pRoot->pLChild = nullptr;
    m_pRoot->pRChild = nullptr;
    m_pRoot->pParent = nullptr;
}

Tree::~Tree()
{
    m_pRoot->DeleteNode();//或者DeleteNode(0,nullptr);
}

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

bool Tree::AddNode(int nodeIndex, int direction, Node * pNode)
{
    Node *temp = SearchNode(nodeIndex);
    if (temp==nullptr)
    {
        return false;
    }
    Node *node = new Node();
    if (node==nullptr)
    {
        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::DeleteNode(int nodeIndex, Node * pNode)
{

    Node *temp = SearchNode(nodeIndex);
    if (temp == nullptr)
    {
        return false;
    }
    if (pNode!=nullptr)
    {
        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();
}

【main.cpp】

#include "Tree.h"
int main()
{
    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 = new Tree();
    tree->AddNode(0, 0, node1);
    tree->AddNode(0, 1, node2);
    tree->AddNode(1, 0, node3);
    tree->AddNode(1, 1, node4);
    tree->AddNode(2, 0, node5);
    tree->AddNode(2, 1, node6);
    tree->DeleteNode(5, nullptr);
    tree->PreorderTraversal();
    cout << "------------" << endl;
    tree->InorderTraversal();
    cout << "------------" << endl;
    tree->PostorderTraversal();
    return 0;
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 216,324评论 6赞 498
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 92,356评论 3赞 392
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 162,328评论 0赞 353
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 58,147评论 1赞 292
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 67,160评论 6赞 388
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 51,115评论 1赞 296
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 40,025评论 3赞 417
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,867评论 0赞 274
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 45,307评论 1赞 310
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,528评论 2赞 332
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,688评论 1赞 348
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,409评论 5赞 343
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 41,001评论 3赞 325
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,657评论 0赞 22
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,811评论 1赞 268
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,685评论 2赞 368
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,573评论 2赞 353

推荐阅读更多精彩内容

  • 2. 数据结构 - 树
    这篇文章收录在我的 Github 上 algorithms-tutorial，另外记录了些算法题解，感兴趣的可以看...
    Lindz阅读 15,206评论 4赞 15
  • 数据结构－树
    树：是n（n>=0）个节点的有限集，n＝０时称为空树。在任何一棵非空树中：1 有且仅有一个特定的称为根（root）...
    安静1337阅读 819评论 0赞 51
  • 数据结构 树 二叉树
    1. 树 1. 树的定义 树（Tree）：是n（n>=0）个节点的有限集，它或为空树（n=0）；或为非空树，对于非...
    Lost_Robot阅读 596评论 0赞 1
  • 数据结构--树
    树的存储结构一(分为顺序存储和链式存储[二叉链表])树的存储结构二 二叉树 二叉树：是n（n≥0）个结点的有限集合...
    不会游泳De鱼阅读 595评论 0赞 0
  • 数据结构---树的基本概念和性质
    树的概念 树（英语：tree）是一种抽象数据类型（ADT）或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构...
    LittlePy阅读 8,829评论 0赞 4