數據結構——樹

樹，主要內容:用數組和線性表分別實現二叉樹，線性表二叉樹中包含前序遍歷，中序遍歷，后續(xù)遍歷。文中代碼均已在VS2015上測試，空指針均為nullptr（C++11）。參考來源：慕課網

樹

樹是節(jié)點的有限集合。

節(jié)點的度：一個節(jié)點含有的子樹的個數稱為該節(jié)點的度；

葉節(jié)點或終端節(jié)點：度為0的節(jié)點稱為葉節(jié)點；

非終端節(jié)點或分支節(jié)點：度不為0的節(jié)點；

雙親節(jié)點或父節(jié)點：若一個節(jié)點含有子節(jié)點，則這個節(jié)點稱為其子節(jié)點的父節(jié)點；

孩子節(jié)點或子節(jié)點：一個節(jié)點含有的子樹的根節(jié)點稱為該節(jié)點的子節(jié)點；

兄弟節(jié)點：具有相同父節(jié)點的節(jié)點互稱為兄弟節(jié)點；

樹的度：一棵樹中，最大的節(jié)點的度稱為樹的度；

節(jié)點的層次：從根開始定義起，根為第1層，根的子節(jié)點為第2層，以此類推；

樹的高度或深度：樹中節(jié)點的最大層次；

堂兄弟節(jié)點：雙親在同一層的節(jié)點互為堂兄弟；

節(jié)點的祖先：從根到該節(jié)點所經分支上的所有節(jié)點；

子孫：以某節(jié)點為根的子樹中任一節(jié)點都稱為該節(jié)點的子孫；

森林：由m（m>=0）棵互不相交的樹的集合稱為森林。

二叉樹

所有節(jié)點的度都小于等于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,

二叉樹實例

數組二叉樹。

下面的數字為數組下標。

節(jié)點的左孩子下標是該節(jié)點下標*2+1。

節(jié)點的左孩子下標是該節(jié)點下標*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)//向左節(jié)點插入 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)//向右節(jié)點插入 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();//創(chuàng)建樹
    ~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;
}
最后編輯于 ：
?著作權歸作者所有,轉載或內容合作請聯系作者
【社區(qū)內容提示】社區(qū)部分內容疑似由AI輔助生成，瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明：文章內容（如有圖片或視頻亦包括在內）由作者上傳并發(fā)布，文章內容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關閱讀更多精彩內容

  • 這篇文章收錄在我的 Github 上 algorithms-tutorial，另外記錄了些算法題解，感興趣的可以看...
    Lindz閱讀 15,673評論 4贊 15
  • 樹：是n（n>=0）個節(jié)點的有限集，n＝０時稱為空樹。在任何一棵非空樹中：1 有且僅有一個特定的稱為根（root）...
    安靜1337閱讀 892評論 0贊 51
  • 1. 樹 1. 樹的定義 樹（Tree）：是n（n>=0）個節(jié)點的有限集，它或為空樹（n=0）；或為非空樹，對于非...
    Lost_Robot閱讀 670評論 0贊 1
  • 樹的存儲結構一(分為順序存儲和鏈式存儲[二叉鏈表])樹的存儲結構二 二叉樹 二叉樹：是n（n≥0）個結點的有限集合...
    不會游泳De魚閱讀 734評論 0贊 0
  • 樹的概念 樹（英語：tree）是一種抽象數據類型（ADT）或是實作這種抽象數據類型的數據結構，用來模擬具有樹狀結構...
    LittlePy閱讀 9,088評論 0贊 4

友情鏈接更多精彩內容