美文网首页数据结构与算法程序员C语言
数据结构探险之树篇

数据结构探险之树篇

作者: 天涯明月笙 | 来源:发表于2017-09-11 14:13 被阅读157次

    数据结构探险之树篇

    什么是树？

    树是节点的有限结合。

    1正2倒 概念
    • 根节点：A
    • 双亲：A
    • 孩子：A ：b,c,d
    • 度：A的度为3，因为它接着三个节点BCD。b的度为2，EF.(直接的孩子)
    • 叶子（终端节点）：CEFGH
    • 根（非终端节点）：ABD。
    • 有序树 & 无序树：如果b的孩子ef。不可以换顺序就是有序树。可以换顺序就是无序树
    • 祖先：对E来说b和a都是它的祖先。对G来说D & A 是它的祖先。（从它一直向上一直到根节点。之前路过的所有节点）
    • 子孙：对A来说底下所有都是子孙。对d来说，G & H是它的子孙。（从该节点开始，伸出节点，以及伸出节点的子节点）

    树的深度

    树的深度
    • 第一层节点深度为1.第二层2，第三层3.
    • 树的深度是节点最大深度。

    森林

    森林

    对于第一幅图。我们可以看出两个不同的子树。

    二叉树

    二叉树的判定

    作图根节点度为3，不为二叉树。右边为二叉树。

    二叉树的遍历

    二叉树的遍历

    遍历：

    • 前序遍历（先根后左右）
    • 中序遍历 (先左，然后根，最后右)
    • 后序遍历 (先左，然右，最后根)

    相对于二叉树的根来说的。

    树的应用：

    • 赫夫曼树（用于压缩软件）
    • 树能够实现人机对战

    二叉树数组实现编码说明

    二叉树编码要求 数组与树的算法转换

    用数组元素为0.表达孩子不存在。

    父节点下标*2+1 该节点的左节点
    父亲节点下标*2+2 该节点的右节点

    • 搜索节点：指定数组的下标
    • 添加节点：往哪一个下标的节点添加。左孩子还是右孩子，添加的节点。
    • 删除节点：删除节点的索引
    • 遍历：遍历数组的方法·

    二叉树数组实现编码实战

    #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


#include"Tree.h"
#include<iostream>
using namespace std;

Tree::Tree(int size, int *pRoot)
{
    m_iSize = size;
    m_pTree = new int[size];
    for (int i = 0; i < size; 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 || m_pTree[nodeindex] == 0)
    //节点没有
    {
        return false;
    }
    switch (direction)
    {
    //0值定义为左孩子
    case 0:
        //不等于0，说明插入过了
        if (nodeindex * 2 + 1 >= m_iSize || m_pTree[nodeindex * 2 + 1] != 0)
        {
            return false;
        }
        m_pTree[nodeindex * 2 + 1] = *pNode;
        break;
    case 1:
        if (nodeindex * 2 + 2 >= m_iSize || m_pTree[nodeindex * 2 + 2] != 0)
        {
            return false;
        }
        m_pTree[nodeindex * 2 + 2] = *pNode;
        break;
    }
    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;

    return true;
}

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


