数据结构探险（四）—— 树

2023-12-28 19:58
文章标签 数据结构 探险

本文主要是介绍数据结构探险（四）—— 树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

  • 树是节点的有限集合
  • 树的用途：压缩软件 哈夫曼树；人机对战（不断做树得搜索）；

二叉树数组

c语言表示：
在这里插入图片描述
在这里插入图片描述

Tree.h

#ifndef TREE_H_INCLUDED
#define TREE_H_INCLUDEDclass 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_INCLUDED

Tree.cpp

#include<iostream>
#include"Tree.h"
using namespace std;Tree::Tree(int size,int *pRoot)
{m_iSize=size;m_pTree= new int[size];//从堆中分配了size个int大小的内存，并且pTree指向他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)
{//先找到结点//nodeindex本身不合法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;//pNode是指针 *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;//pNode是指针 *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;return true;
}void Tree::TreeTraverse() //用数组表示的树，直接循环输出即可
{for(int i=0;i<m_iSize;i++){cout<<m_pTree[i]<<" ";}
}
测试
#include<stdlib.h>
#include<iostream>
#include"Tree.h"using namespace std;int main()
{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(6,&node);cout<<"node = "<<node<<endl;pTree->TreeTraverse();int *p=pTree->SearchNode(2);cout<<endl<<"node = "<<*p<<endl;delete pTree;system("pause");return 0;
}

在这里插入图片描述

二叉树链表

在这里插入图片描述

Tree.h

#include"Node.h"
#include<stdio.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;
};

Tree.cpp

#include"Tree.h"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;// 注意注意：：注意在添加时要把父节点也记着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();//temp以及以下的子节点都删除return true;
}void Tree::PreorderTraversal()
{m_pRoot->PreorderTraversal();//从根开始遍历
}void Tree::InorderTraversal()
{m_pRoot->InorderTraversal();
}void Tree::PostorderTraversal()
{m_pRoot->PostorderTraversal();}

Node.h

#ifndef NODE_H_INCLUDED
#define NODE_H_INCLUDEDclass 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_H_INCLUDED

Node.cpp

#include<stdlib.h>
#include<stdio.h>
#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;}
测试：

demo.cpp

#include<stdlib.h>
#include"Tree.h"
#include"Node.h"
#include<iostream>
using namespace std;/*(0)5(1)         8(2)
2(3)    6(4)   9(5)   7(6)
*/
using namespace std;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(6,NULL);
//     tree->DeleteNode(5,NULL);tree->DeleteNode(2,NULL);//     cout<<"--------------pre----------------"<<endl;
//     tree->PreorderTraversal();
//     cout<<"--------------in----------------"<<endl;
//     tree->InorderTraversal();cout<<"--------------poster----------------"<<endl;tree->PostorderTraversal();delete tree;system("pause");return 0;}

在这里插入图片描述

这篇关于数据结构探险（四）—— 树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/547115。

相关文章

【数据结构】线性表：顺序表

【数据结构】线性表：顺序表

文章目录 1. 线性表2. 顺序表2.1 概念及结构2.2 接口实现2.3 顺序表的问题及思考 1. 线性表 线性表是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式
阅读更多...
数据结构9——排序

数据结构9——排序

一、冒泡排序 冒泡排序（Bubble Sort），顾名思义，就是指越小的元素会经由交换慢慢“浮”到数列的顶端。 算法原理 从左到右，依次比较相邻的元素大小，更大的元素交换到右边；从第一组相邻元素比较到最后一组相邻元素，这一步结束最后一个元素必然是参与比较的元素中最大的元素；按照大的居右原则，重新从左到后比较，前一轮中得到的最后一个元素不参4与比较，得出新一轮的最大元素；按照上述规则，每一轮结
阅读更多...
算法与数据结构面试宝典——回溯算法详解（C#，C++）

算法与数据结构面试宝典——回溯算法详解（C#，C++）

文章目录 1. 回溯算法的定义及应用场景2. 回溯算法的基本思想3. 递推关系式与回溯算法的建立4. 状态转移方法5. 边界条件与结束条件6. 算法的具体实现过程7. 回溯算法在C#，C++中的实际应用案例C#示例C++示例 8. 总结回溯算法的主要特点与应用价值 回溯算法是一种通过尝试各种可能的组合来找到所有解的算法。这种算法通常用于解决组合问题，如排列、组合、棋盘游
阅读更多...
嵌入式学习——数据结构（哈希、排序）——day50

