14-数据结构探险系列-树篇

作者: 天涯明月笙 | 来源:发表于2018-07-28 16:18 被阅读37次

14-数据结构探险系列-树篇
11-数据结构探险系列—队列篇
数据结构探险系列—队列篇-学习笔记
数据结构探险之树篇
15-数据结构探险系列-图篇
12-数据结构探险系列—栈篇
数据结构探险系列—栈篇-学习笔记
数据结构算法之美-23讲二叉树基础（上）：树、二叉树
13-数据结构探险系列-线性表篇
Redis为什么用跳表而不用平衡树？

数据结构探险之树篇

树的基本概念

什么是树？

树是节点的有限结合。

二叉树编码要求

数组与树的算法转换

用数组元素为0,表达当前节点不存在节点。

父节点下标*2+1 该节点的左节点；父亲节点下标*2+2 该节点的右节点（基于这是个二叉树）

要求完成的基本操作:

搜索节点：指定数组的下标
添加节点：往哪一个下标的节点添加。左孩子还是右孩子，添加的节点。
删除节点：删除节点的索引
遍历：遍历数组的方法·（数组实现的就简单的按索引遍历）

二叉树数组实现编码实战

3-2-BinaryTreeArray

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.cpp

#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)
// direction决定往左插，还是往右插。
{
    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] << " ";
    }
}

main.cpp

#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();
    
    // 传入节点值，找到index
    int *p = pTree->SearchNode(2);
    cout << endl;
    cout << "***************"<<endl;
    cout << "index:" << *p<<endl;
    cout << "***************"<<endl;
    // 删除传入index
    int temp;
    pTree->DeleteNode(6, &temp);
    cout << endl;
    cout << "delete node=" << temp << endl;
    
    pTree->TreeTraverse();
    cout << endl;
    delete pTree;
    pTree = NULL;
    
    return 0;
}

运行结果：

父节点指针

结点要素:索引数据左孩子指针右孩子指针父结点指针

6-6-BinaryTreeArrayLinkedList

NULL 包含在<stdio.h>

Node.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

Node.cpp

#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

#ifndef TREE_H
#define TREE_H
#include "Node.h"

class Tree
{
public:
    Tree(); //创建树
    ~Tree();//销毁树 del node 删除最根节点即可
    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"
#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;
    }
    // 要把pnode值保存下来。
    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;
    }
    // 把树中删除节点的操作下移到node中来解决
    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()
{
    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;
    return 0;
}

前序遍历：根左右0134256 中序遍历：左根右3140526 后序遍历：左右根 3415620

14-数据结构探险系列-树篇
数据结构探险之树篇树的基本概念什么是树？树是节点的有限结合。上图是我们在树中要基础的概念根节点：A; 双...
11-数据结构探险系列—队列篇
数据结构探险系列—队列篇这是c++远征系列的进阶课程。少了基础语法，对于程序语言的应用，思考。什么是数据结构...
数据结构探险系列—队列篇-学习笔记
数据结构探险系列—队列篇这是c++远征系列的进阶课程。什么是数据结构？一群数据集合和数据之间的关系。是指相互...
数据结构探险之树篇
数据结构探险之树篇什么是树？树是节点的有限结合。根节点：A 双亲：A 孩子：A ：b,c,d 度：A的度为3...
15-数据结构探险系列-图篇
数据结构探险之图篇图的简介什么是图？如下图：无向图 & 有向图(箭头分方向)。图可以看做节点和连线的集合，无...
12-数据结构探险系列—栈篇
数据结构探险—栈篇什么是栈？古代栈就是牲口棚的意思。栈是一种机制：后进先出 LIFO（last in fir...
数据结构探险系列—栈篇-学习笔记
数据结构探险—栈篇什么是栈？古代栈就是牲口棚的意思。栈是一种机制：后进先出 LIFO（last in firs...
数据结构算法之美-23讲二叉树基础（上）：树、二叉树
数据结构算法之美-23讲二叉树基础（上）：树、二叉树特别备注本系列非原创，文章原文摘自极客时间-数据结构算法之...
13-数据结构探险系列-线性表篇
数据结构探险之线性表篇将要学到得, 线性表（链表）整体的路线图如上图所示，线性表要比队列和栈编码上难一点，起到...
Redis为什么用跳表而不用平衡树？
Redis为什么用跳表而不用平衡树？本文是《Redis内部数据结构详解》系列的第六篇。在本文中，我们围绕一个Re...