#include <iostream>
#include <stdlib.h>
#include "Tree.h"
using namespace std;
/********************************************************************
/*        数组---树  Tree【】=3 5 8 2 6 9 7
3(0)                                左孩子小标=父节点下标*2+1
5(1)              8(2)                       右孩子小标=父节点下标*2+2
2(3)      6(4)  9(5)        7(6)

**********************************************************************/
int main()
{
    int root = 3;
    Tree *pTree = new Tree(10, &root);
    int node1 = 5;
    int node2 = 8;
    //0号节点插入左孩子。
    pTree->AddNode(0, 0, &node1);
    //0号节点插入右孩子。
    pTree->AddNode(0, 1, &node2);

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

    pTree->AddNode(2, 0, &node5);
    pTree->AddNode(2, 1, &node6);
    pTree->TreeTraverse();
    int *p = pTree->SearchNode(2);
    int temp;
    pTree->DeleteNode(6, &temp);
    cout << endl;
    cout << "index:" << *p << endl;
    cout << endl;
    cout << "delete node=" << temp << endl;

    pTree->TreeTraverse();
    cout << endl << "node=" << *pTree->SearchNode(2) << endl;
    delete pTree;
    pTree = NULL;

    system("pause");
    return 0;
}

    运行结果：

    运行结果

    二叉树链表实现编码

    二叉树链表实现
    • 前序遍历、中序遍历、后序遍历
    • 结点要素：索引、数据、左孩子指针、右孩子指针
    • 结点左孩子指针找到左孩子。右孩子指针找到右孩子
    • 通过搜索先找到要挂载的结点。在左右两边分别挂载左孩子右孩子。
    • 删除的时候进行级联删除
    • 销毁树。一级一级都删除。
    • 前序遍历：0-1-3-4-2-5-6
    • 中序遍历：3-1-4-0-5-2-6(左根右)
    • 后序遍历：3-4-1-5-6-2-0（左右根）
    #include<stdlib.h>
#include"Tree.h"
#include<iostream>
using namespace std;
/********************************************************************
 【数据结构探险---树篇】
     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 PreorderTravers();//前序遍历
    void InorderTravers(); //中序遍历
    void PostorderTravers();//后序遍历
    --------------------------------------------------------------------
    二叉树--链表实现 
                  (0)                                  左孩子索引=父节点索引*2+1
       5(1)              8(2)                       右孩子索引=父节点索引*2+2
2(3)      6(4)  9(5)        7(6)
前序遍历：根左右0134256    中序遍历：左根右3140526   后序遍历：左右根 3415620
**********************************************************************/

int main(void)
{   
    int root=3;
    Tree *pTree=new Tree(10,&root);

    delete pTree;
    pTree=NULL;
    system("pause");
    return 0;
}

    二叉树数组实现原理演示

    二叉树编码实战

    父节点指针

    NULL 包含在<stdio.h>

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

    }

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

    tree.h & tree.cpp:

    #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 <iostream>
using namespace std;
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) {
    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;//注意，要在添加时把父节点也记着
    
    //0挂左，1挂右
    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 == 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();
}

    main.cpp:

    #include "Tree.h"
#include <stdlib.h>
#include <iostream>
using namespace std;

/*
二叉树--链表实现

           (0)                                  左孩子索引 = 父节点索引 * 2 + 1
    5(1)         8(2)                           右孩子索引 = 父节点索引 * 2 + 2
2(3)   6(4)   9(5)   7(6)

前序遍历：根左右0134256    中序遍历：左根右3140526   后序遍历：左右根 3415620
*/
int main()
{
    int root = 3;
    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 *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);

    pTree->DeleteNode(6, NULL);//删除失败
    cout << "前序遍历" << endl;
    pTree->PreorderTraversal();
    /*cout << "中序遍历" << endl;
    pTree->InorderTraversal();
    cout << "后序遍历" << endl;
    pTree->PostorderTraversal();*/
    delete pTree;
    pTree = NULL;
    system("pause");
    return 0;


    system("pause");
    return 0;
}
    三种遍历运行结果

    相关文章

      网友评论

      • 知识学者::grin: 向大佬致敬:smiley: 等我把语法讲完了，也试一试数据结构
        。图和树，链表哪里一团糟糕。
        天涯明月笙:哈哈。加油，一点一点进步。最近忙都更新的少了。我会尽力多更新点数据结构的

      本文标题：数据结构探险之树篇

      本文链接：https://www.haomeiwen.com/subject/ouqfsxtx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      数据结构与算法

      程序员

      C语言

      C++

      数据结构

      c++

      关于我们|服务条款|联系我们|数据结构探险之树篇|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！