数据结构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...
