树结构及其算法-用数组来实现二叉树

这篇具有很好参考价值的文章主要介绍了树结构及其算法-用数组来实现二叉树。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

树结构及其算法-用数组来实现二叉树

C++代码 


树结构及其算法-用数组来实现二叉树

使用有序的一维数组来表示二叉树,首先可将此二叉树假想成一棵满二叉树,而且第层具有个节点,按序存放在一维数组中。首先来看看使用一维数组建立二叉树的表示方法以及数组索引值的设置。

树结构及其算法-用数组来实现二叉树,算法(Algorithm),c++,开发语言,算法,树结构,数组,二叉树

可以看出此一维数组中的索引值有以下关系:

  1. 左子树的索引值是父节点的索引值乘2。
  2. 右子树的索引值是父节点的索引值乘2加1。

接着来看如何以一维数组建立二叉树的实例,实际上就是建立一棵二叉查找树。这是一种很好的排序应用模式,因为在建立二叉树的同时数据就经过了初步的比较判断,并按照二叉树的建立规则来存放数据。二叉查找树具有以下特点:

  1. 可以是空集合,若不是空集合,则节点上一定要有一个键值。
  2. 每一个数根的值需大于左子树的值。
  3. 每一个树根的值需小于右子树的值。
  4. 左右子树也是二叉查找树。
  5. 树的每个节点值都不相同。 

C++代码 

#include<iostream>
using namespace std;

class Tree {
private:
	int* treeNode;
	int size;
	int level;
public:
	Tree(int size) {
		treeNode = new int[size] {0};
		this->size = size;
		level = 0;
	}
	void SetTree(int* tempData, int tempSize) {
		for (int i = 0; i < tempSize; i++) {
			for (level = 1; treeNode[level] != 0;) {
				if (tempData[i] > treeNode[level])
					level = level * 2 + 1;
				else
					level = level * 2;
			}
			treeNode[level] = tempData[i];
		}
	}
	void PrintTree() {
		for (int i = 1; i < size; i++)
			cout << treeNode[i] << " ";
		cout << endl;
	}
};

int main() {
	int data[]{ 6, 3, 5, 9, 7, 8, 4, 2 };
	cout << "原始数据:" << endl;
	for (int i = 0; i < 8; i++)
		cout << data[i] << " ";
	cout << endl;

	Tree tree(16);
	tree.SetTree(data, 8);
	cout << "二叉树数据:" << endl;
	tree.PrintTree();

	return 0;
}

输出结果

树结构及其算法-用数组来实现二叉树,算法(Algorithm),c++,开发语言,算法,树结构,数组,二叉树文章来源地址https://www.toymoban.com/news/detail-739589.html

到了这里,关于树结构及其算法-用数组来实现二叉树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 模拟实现链式二叉树及其结构学习——【数据结构】

    W...Y的主页 😊 代码仓库分享 💕 之前我们实现了用顺序表完成二叉树(也就是堆),顺序二叉树的实际作用就是解决堆排序以及Topk问题。 今天我们要学习的内容是链式二叉树,并且实现链式二叉树,这篇博客与递归息息相关! 目录 链式存储 二叉树链式结构的实现 链式二叉

    2024年02月07日
    浏览(39)
  • 【数据结构】二叉树链式结构的实现及其常见操作

    目录 1.手搓二叉树 2.二叉树的遍历 2.1前序、中序以及后序遍历 2.2二叉树的层序遍历 3.二叉树的常见操作 3.1求二叉树节点数量 3.2求二叉树叶子节点数量 3.3求二叉树第k层节点个数 3.3求二叉树的深度 3.4二叉树查找值为x的节点 4.二叉树的销毁 在学习二叉树的基本操作前,需先要

    2024年02月12日
    浏览(45)
  • 【数据结构和算法】--- 二叉树(3)--二叉树链式结构的实现(1)

    在学习二叉树的基本操作前,需先要创建一棵二叉树,然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入,且为了方便后面的介绍,此处手动快速创建一棵简单的二叉树,快速进入二叉树操作学习,等二叉树结构了解的差不多时,我们反过头再来研

    2024年01月25日
    浏览(59)
  • 【数据结构和算法15】二叉树的实现

    二叉树是这么一种树状结构:每个节点最多有两个孩子,左孩子和右孩子 重要的二叉树结构 完全二叉树(complete binary tree)是一种二叉树结构,除最后一层以外,每一层都必须填满,填充时要遵从先左后右 平衡二叉树(balance binary tree)是一种二叉树结构,其中每个节点的左

    2024年02月16日
    浏览(34)
  • 树和二叉树(概念及其结构)

    1.1树的概念 树是一种非线性的数据结构,它是由n(n=0)个有限结点组成一个具有层次关系的集合。把它 叫做树是因为它看起来像一颗倒挂的树,也就是说它是根朝上,而叶朝下的。 *有一个特殊的节点叫做根节点,根节点没有前驱节点 *除根节点外,其余节点被分成不相交的

    2023年04月22日
    浏览(30)
  • 【数据结构和算法】---二叉树(2)--堆的实现和应用

    如果有一个数字集合,并把它的所有元素 按完全二叉树的顺序存储方式存储在一个一维数组中 ,且在逻辑结构(即二叉树)中,如果 每个父亲节点都大于它的孩子节点那么此堆可以称为大堆 ;那么如果 每个父亲节点都小于它的孩子节点那么此堆可以称为小堆 。 堆的 性质

    2024年02月03日
    浏览(45)
  • 【数据结构与算法】哈夫曼编码(最优二叉树)实现

    哈夫曼编码 等长编码:占的位置一样 变长编码(不等长编码):经常使用的编码比较短,不常用的比较短 最优:总长度最短 最优的要求:占用空间尽可能短,不占用多余空间,且不能有二义性 这里给出哈夫曼二叉树的实现: HuffmanTree.h: 测试数据(主函数): 运行结果截图

    2024年02月16日
    浏览(46)
  • 【数据结构与算法】哈夫曼编码(最优二叉树实现

    哈夫曼编码 等长编码:占的位置一样 变长编码(不等长编码):经常使用的编码比较短,不常用的比较短 最优:总长度最短 最优的要求:占用空间尽可能短,不占用多余空间,且不能有二义性 这里给出哈夫曼二叉树的实现: HuffmanTree.h: 测试数据(主函数): 运行结果截图

    2024年02月16日
    浏览(44)
  • 数据结构进阶篇 之 【二叉树】详细概念讲解(带你认识何为二叉树及其性质)

    有朋自远方来,必先苦其心志,劳其筋骨,饿其体肤,空乏其身,鞭数十,驱之别院 1.1 二叉树中组分构成名词概念 1.2 二叉树的结构概念 1.3 特殊的二叉树 2.1 顺序存储 2.2 链式存储 前言: 在你的想象中如果有一个“二叉树”会是什么样子呢? 顾名思义,现实中的二叉树我们

    2024年04月13日
    浏览(43)
  • DSt:数据结构的最强学习路线之数据结构知识讲解与刷题平台、刷题集合、问题为导向的十大类刷题算法(数组和字符串、栈和队列、二叉树、堆实现、图、哈希表、排序和搜索、动态规划/回溯法/递归/贪心/分治)总

    Algorithm:【算法进阶之路】之算法面试刷题集合—数据结构知识和算法刷题及其平台、问题为导向的十大类刷题算法(数组和字符串、链表、栈和队列、二叉树、堆、图、哈希表、排序和搜索、回溯算法、枚举/递归/分治/动态规划/贪心算法)总结 目录 相关文章

    2024年02月08日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包