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

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。

相关文章

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...
【408数据结构】散列 （哈希）知识点集合复习考点题目

【408数据结构】散列 （哈希）知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独，于是我记下了些许笔记相伴，希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法，它通过散列函数将关键字映射到数组的一个位置，从而实现快速查找。这种方法的时间复杂度平均为(
阅读更多...
浙大数据结构：树的定义与操作

浙大数据结构：树的定义与操作

四种遍历 #include<iostream>#include<queue>using namespace std;typedef struct treenode *BinTree;typedef BinTree position;typedef int ElementType;struct treenode{ElementType data;BinTree left;BinTre
阅读更多...
Python 内置的一些数据结构

Python 内置的一些数据结构

文章目录 1. 列表 (List)2. 元组 (Tuple)3. 字典 (Dictionary)4. 集合 (Set)5. 字符串 (String) Python 提供了几种内置的数据结构来存储和操作数据，每种都有其独特的特点和用途。下面是一些常用的数据结构及其简要说明： 1. 列表 (List) 列表是一种可变的有序集合，可以存放任意类型的数据。列表中的元素可以通过索
阅读更多...
浙大数据结构：04-树7 二叉搜索树的操作集

浙大数据结构：04-树7 二叉搜索树的操作集

这道题答案都在PPT上，所以先学会再写的话并不难。 1、BinTree Insert( BinTree BST, ElementType X ) 递归实现，小就进左子树，大就进右子树。 为空就新建结点插入。 BinTree Insert( BinTree BST, ElementType X ){if(!BST){BST=(BinTree)malloc(sizeof(struct TNo
阅读更多...
【数据结构入门】排序算法之交换排序与归并排序

【数据结构入门】排序算法之交换排序与归并排序

前言         在前一篇博客，我们学习了排序算法中的插入排序和选择排序，接下来我们将继续探索交换排序与归并排序，这两个排序都是重头戏，让我们接着往下看。  一、交换排序 1.1 冒泡排序 冒泡排序是一种简单的排序算法。 1.1.1 基本思想 它的基本思想是通过相邻元素的比较和交换，让较大的元素逐渐向右移动，从而将最大的元素移动到最右边。 动画演示： 1.1.2 具体步
阅读更多...
数据结构：线性表的顺序存储

数据结构：线性表的顺序存储

文章目录 🍊自我介绍🍊线性表的顺序存储介绍概述例子 🍊顺序表的存储类型设计设计思路类型设计 你的点赞评论就是对博主最大的鼓励 当然喜欢的小伙伴可以：点赞+关注+评论+收藏（一键四连）哦~ 🍊自我介绍   Hello,大家好，我是小珑也要变强（也是小珑），我是易编程·终身成长社群的一名“创始团队·嘉宾” 和“内容共创官” ,现在我来为大家介绍一下有关物联网-嵌入
阅读更多...
[数据结构]队列之顺序队列的类模板实现

[数据结构]队列之顺序队列的类模板实现

队列是一种限定存取位置的线性表，允许插入的一端叫做队尾（rear），允许删除的一端叫做队首（front）。 队列具有FIFO的性质 队列的存储表示也有两种方式：基于数组的，基于列表的。基于数组的叫做顺序队列，基于列表的叫做链式队列。 一下是基于动态数组的顺序队列的模板类的实现。 顺序队列的抽象基类如下所示：只提供了接口和显式的默认构造函数和析构函数，在派生类中调用。 #i
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2