菜缤的世界 CairBin's Blog - 二叉树
type: channel
link: https://blog.cairbin.top/index.php/tag/二叉树/
items: 哈夫曼树及哈夫曼编码（基于优先队列实现）
items: 二叉搜索树BST
items: 数据结构——堆
items: 二叉树及其遍历
items: 二叉树

哈夫曼树及哈夫曼编码（基于优先队列实现）
type: item
date: 2022-10-24T17:53:00+00:00
description: 哈夫曼树及哈夫曼编码（基于优先队列实现）概念基础路径：从树中一个结点到另一个结点之间的分支路径长度：路径上的分支数目称为路径长度树的路径长度：从树根到每一结点的路径长度之和结点的带权路径长度：从该结点到树根之间的路径长度与结点上的权值的乘积树的带权路径长度WPL：树中所有叶子节点的带权路径长度之和哈夫曼树概念由树的带权路径长度(WPL)定义可得到公式如下，其中$w_i$为叶子结点权值，$l_i$为叶子结点路径长度$$ WPL(n) = \sum_{i=1}^{n} w_il_i $$设有如下n个权值$$ \{w_1,w_2,...,w_n\} $$构造一棵有n个叶子节点的二叉树，每个叶子的权值为$w_i$其中，WPL最小的二叉树就被称作哈夫曼树，也叫最优二叉树也就是说哈夫曼树的WPL满足如下条件$$ WPL_{Haffman} = WPL_{min}(n) $$由此概念不难理解，哈夫曼树的形态不是唯一的，但是具有一组权值的各哈夫曼树的WPL是唯一的从根节点出发，连接左儿子的边记为0，连接右儿子的边记为1，一直到叶子节点，所经过的边的编号构成的二进制序列即为该叶子结点的哈夫曼编码哈夫曼编码的优点在于，对于每个叶子节点（对应唯一的字母或其他数据）的编码是唯一的，且任意一个编码不会是另外一个编码的前缀，这确保了解码的唯一性。另外还有一些性质：对于具有$n_0$个叶子结点的哈夫曼树，其结点数如下$$ node = 2n_0-1 $$构建哈夫曼树与获取哈夫曼编码假设有这样四个字母与它们权值构成的序偶组成的集合如下$$ \{(A,2),(B,5),(C,4),(D,9)\} $$利用该数据构建哈夫曼树首先将上述数据看成只有一个结点的二叉树取出两个根节点权值最小的二叉树$$ \{2，4\} $$将两者（左子树根结点权值小于等于右子树根节点）连接到同一个父节点上，则其父节点的权值为6加上刚才诞生的新的树，还没有被利用的树的根节点对应的权值有$$ \{5,6,9\} $$同样再选出两个最小的（如果这时候，新构造的根节点与原有的根节点权值相等，则原有的根节点对应的树作为左子树，新构造的根节点对应的树作为右子树），重复上述步骤即可得到下图这时候只剩下两棵树没被使用，其根节点对应的权值如下$$ \{9,11\} $$同样再次执行上述步骤即可将所有树利用，即得到一个完整的哈夫曼树将连接左儿子的边记为0，连接右儿子的边记为1即可得到各个字母的哈夫曼编码（我一般习惯将编码序列从右往左写，例如A的为011,，如果从左往右写就要写成110，本文包括下文中的代码演示均使用从右向左的方法）$$ A:011,B:01,C:111,D:0 $$如果一串字符串BDA则对应的哈夫曼编码如下（字符串顺序从左往右读，编码从右向左读取来解码）$$ 0\space10\space011 $$代码演示类定义首先定义一个哈夫曼树的类typedef vector<pair<int, char>> huff; class Huffman { private: //结点定义 class node { public: char word; int weight; //权值 node *lc, *rc; //左儿子结点，右儿子结点 string code; node(int weight, char word) { lc = nullptr; rc = nullptr; code = ""; this->word = word; this->weight = weight; } }; private: priority_queue<pair<int, node*>, vector<pair<int, node*>>, greater<pair<int, node*>>> que; //存放结点指针的优先队列（小根堆） node* root; //根结点 unordered_map<char, string> un_map; public: Huffman(vector<pair<int, char>> vec); string Find(char index); private: void _CreateCode(node *n, stack<string> st, int flag); };方法构造函数Huffman::Huffman(vector<pair<int,char>> vec) { //将外部数据转成结点，存放到优先队列 for (auto it = vec.begin(); it != vec.end(); it++) { node* p = new node(it->first, it->second); this->que.push(make_pair(it->first,…

二叉搜索树BST
type: item
date: 2022-10-21T08:13:00+00:00
description: 二叉搜索树BST原因最近想了解下C++ STL中的map和set的原理，它们是由红黑树实现的，但是想要了解红黑树要先了解下最基本的二叉搜索树概念二叉搜索树(Binary Search Tree)是有如下特征：每个元素有唯一的键，这些键能比较大小任何一个结点，它的左子树上任意结点的键都比它小，它的右子树上任意结点的键都比它大（由此可以推出，键值最大的结点无右儿子，键值最小的结点无左儿子）另外，如果对这棵二叉树进行中序遍历，键的排列会是严格递增的代码定义BST的C++类定义如下：class BST{ private: class node{ public: int key; int value; node* lc; //左儿子 node* rc; //右儿子 }; private: node* root; //对外接口 public: BST(); void Insert(int key, int value); bool Find(int key, int &value); bool Delete(int key); void MidOrder(); //内部接口及功能实现 private: void _Insert(node* &n, int key, int value); bool _Find(node* n, int key, int &value); node* _Delete(node* &n, int key, bool &flag); void _MidOrder(node* n); };它的结点包含一对键值对，此处为了方便全用整型变量表示（当然可以写成泛型的形式，但是应当注意键的类型需能比较大小或重载了该运算符）另外，由于BST也是一种二叉树，所以结点也满足二叉树的结点定义，即包含左儿子指针和右儿子指针操作BST的操作有插入、查询、删除、遍历（建树的过程在插入中实现），这些方法基本都是递归实现的。在上文的类定义中，由于node类为私有，并且方法的实现为递归，为了安全与简洁，对外部的方法作为接口会调用对应的私有方法，因此下文的每种操作都会列举出一个接口和方法实现，使用只需要调用规范好的接口就行了。构造函数BST::BST(){ //初始化 this->root = nullptr; }插入以第1个数据为根结点，逐个插入所有数据。插入时分三种情况：当传入指针即当前结点为空，则new直接插入（new一个结点，并赋值）若插入数据键比当前结点的键小，则向左子树递归继续寻找插入位置若插入数据键比当前结点的键大，则向右子树递归继续寻找插入位置其代码如下：//插入方法实现 void BST::_Insert(node* &n, int key, int value){ //为空直接插入 if(!n) { n = new node; n->key = key; n->value = value; n->lc = nullptr; n->rc = nullptr; return; } //不为空需要找查 if(n->key == key) //如果等于当前键，则直接修改该结点的值 n->value = value; else if(n->key > key) //当前结点的键大于所要插入的键，则往左子树找插入点 this->_Insert(n->lc, key, value); else //当前结点的键大于所要插入结点的键，则往右子树找插入点 this->_Insert(n->rc, key, value); } //插入方法接口 //参数：键，值 void BST::Insert(int key, int value) { this->_Insert(this->root, key, value); } 查询该操作原理与插入类似，都是需要比较键的大小往判断往左子树找还是右子树找//查找方法实现 //成功返回true，并将value改为键对应的值；否则返回false，value不做处理 bool BST::_Find(node* n, int key, int &value) { //检查是否为空 if(!n) return false; if(n->key == key) //找到 { value = n->value; return true; } else if(n->key > key) //未找到，且当前键大于查询键，继续往左找 return this->_Find(n->lc, key, value); else //未找到，且当前键小于查询键，继续往右找 return this->_Find(n->rc, key, value); } //查找方法的接口 bool BST::Find(int key, int &v…

数据结构——堆
type: item
date: 2022-04-09T07:41:00+00:00
description: 堆堆的概念堆（heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象，即是一种顺序储存结构的完全二叉树。1提示：完全二叉树完全二叉树：对一棵深度为k、有n个结点二叉树编号后，各节点的编号与深度为k的满二叉树相同位置的结点的编号相同，这颗二叉树就被称为完全二叉树。2堆的性质堆中某个结点的值总是不大于或不小于其父结点的值堆总是一棵完全二叉树除了根结点和最后一个左子结点可以没有兄弟结点，其他结点必须有兄弟结点最大堆最小堆最大堆3：根结点的键值是所有堆结点键值中最大者，且每个结点的值都比其孩子的值大。最小堆3：根结点的键值是所有堆结点键值中最小者，且每个结点的值都比其孩子的值小。代码定义有限数组形式int Heap[1024]; //顺序结构的二叉树若某结点编号为i，且存在左儿子和右儿子，则他们分别对应Heap[i*2+1]; //左儿子 Heap[i*2+2]; //右儿子其父节点Heap[i/2]; //i的父节点动态数组形式在项目开发中，经常以动态数组形式出现，在本文主要对这种形式进行介绍//默认容量 #define DEFAULT_CAPCITY 128 typedef struct _Heap { int *arr; //储存元素的动态数组 int size; //元素个数 int capacity; //当前存储的容量 }Heap;操作只使用InitHeap()函数进行初始化即可，AdjustDown()与BuildHeap()仅为堆建立时的内部调用向下调整结点以创建最大堆为例将“判断最大子结点是否大于当前父结点”处的>=改为<=即可创建最小堆//向下调整，将当前结点与其子结点调整为最大堆 //用static修饰禁止外部调用 static void AdjustDown(Heap& heap, int index) { int cur = heap.arr[index]; //当前待调整结点 int parent, child; /* 判断是否存在子结点大于当前结点。 若不存在，堆是平衡的，则不调整； 若存在，则与最大子结点与之交换，交换后该子节点若还有子结点，则以此方法继续调整。 */ for (parent = index; (parent * 2 + 1) < heap.size; parent = child) { child = parent * 2 + 1; //左子结点 //取两个子结点中最大节点,(child+1)<heap.size防止越界 if (((child + 1) < heap.size && (heap.arr[child] < heap.arr[child + 1]))) child++; //判断最大子结点是否大于当前父结点 if (cur >= heap.arr[child]) //将此处的>=改成<=可构建最小堆 { //不大于，不需要调整 break; } else { //大于，则交换 heap.arr[parent] = heap.arr[child]; heap.arr[child] = cur; } } }建立堆//建立堆，用static修饰禁止外部调用 static void BuildHeap(Heap& heap) { int i; //从倒数第二层开始调整（若只有一层则从该层开始） for (i = heap.size / 2 - 1; i >= 0; i--) { AdjustDown(heap, i); } }初始化//初始化堆 //参数：被初始化的堆，存放初始数据的数组， 数组大小 bool InitHeap(Heap &heap, int *orginal, int size) { //若容量大于size，则使用默认量，否则为size int capacity = DEFAULT_CAPCITY>size?DEFAULT_CAPCITY:size; heap.arr = new int[capacity]; //分配内存，类型根据实际需要可修改 if(!heap.arr) return false; //内存分配失败则返回False heap.capacity = capacity; //容量 heap.size = 0; //元素个数置为0 //若存在原始数组则构建堆 if(size>0) { /* 内存拷贝，将orginal的元素拷贝到堆数组arr中 size*sizeof(int)为元素所占内存空间大小 */ memcpy(heap.arr,orginal, size*sizeof(int)); heap.size = size; //调整大小 BuildHeap(heap); //建堆 } return true; }…

二叉树及其遍历
type: item
date: 2022-03-06T16:12:00+00:00
description: 二叉树及其遍历二叉树概念定义什么是二叉树二叉树特点是每个节点最多只能有两棵子树，且有左右之分的树。注：关于数据结构——树的一些基本概念可以参考《树的概念及基本术语》 - CairBin's Blog二叉树的基本性质关于二叉树的基本性质前面已经写的很详细了，可以回顾文章《二叉树》 - CairBin's Blog二叉树结构体定义结构体定义及其构造函数//链式二叉树结构体定义 typedef struct _BinTree { int data; //存放数据 struct _BinTree* lc; //左儿子 struct _BinTree* rc; //右儿子 //构造函数 _BinTree(int d, struct _BinTree* l = NULL, struct _BinTree* r = NULL) :data(d), lc(l), rc(r) {}; }Node;析构函数//析构函数 void destroyBinTree(Node* node) { //如果不存在该节点说明已经到该路径底部,则返回 if (node == NULL) return; //如果没到达该路径尽头则删除路上节点并继续向下走 //保存指向子节点的指针 Node* pl = node->lc; Node* pr = node->rc; delete node; //删除当前节点 node = NULL; //指针置为空，防止野指针 //递归,向下走 destroyBinTree(pl); destroyBinTree(pr); }创建二叉树并写入数据//创建二叉树结构并写入数据 //代码参考https://blog.csdn.net/u013575812/article/details/50129435 void buildBinTree(Node** node) { int data; cin >> data; if (data == -1) *node = NULL; else { *node = (Node*)malloc(sizeof(Node)); (*node)->data = data; buildBinTree(&(*node)->lc); buildBinTree(&(*node)->rc); } }二叉树的遍历宽度优先遍历（BFS）层序遍历图解分析二叉树宽度优先遍历就是要一层一层去遍历，故对于二叉树又叫层序遍历。以上图举例，BFS遍历顺序为EBCADFICH注：我们用队列实现搜索过程，关于队列的知识可以看文章《队列》 - CairBin's Blog此处为了方便，就不手动写队列(queue)了，直接使用C++ STL模板里的Queue代码下面给出代码：//BFS、层序遍历 void levelOrder(Node* node, queue<Node*>& que) { if (!node) return; Node* p = node; que.push(p); while (!que.empty()) { p = que.front(); //p设为队列头部元素 que.pop(); //队列尾部元素出队 cout << p->data << endl; if (p->lc) que.push(p->lc); if (p->rc) que.push(p->rc); } }深度优先遍历(DFS)按深度搜索的顺序访问二叉树，对根（父）节点、左儿子、右儿子进行组合，有三种访问顺序先序遍历中序遍历后序遍历这些遍历组合有如下性质中序+先序——可确定该树中序+后序——可确定该树先序+后续，且不知道中序——不可确定该树这些遍历又分别有两种方法：递归方法非递归方法对于非递归方法需要用到数据结构——栈（stack），关于栈的知识可以参考文章《栈的概念及性质》 - CairBin's Blog《顺序栈的操作》 - CairBin's Blog《链栈的操作》 - CairBin's Blog这里同样用STL模板里的Stack先序遍历图解分析我们依旧用该图先序遍历顺序：父节点、左儿子、右儿子本图访问顺序为：EBADCGFIH代码递归方法//先序遍历，递归 void preOrder_A(Node* node) { if (node == NULL) return; cout << node->data << endl; preOrder_A(node->lc); preOrder_A(node->rc); }非递归方法//先序遍历，非递归 void preOrder_B(Node* node, stack<Node*> &st) { if (!node) return; Node* p = node; while (p || !st.em…

二叉树
type: item
date: 2021-11-21T05:45:00+00:00
description: 二叉树二叉树的定义二叉树在一般的树上加了两个限制条件：每个结点最多只有两个子树子树有左右之分，不能颠倒二叉树的形态空二叉树只有根结点只有左子树，右子树为空只有右子树，左子树为空既有左子树，又有右子树满二叉树、完全二叉树以及非完全二叉树满二叉树：所有的分支结点都有左、右子节点，并且所有叶子结点都集中在最下层的二叉树。完全二叉树：对一棵深度为k、有n个结点二叉树编号后，各节点的编号与深度为k的满二叉树相同位置的结点的编号相同，这颗二叉树就被称为完全二叉树非完全二叉树：没有满足完全二叉树中的条件的二叉树二叉树的主要性质非空二叉树上叶子结点数等于双分支结点（有两个分支的结点）数加1总结点数 = 叶子结点数 + 单分支结点数 + 双分支结点数 = 单分支结点数 + 2*双分支结点数总分支数 = 总结点数 - 1 （此性质对所有树都成立，并非只是二叉树）空指针数 = 所有结点数 + 1二叉树第i层最多有 2^(i-1) 个结点，其中i>=1深度为k的二叉树最多有 2^k - 1 个结点有n个结点的完全二叉树，对各结点从上到下、从左到右编号。若i为某结点a的编号（范围1~n）。若i不等于1，则a父结点的编号为不超过(i/2)的最大整数若2i<=n ,则a左儿子的编号为 2i ; 若 2i>n ，则a无左儿子若2i+1<=n ,则a的右儿子编号为 2i+1 ;若 2i+1>n ，则a 无右儿子给定n个结点，能构成二叉树种树如下具有n个结点的二叉树深度如下二叉树的储存结构顺序储存结构顺序储存结构用一个数组来存放一棵二叉树，这种方式最适合完全二叉树定义如下int Tree[1024]; //顺序结构的二叉树若某结点编号为i，且存在左儿子和右儿子，则他们分别对应Tree[i*2]; //左儿子 Tree[2*i+1]; //右儿子链式储存结构定义如下typedef struct _BtTree{ int data; struct _BtTree *leftchild; struct _BtTree *rightchild; }BtTree;