哈夫曼树及哈夫曼编码（基于优先队列实现）
哈夫曼树及哈夫曼编码（基于优先队列实现）概念基础路径：从树中一个结点到另一个结点之间的分支路径长度：路径上的分支数目称为路径长度树的路径长度：从树根到每一结点的路径长度之和结点的带权路径长度：从该结点到树根之间的路径长度与结点上的权值的乘积树的带权路径长度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,p)); } //构造哈夫曼树 int cnt = 0; //计数，每弹出两个结点连接到一个父节点，cnt置为0 pair<int,node*> temp[2]; while (!que.empty()) { if (cnt >= 2) { node* p = new node(temp[0].first + temp[1].first, ' '); p->lc = temp[0].second; p->rc = temp[1].second; que.push(make_pair(temp[0].first + temp[1].first, p)); cnt = 0; this->root = p; //不断设置根节点 continue; } temp[cnt] = que.top(); que.pop(); cnt++; } //最后会剩余两个结点于temp中，把它们连接起来 node* p = new node(temp[0].first + temp[1].first, ' '); p->lc = temp[0].second; p->rc = temp[1].second; this->root = p; //建立叶子节点编码，左分支为0，右分支为1 stack<string> st; _CreateCode(this->root, st, 0); }编码映射将字母对应的哈夫曼编码保存到叶子节点中去，并且创建一个映射关系到map中void Huffman::_CreateCode(node *n,stack<string> st, int flag) { if (!n) return; flag == -1 ? st.push("0") : (flag == 0 ? st.push("") : st.push("1")); if (n->lc == nullptr && n->rc == nullptr) { while (!st.empty()) { n->code += st.top(); st.pop(); } un_map[n->word] = n->code; return; } this->_CreateCode(n->lc, st, -1); this->_CreateCode(n->rc, st, 1); } 查询查询的话只需要返回unordered_map<char, string> un_map;相关的键对应的值就行了string Huffman::Find(char index) { return this->un_map[index]; }结束此处代码不足之处是还有解码没有实现。但是我觉得用每个字符的哈夫曼编码作为子串去匹配主串实现解码就行了，这应该是个字符串算法相关的问题，所以这里我就没写。
二叉搜索树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 &value) { return this->_Find(this->root, key, value); }删除结点删除结点的操作比较麻烦。首先根据键找到被删除结点，进行删除后改树应仍满足BST的定义，这就需要进行分类讨论：当要被删除的结点为叶子结点，直接将其对应的父结点的指针置为空，并删除该结点当要被删除的结点仅有左子树或右子树时，其对应父结点的指针应指向子树的根结点，再进行删除。当要被删除的结点既有左子树，又有右子树，这种情况比较麻烦。一种删除方法是将右子树的最小键结点的键与值替换当前结点，然后删除右子树的最小键结点代码如下（比较抽象）：//删除方法的实现 BST::node* BST::_Delete(node* &n, int key, bool &flag) { if(!n) return n; if(n->key>key) //往左找 n->lc = this->_Delete(n->lc, key, flag); if(n->key<key) //往右找 n->rc = this->_Delete(n->rc, key, flag); else{ //找到 flag = true; //设置flag，表示删除成功 //如果仅有左子树或右子树或为叶子结点 if(!(n->rc)) //无右子树或为叶子结点 return n->lc; if(!(n->lc)) //无左子树 return n->rc; //寻找右子树最小键结点的键与值拷贝至当前结点 node* p = n->rc; while(p->lc) p = p->lc; n->value = p->value; n->key = p->key; bool temp = false; n->rc = this->_Delete(n->rc, p->key, temp); //将右子树最小键结点的父结点左指针置为空 delete p; //删除原右子树最小键结点 } return n; } //删除方法的接口 bool BST::Delete(int key) { bool flag = false; this->_Delete(this->root, key, flag); return flag; }遍历遍历方法无非就是二叉树的那几种，但是正如前面提到的，对BST进行中序遍历的时候，其键的排序是严格递增的，这也正是采用该数据结构的一种重要原因，所以此处仅给出了中序遍历的递归定义注：其他遍历可参考之前文章 二叉树及其遍历-CairBin//中序遍历方法实现 void BST::_MidOrder(node* n) { if(!n) return; this->_MidOrder(n->lc); cout << n->key << ":" << n->value << " "; this->_MidOrder(n->rc); } //中序遍历接口 void BST::MidOrder() { this->_MidOrder(this->root); cout << endl; }缺点与改进BST的插入是按给定序列的顺序进行的，最后建成的树是唯一的。也就是说它可能很好，也可能很坏。最坏的情况：如序列{1,2,3,4,5,6,7}，为方便排序令其键与值相等，然后就会发现该BST会退化成一个每个结点都有右子树，无左子树（叶子结点都没有）的链表，导致访问一个结点的复杂度为$O(n)$最好的情况：如序列{4,2,1,3,6,5,7}，同样令键与值相等，其为一个三层的满二叉树，访问结点的复杂度为$O(log_{2}{n})$从上述情况看，BST优劣取决于是否为一个平衡的二叉树，所以有一系列相关的算法进行改进。BST算法有：红黑树、AVL、Splay等参考《算法竞赛入门到进阶》——清华大学出版社
堆堆的概念堆（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; }打印堆实际上是一个层序遍历4//以树状的形式打印堆 void PrintHeapAsTreeStyle(Heap hp) { queue<int> que; int r = 0; que.push(r); queue<int> temp; while (!que.empty()) { r = que.front(); que.pop(); if (r * 2 + 1 < hp.size) temp.push(r * 2 + 1); if (r * 2 + 2 < hp.size) temp.push(r * 2 + 2); if (que.empty()) { cout << hp.arr[r] << endl; que = temp; temp = queue<int>(); } else cout << hp.arr[r] << " "; } }测试main函数int main() { Heap hp; int vals[] = { 1,2,3,87,93,82,92,86,95 }; if (!InitHeap(hp, vals, sizeof(vals) / sizeof(vals[0]))) { fprintf(stderr, "初始化堆失败！\n"); exit(-1); } PrintHeapAsTreeStyle(hp); return 0; }结果95 93 92 87 1 82 3 86 2完整代码#include <iostream> #include <queue> using namespace std; //默认容量 #define DEFAULT_CAPCITY 128 typedef struct _Heap { int* arr; int size; int capacity; }Heap; //向下调整，将当前结点与其子结点调整为最大堆 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; } //以树状的形式打印堆 void PrintHeapAsTreeStyle(Heap hp) { queue<int> que; int r = 0; que.push(r); queue<int> temp; while (!que.empty()) { r = que.front(); que.pop(); if (r * 2 + 1 < hp.size) temp.push(r * 2 + 1); if (r * 2 + 2 < hp.size) temp.push(r * 2 + 2); if (que.empty()) { cout << hp.arr[r] << endl; que = temp; temp = queue<int>(); } else cout << hp.arr[r] << " "; } } int main() { Heap hp; int vals[] = { 1,2,3,87,93,82,92,86,95 }; if (!InitHeap(hp, vals, sizeof(vals) / sizeof(vals[0]))) { fprintf(stderr, "初始化堆失败！\n"); exit(-1); } PrintHeapAsTreeStyle(hp); return 0; }参考堆（数据结构）_百度百科 ↩二叉树 - 菜缤的世界 CairBin's Blog ↩最大堆和最小堆_varyall的博客-CSDN博客 ↩二叉树及其遍历 - 菜缤的世界 CairBin's Blog ↩
二叉树及其遍历二叉树概念定义什么是二叉树二叉树特点是每个节点最多只能有两棵子树，且有左右之分的树。注：关于数据结构——树的一些基本概念可以参考《树的概念及基本术语》 - 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.empty()) { //从根节点一直往左入栈 while (p) { st.push(p); cout << p->data << endl; p = p->lc; } //访问栈，从左节点获得右边节点数据 if (!st.empty()) { p = st.top(); st.pop(); p = p->rc; } } }中序遍历图解分析中序遍历顺序：左儿子、父节点、右儿子本图遍历顺序：ABCDEFG上述顺序正好为字典顺序，这并不是巧合，这是因为此图是个二叉搜索树，在进行中序遍历时实现了排序功能中序遍历特征：已知根节点，从中序遍历结果来看，排在根节点左边的都在左子树上，排在根节点右边的都在右子树上。例如E是根节点，ABCD都在左子树代码递归方法//中序遍历，递归 void inOrder_A(Node* node) { if (!node) return; inOrder_A(node->lc); cout << node->data << endl; inOrder_A(node->rc); }非递归方法//中序遍历，非递归 void inOrder_B(Node* node, stack<Node*>& st) { if (!node) return; Node* p = node; while (p || !st.empty()) { //左边一直入栈 while (p) { st.push(p); p = p->lc; } //从最左下儿子开始向右访问 if (!st.empty()) { p = st.top(); cout << p->data << endl; st.pop(); p = p->rc; } } }后序遍历图解分析后序遍历顺序： 左儿子、右儿子、父节点图中顺序：ACDBFHIGE后续遍历最后一个节点是根节点代码递归方法//后序遍历，递归 void postOrder_A(Node* node) { if (!node) return; postOrder_A(node->lc); postOrder_A(node->rc); cout << node->data << endl; }非递归方法//后序遍历，非递归 void postOrder_B(Node* node) { if (!node) return; stack<Node*> s; // 保证前序遍历 stack<Node*> t; // 反向输出左右根 Node* p = node; while (p || !s.empty()) { while (p) { s.push(p); t.push(p); p = p->lc; } if (!s.empty()) { p = s.top(); s.pop(); p = p->lc; } } while (!t.empty()) { cout << t.top()->data << endl; t.pop(); } }本文参考从上往下打印二叉树BFS(C++)_柠檬不加糖的博客-CSDN博客二叉树DFS/BFS实现（C++）_usstmiracle的博客-CSDN博客二叉树遍历总结：DFS+BFS【C++】 - Ueeei - 博客园 (cnblogs.com)C++基础]队列中的常用函数 - Horstxu - 博客园 (cnblogs.com)二叉树_百度百科 (baidu.com)《算法竞赛入门到进阶》—— 清华大学出版社
二叉树二叉树的定义二叉树在一般的树上加了两个限制条件：每个结点最多只有两个子树子树有左右之分，不能颠倒二叉树的形态空二叉树只有根结点只有左子树，右子树为空只有右子树，左子树为空既有左子树，又有右子树满二叉树、完全二叉树以及非完全二叉树满二叉树：所有的分支结点都有左、右子节点，并且所有叶子结点都集中在最下层的二叉树。完全二叉树：对一棵深度为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;