数据结构13-平衡二叉树
数据结构13-平衡二叉树平衡二叉树(Balanced Binary Tree),也称为AVL树(以发明者 Adelson-Velsky 和 Landis 命名),是一种高度平衡的二叉搜索树(BST)。它的核心目标是保证任意节点的左右子树高度差不超过 1,从而在最坏情况下仍能提供对数时间复杂度的查找、插入和删除操作。 以下是平衡二叉树的详细知识点: 折半查找的二叉判定树就是AVL树 1. 基本定义平衡二叉树是满足以下条件的二叉搜索树: 二叉搜索树性质:左子树所有节点的值小于根节点,右子树所有节点的值大于根节点。 平衡条件:任意节点的左右子树高度差(平衡因子,BF)绝对值不超过 1。 BF=Height(Left Subtree)−Height(Right Subtree)BF = \text{Height(Left Subtree)} - \text{Height(Right Subtree)}BF=Height(Left Subtree)−Height(Right Subtree) 2. 平衡因子 平衡因子可以是 -1, 0,...
数据结构14-哈夫曼树
数据结构14-哈夫曼树哈夫曼树(Huffman Tree)是由计算机科学家David A. Huffman于1952年提出的一种用于数据压缩的二叉树,它能有效地减少存储数据所需的空间。哈夫曼树广泛应用于无损数据压缩算法,如ZIP压缩、PNG图像格式、MP3音频格式等。哈夫曼编码是一种基于字符频率的变长编码,频率高的字符用较短的编码,频率低的字符用较长的编码,从而达到数据压缩的效果。 哈夫曼树的基本原理哈夫曼树的基本思想是:根据输入数据中字符的频率,构建一棵最优的二叉树,树中的每个叶子节点代表一个字符,每个字符的编码通过从根节点到叶子节点的路径来表示。路径中的左子树表示0,右子树表示1。在哈夫曼树中,频率较高的字符会有较短的编码,频率较低的字符会有较长的编码。 哈夫曼树的构建步骤构建哈夫曼树的过程一般分为以下几个步骤: 1. 统计字符频率首先需要统计输入数据中每个字符出现的频率。频率高的字符会优先获得较短的编码。 2. 创建哈夫曼树节点将每个字符及其频率作为一个单独的节点,将所有节点加入到一个优先队列(最小堆)中。队列中的节点会根据字符的频率进行排序,频率小的节点排在前面。 3....
数据结构12-二叉排序树
数据结构12-二叉排序树1
数据结构基础11-线索二叉树的三种写法
数据结构基础11-线索二叉树的三种写法 一.中序线索二叉树1.代码如下:12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576#include<stdio.h>#include<stdlib.h>#include<iostream>using namespace std;typedef struct BiThrNode { char data;// 数据 struct BiThrNode* leftchild;// 左指针 struct BiThrNode* rightchild;// 右指针 int LTag; // 左标志 int RTag; // 右标志}BiThrNode, * BiThrTree;// 全局定义一个线索化二叉树的一个全局变量BiThrNode* pre =...
数据结构基础10-二叉树的创建与三种遍历
数据结构基础10-二叉树的创建与三种遍历-C/C++实现 前序遍历:根左右 中序遍历:左根右 后序遍历:左右根 一.二叉树的递归遍历1.代码如下123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869#include<stdio.h>#include<stdlib.h>#include<iostream>using namespace std;typedef struct Tree { char data;// 数据 struct Tree* leftchild;// 左子树 struct Tree* rightchild;// 右子树}tree, * treelist;// 二叉树的创建void createTree(treelist& app) { char ch; cin >>...
动态爱心♥
...
数据结构-实验二
数据结构-实验二二叉树的操作与实现1、二叉树的基本操作算法实现 (1) 利用(广义表)二叉树字符串“A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))”创建二叉树 的二叉链式存储结构;(请勿根据扩展二叉树进行创建) (2) 输出该二叉树(中序遍历序列); (3) 输出‘H’结点的左、右孩子结点值; (4)...
水墨画网页
...
数据结构-实验一
数据结构-实验一线性表、堆栈和队列的操作与实现1、线性表的链表实现 (1) 用随机函数生成10个3位整数(100~999),把这些整数存于链表中; 要求每次运行生成的10个数据都不相同 (2) 输出链表的内容; (3) 读入一个整数,查看该整数是否在表中,若在,输出其位置(首位置为1); (4) 读入一个整数,以及要插入的位置,把该整数插入到链表中,输出链表的内容, 要求判断输入的位置是否合理; (5) 读入一个整数,若该整数在链表里,删除该整数,输出链表的内容; (6) 把链表的内容翻转,输出链表的内容,要求不占用新的存储空间。考核重点 其他表达方式:将链表中所有结点的链接方向“原地”逆转,即要求仅利用原表中 的存储空间。 (7) 将两个非递减的有序链表合并成一个非递增的有序链表,要求结果链表仍使用...
数据结构queue实现BFS
手撕数据结构队列,以实现BFS算法,不使用原有的queue 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161#include <iostream>#include <stdio.h>#include <stdlib.h>using namespace...