嵌入式学习——数据结构（哈希、排序）——day50

1. 查找二叉树、搜索二叉树、平衡二叉树 2. 哈希表——人的身份证——哈希函数 3. 哈希冲突、哈希矛盾 4. 哈希代码 4.1 创建哈希表 4.2  5. 算法设计 5.1 正确性 5.2 可读性（高内聚、低耦合） 5.3 健壮性 5.4 高效率（时间复杂度）时间复杂度越低，效率越高， 5.5 低储存（空间复杂度）空间复杂度越低，存储空间越少 6.排序算法 6.1 冒
阅读更多...
【数据结构与算法 经典例题】使用队列实现栈（图文详解）

【数据结构与算法 经典例题】使用队列实现栈（图文详解）

💓 博客主页：倔强的石头的CSDN主页               📝Gitee主页：倔强的石头的gitee主页    ⏩ 文章专栏：《数据结构与算法 经典例题》C语言                                   期待您的关注 ​​ 目录  一、问题描述 二、前置知识 三、解题思路 四、C语言实现代码 🍃队列实现代码：
阅读更多...
数据结构：二叉树详解 c++信息学奥赛基础知识讲解

数据结构：二叉树详解 c++信息学奥赛基础知识讲解

目录 一、二叉树的定义 二、二叉树的形态 三、二叉树的性质 四、二叉树的存储 五、二叉树的创建与遍历（递归） 六、二叉树实现 创建二叉树 展示二叉树 1、计算数的高度 2、计算数的叶子数量 3、计算数的宽度 4、层次遍历 5、前序遍历 递归写法 非递归写法 6、中序遍历 递归写法 非递归写法 7、后序遍历 递归写法 非递归写法 8、输出根节点到所有叶
阅读更多...
Java数据结构4-链表

Java数据结构4-链表

1. ArrayList的缺陷 由于其底层是一段连续空间，当在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n)，效率比较低，因此ArrayList不适合做任意位置插入和删除比较多的场景。因此：java集合中又引入了LinkedList，即链表结构。 2. 链表 2.1 链表的概念及结构 链表是一种物理存储结构上非连续存储结构，数据元素
阅读更多...
大学生自救数据结构与算法（py实现）——01递归

大学生自救数据结构与算法（py实现）——01递归

目录 目录 递归 基本概念 工作原理 基本要素 优点 缺点 实现技巧 实例解析：计算阶乘 斐波那契数列 高效的斐波那契数列 python中的最大递归深度 二分查找 基本原理 性能分析 优化与变体 线性递归  元素序列的递归求和 二路递归 二路递归的基本概念 典型应用 工作原理 多重递归  示例：计算卡特兰数（Catalan Number） 尾递
阅读更多...
数据结构和算法(1) ---- Queue 的原理和实现

数据结构和算法(1) ---- Queue 的原理和实现

Queue 的定义和结构 队列(Queue) 是只允许在一端进行插入，在另一端进行删除的线性表 队列是一种先进先出(First In First Out)的线性表，简称 FIFO(First IN First OUT), 允许插入的一端称为队尾, 允许删除的一端称为队列头 队列的基本结构如下图所示： Queue 的抽象数据类型 队列也有线性表的各种操作,不同的是插入元素只能在队列尾,删除
阅读更多...
从零开始学数据结构系列之第三章《平衡二叉树基础概念》

从零开始学数据结构系列之第三章《平衡二叉树基础概念》

文章目录 前言什么是平衡二叉树往期回顾 前言 ​   在前面的学习过程中，我们了解到二叉排序树可以在一定程度上提高查找（搜索）的效率，但仍然会出现特殊情况，让二叉排序树失效。例如，将序列{1,2,3,4,5,6}中的元素依次插入到二叉排序树中，会得到右斜树，这就相当于一个单链表了，搜索效率降低为O(n)。   于是在 1962 年，一个姓 AV 的大佬（G. M. Ade
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2