189 8069 5689
免责声明：
主要从事网页设计、PC网站建设（电脑版网站建设）、wap网站建设（手机版网站建设）、响应式网站、程序开发、微网站、小程序定制开发等，凭借多年来在互联网的打拼，我们在互联网网站建设行业积累了丰富的网站设计、成都网站设计、网络营销经验，集策划、开发、设计、营销、管理等多方位专业化运作于一体，具备承接不同规模与类型的建设项目的能力。
- 笔记来源：本系列所有笔记均整理自 B站·王道考研·数据结构 视频教程。
- 参考书籍：《2021年数据结构考研复习指导》，王道论坛所著，电子工业出版社出版，ISBN ：9787121379819。
目录
1 树 1.1 树的概念树，由 n （n >= 0）个结点组成的有限集。
（m^h - 1）/ (m - 1)个结点，最少有h个结点h + m - 1个结点
二叉树是一种每个结点最多只有两棵子树的树，子树分别叫做左子树和右子树，其顺序不能交换。即便树中只有一颗子树，也要区分是左子树还是右子树。因此，二叉树中不存在度大于2的结点。
性质1
性质2
性质3
完全二叉树的性质
对于一棵完全二叉树，采用顺序存储结构如下：
对于普通的二叉树，为了让数组下标能够反应出结点间的逻辑关系，只能添加一些并不存在的虚拟结点，让其与完全二叉树相对应起来，如下：
但是这种方式，使得存储空间利用率降低，而且不方便判断是某个结点是否有左或右孩子，也不方便判断这个结点是否属于叶子结点。因此对于二叉树，一般使用链式存储结构。
二叉链表的结点，至少包含三个域：
链式存储实现二叉树定义：
#includenamespace MYTREE{using std::cout;
using std::endl;
// 链式存储实现二叉树
// 二叉树结点定义
struct TreeNode {int data; // 数据域
TreeNode* lc; // 指向左孩子节点的指针
TreeNode* rc; // 指向右孩子节点的指针
};
// 二叉树
typedef TreeNode* BinaryTree;
// 给指定结点添加孩子结点
// 约定flag：true 表示左孩子 false 表示右孩子
bool InsertNode(TreeNode* node, bool flag, int value) {if (node == NULL) { return false;
}
// 创建新的结点
TreeNode* new_node = new TreeNode;
new_node->data = value;
new_node->lc = NULL;
new_node->rc = NULL;
if (flag) { // 添加左子结点
node->lc = new_node;
}
else { // 添加右子结点
node->rc = new_node;
}
return true;
}
}
int main() {using namespace MYTREE;
// 创建一棵空树
BinaryTree tree = NULL;
// 插入根结点 1
tree = new TreeNode;
tree->data = 1;
tree->lc = NULL;
tree->rc = NULL;
// 插入根结点的左子结点 2
InsertNode(tree, true, 2);
// 插入根结点的右子结点 3
InsertNode(tree, false, 3);
// 给跟结点的左孩子结点插入右子结点 4
InsertNode(tree->lc, false, 4);
// 给跟结点的右孩子结点插入左子结点 6
InsertNode(tree->rc, true, 6);
// 给跟结点的右孩子结点插入右子结点 7
InsertNode(tree->rc, false, 7);
// 给跟结点的左孩子结点的右孩子结点插入右子结点 11
InsertNode(tree->lc->rc, false, 11);
// 给跟结点的右孩子结点的左孩子结点插入左子结点 12
InsertNode(tree->rc->lc, true, 12);
} 使用两个指针表示左右孩子结点，可以很方便的访问到左右孩子结点，但是要访问其父结点就只能从头遍历，可以根据实际情况，在结点中增设一个父结点指针，指向其父结点，这样的链表称为三叉链表。
4、二叉树的遍历 4.1 先序、中序、后续遍历遍历一棵二叉树，需要确定对根结点N，左子树L 和右子树R 的访问顺序，一般按照先左后右的原则，遍历顺序中的序是指访问根结点的顺序，常见的分为三种：
对于有n个结点的一棵二叉树，使用三种遍历方式的递归算法，若不考虑访问结点的方式带来的影响，那么：
// 先序遍历：根→左孩子→右孩子
void PreOrder(const BinaryTree& tree) {// 如果是空树，则什么也不做
if (tree != NULL) {// 最先访问根结点
cout<< tree->data<< " ";
// 然后访问左子树
PreOrder(tree->lc);
// 最后访问右子树
PreOrder(tree->rc);
}
}// 中序遍历
void InOrder(const BinaryTree& tree) {// 如果是空树，则什么也不做
if (tree != NULL) {// 最先访问左子树
InOrder(tree->lc);
// 然后访问根结点
cout<< tree->data<< " ";
// 最后访问右子树
InOrder(tree->rc);
}
}// 后序遍历
void PostOrder(const BinaryTree& tree) {// 如果是空树，则什么也不做
if (tree != NULL) {// 最先访问左子树
PostOrder(tree->lc);
// 然后访问右子树
PostOrder(tree->rc);
// 最后访问根结点
cout<< tree->data<< " ";
}
}// 求二叉树的深度
int GetDepth(const BinaryTree& tree) {if (tree == NULL) {return 0;
}
else {int l = GetDepth(tree->lc); // 求出左子树的深度
int r = GetDepth(tree->rc); // 求出由子树的深度
// 树的深度 = Max(左子树深度，右子树深度) + 1
return l >r ? l + 1 : r + 1;
}
}二叉树的层序遍历是指，从上到下，从左到右一次遍历每个结点，需要借助队列完成。
使用一个链式队列来存储二叉树的结点指针：
// 链式队列的一个节点
struct LQNode {// 数据域存储的是二叉树的一个结点的指针
TreeNode* data;
LQNode* next;
};
// 链式队列
struct LinkQueue {LQNode* front; // 队头指针，指向第一个节点或者指向头结点
LQNode* rare; // 队尾指针，指向最后一个节点
};
// 带头结点的链式队列 初始化
void InitLinkQueue(LinkQueue& queue) {// 初始时，队头指针、队尾指针都指向头结点
queue.front = queue.rare = new LQNode;
// 头结点的next指针域指向空
queue.front->next = NULL;
}
// 带头结点的链式队列 判断是否为空
bool LinkQueueIsEmpty(LinkQueue queue) {// 通过头指针与尾指针是否指向同一个位置判断
return queue.front == queue.rare;
}
// 带头结点的链式队列 入队
// 将 一个指向二叉树结点的指针 TreeNode* 存入队列尾部
bool LinkQueueIn(LinkQueue& queue, TreeNode* node_pointer) {// 创建一个新的节点
LQNode* s = new LQNode;
if (s == NULL) {// 分配内存失败
return false;
}
// 将数据存入新的节点
s->data = node_pointer;
// 新节点应该是最后一个节点，它的指针域应该指向NULL
s->next = NULL;
// 将新的节点插入到队尾（只能从队尾插入）
queue.rare->next = s;
// 队尾指针后移,指向新插入的节点
queue.rare = s;
return true;
}
// 带头结点的链式队列 出队
// 使用引用变量的方式，将一个指向二叉树结点的指针 TreeNode* 返回
bool LinkQueueOut(LinkQueue& queue, TreeNode*& node_pointer) {if (queue.front == queue.rare) {return false; // 空队列
}
// 指向要出队的节点
// 队首结点是头结点的后继节点
LQNode* p = queue.front->next;
// 先使用引用变量将要出队的元素返回
node_pointer = p->data;
// 修改头结点的后继节点
queue.front->next = p->next;
// 如果此时是最后一个元素出队
if (queue.rare == p) {// 队尾指针也指向头结点
queue.rare = queue.front;
}
// 释放内存空间
delete p;
return true;
}层序遍历二叉树：
// 层序遍历
void LevelOrder(const BinaryTree& tree) {// 辅助队列
LinkQueue queue;
// 初始化空队列
InitLinkQueue(queue);
// 当前访问的结点
TreeNode* p = NULL;
// 根结点入队
LinkQueueIn(queue, tree);
// 如果队列不为空，开始循环
while (!LinkQueueIsEmpty(queue)) {// 队头节点出队
LinkQueueOut(queue, p);
// 访问出队结点数据域
cout<< p->data<< " ";
// 如果左子树不为空，左子树根结点入队
if (p->lc != NULL) { LinkQueueIn(queue, p->lc);
}
// 如果右子树不为空，右子树根结点入队
if (p->rc != NULL) { LinkQueueIn(queue, p->rc);
}
}
}若只给出一棵二叉树的前序遍历序列或中序遍历序列或后序遍历序列或层序遍历序列，无法确定唯一的一棵二叉树。由中序遍历序列和其他三个中的任意一个遍历序列组合，就能确定唯一的二叉树：
传统的二叉链表，仅仅能体现父子关系，无法表达出结点在遍历序列中的前驱或后继。
以普通二叉树的中序遍历为例：
包含n个节点的二叉树中，存在 n+1 个空指针域。可以利用这些空指针域，来存放结点在遍历序列中的前驱指针和后继指针。
因此，根据如下规定，若某个结点：
中序线索二叉树，以中序序列为依据进行线索化。先序线索二叉树与后续线索二叉树同理。
#include// 线索二叉树
namespace CLUE_BINARY_TREE {using std::cout;
using std::endl;
typedef int E;
// 定义线索二叉树的结点
struct CBTreeNode {E data;// 数据域
CBTreeNode* lc; // 左孩子指针或者前驱结点指针
CBTreeNode* rc; // 右孩子指针或者后继结点指针
int l_tag; // 左指针标识，0表示指向的是左孩子，1表示指向的是前驱
int r_tag; // 右指针标识，0表示指向的是右孩子，1表示指向的是后继
};
// 线索二叉树
typedef CBTreeNode* CBTree;
// 给指定结点添加孩子结点 约定flag：true 表示左 false 表示右
bool AddNode(CBTreeNode* node, bool flag, E value) {if (node == NULL) { return false; // 指定结点不能为空
}
CBTreeNode* new_node = new CBTreeNode; // 创建新的结点
new_node->data = value;
new_node->lc = NULL;
new_node->rc = NULL;
if (flag) { node->lc = new_node; // 添加左子结点
}
else { node->rc = new_node;// 添加右子结点
}
return true;
}
// 构建一棵二叉树
void BuildTree(CBTree& tree) {// 创建 根结点
tree = new CBTreeNode;
tree->data = 1;
tree->lc = NULL;
tree->rc = NULL;
AddNode(tree, true, 2); // 根结点添加左孩子
AddNode(tree, false, 3); // 根结点添加右孩子
AddNode(tree->lc, true, 4); // 根结点的左孩子添加左孩子
AddNode(tree->lc, false, 5); // 根结点的左孩子添加右孩子
AddNode(tree->rc, true, 6); // 根结点的右孩子添加左孩子
AddNode(tree->rc, false, 7); // 根结点的右孩子添加右孩子
AddNode(tree->rc->rc, true, 8); // 根结点的右孩子 的右孩子 添加左孩子
AddNode(tree->rc->rc, false, 9); // 根结点的右孩子 的右孩子 添加右孩子
}
void Visit(const CBTree& tree) {cout<< tree->data<< " ";
}
// 普通二叉树的中序遍历
void InOrder(const CBTree& tree) {if (tree != NULL) { // 先访问左子树
InOrder(tree->lc);
// 访问根结点
Visit(tree);
// 后访问右子树
InOrder(tree->rc);
}
}
// 通过中序遍历对二叉树进行线索化递归算法
// p 指向正在访问的结点；pre 指向刚刚访问过的结点
void InClue(CBTree& p, CBTree& pre) {if (NULL != p) { // 递归线索化左子树
InClue(p->lc, pre);
// 左子树为空，则建立前驱线索
if (NULL == p->lc) { p->lc = pre; // 指向前驱结点
p->l_tag = 1; // 表示lc指向的是前驱结点
}
// 建立前驱结点的后继线索
if (NULL != pre && NULL == pre->rc) { pre->rc = p; // 指向后继结点
pre->r_tag = 1; // 表示rc指向的是后继结点
}
// 标记当前结点为刚刚访问过的结点
pre = p;
// 递归线索化右子树
InClue(p->rc, pre);
}
}
// 建立中序线索二叉树
void CreateInCBTree(CBTree& tree) {// 指向刚刚访问过的结点的指针
CBTreeNode* pre = NULL;
// 如果是非空二叉树，则进行线索化
if (NULL != tree) { // 线索化二叉树
InClue(tree, pre);
// 处理遍历序列中的最后一个节点
pre->rc = NULL;
pre->r_tag = 1;
}
}
// 求中序线索二叉树 中序序列的第一个结点
CBTreeNode* GetFirst(CBTreeNode* p) {while (p->l_tag == 0) { p = p->lc;
}
return p;
}
// 求线索二叉树中，中序序列的最后结点
CBTreeNode* GetLast(CBTreeNode* p) {while (p->r_tag == 0) { p = p->rc;
}
return p;
}
// 求线索二叉树中，结点p在中序序列下的后继结点
CBTreeNode* GetNext(CBTreeNode* p) {if (p->r_tag == 0) { return GetFirst(p->rc);
}
else { // 为 1 直接返回后继线索
return p->rc;
}
}
// 求线索二叉树中，结点p在中序序列下的前驱结点
CBTreeNode* GetPre(CBTreeNode* p) {if (p->l_tag == 0) { return GetLast(p->lc);
}
else { // 为 1 直接返回前驱线索
return p->lc;
}
}
// 中序线索二叉树的遍历
void InClueOrder1(CBTree tree) {for (CBTreeNode* p = GetFirst(tree); p != NULL; p = GetNext(p)) { Visit(p); // 访问结点
}
}
// 中序线索二叉树的逆向遍历
void InClueOrder2(CBTree tree) {for (CBTreeNode* p = GetLast(tree); p != NULL; p = GetPre(p)) { Visit(p); // 访问结点
}
}
}
int main() {using namespace CLUE_BINARY_TREE;
CBTree tree;
BuildTree(tree);
// 普通中序遍历线索二叉树
// InOrder(tree);
cout<< endl;
// 构建中序线索二叉树
CreateInCBTree(tree);
// 遍历中序线索二叉树
InClueOrder1(tree);
cout<< endl;
InClueOrder2(tree);
} 
#define MAX_SIZE 100
typedef int E;
// 树的结点定义
struct TreeNode {E data; // 数据域
int parent; // 双亲的位置域
};
// 树的定义
struct MyTree {TreeNode nodes[MAX_SIZE]; // 结点数组
int n; // 结点数
};
// 链式存储实现二叉树
// 二叉树结点定义
struct TreeNode {int data; // 数据域
TreeNode* lc; // 指向左孩子节点的指针
TreeNode* rc; // 指向右孩子节点的指针
};
// 二叉树
typedef TreeNode* BinaryTree;左子树结点值< 根结点值< 右子树结点值：
// 查找，非递归实现，空间复杂度 O(1)
TreeNode* Search1(BinaryTree tree, int e) {while (tree != NULL && e != tree->data) {// 目标值在右子树上
if (e >tree->data) { tree = tree->rc;
}
// 目标值在左子树上
else { tree = tree->lc;
}
}
return tree;
}
// 查找，递归实现，空间复杂度O(h)，h表示树的高度
TreeNode* Search2(BinaryTree tree, int e) {if (tree == NULL) {// 查找失败
return NULL;
}
if (e == tree->data) {return tree; // 查找成功
}
else if (e< tree->data) {// 在左子树上查找
return Search2(tree->lc,e);
}
else {// 在右子树上查找
return Search2(tree->rc,e);
}
}若原二叉排序树为空，则直接插入结点，否则，若关键字 k 小于根结点的值，将其插入到左子树上，若关键字 k 大于根结点的值，将其插入到右子树上。
// 插入，递归实现，空间复杂度O(h)，h 为二叉树的高度
bool Insert1(BinaryTree& tree, int e) {if (tree == NULL) {// 空树，直接插入到根结点
tree = (BinaryTree)malloc(sizeof(TreeNode));
tree->data = e;
tree->lc = tree->rc = NULL;
return true;
}
else if (e == tree->data) {// 存在相同关键字结点，插入失败
return false;
}
else if (e< tree->data) {// 在左边插入
Insert1(tree->lc, e);
}
else {// 在右边插入
Insert1(tree->rc, e);
}
}可以使用插入函数，构造一棵二叉搜索树：
// 通过一个数组构造一棵二叉排序树
void BuildBST(BinaryTree& tree, int arr[], int n) {tree = NULL;
int i = 0;
while (i< n) {Insert1(tree, arr[i]);
i++;
}
}先搜索找到目标结点：
查找成功时的查找长度：
最坏的情况：每个结点只有一个分支，树的高度h等于结点数n，平均查找长度 O(n)
最好的情况：n 个节点的二叉树，达到最小高度，即 log2n 向下取整再加1，此时的平均查找长度为 O(log2n)
查找失败时的查找长度：
平衡二叉树（Balanced Binary Tree），简称平衡树（AVL树）：树上任一结点的左子树和右子树的高度差不超过1。
结点的平衡因子= 左子树的高度 - 右子树的高度
因此，平衡二叉树的各结点的平衡因子只可能是 -1或0或1。
平衡二叉树的定义// 平衡二叉树的结点定义
struct AVLNode {int key; // 数据域
int balance; // 平衡因子
AVLNode* lc; // 左孩子指针
AVLNode* rc; // 右孩子指针
};
// 平衡二叉树定义
typedef AVLNode* AVLTree;二叉排序树在插入结点后，如何保持平衡，使得查找操作的时间复杂度达到最优的 O(log2n)？
从新插入结点往回找到第一个不平衡的结点（最小不平衡子树），调整以该结点为根的子树。
最小不平衡子树恢复平衡后，其他受影响的结点也将恢复平衡
如何让最小不平衡子树恢复平衡呢？需要分四种情况：
RR 在A结点的右孩子的右子树中插入新的结点导致不平衡
LR 在A结点的左孩子的右子树中插入新的结点导致不平衡
RL 在A结点的右孩子的左子树中插入新的结点导致不平衡
结点的权：给树中的结点赋予一个表示某种意义的数值，这个数值就是该结点的权。
结点的带权路径长度：从根结点到任意结点的路径长度与该结点权值的乘积，称为结点的带权路径长度。
树的带权路径长度：所有叶子结点的带权路径长度之和。
哈夫曼树：在含有 n 个带权叶结点的二叉树中，其中带权路径长度最小的二叉树叫做最优二叉树，也叫做哈夫曼树。
如下三个二叉树都有 4个带权的叶子结点：
第三个二叉树的带权路径长度最小，第三个二叉树是哈夫曼树。
第二种构造结果：
比如，要传递四个字符 A B C D
前缀编码：如果不存在一个编码是另一个编码的前缀，则称这样的编码是前缀编码，非前缀编码在解码是有歧义。
由哈夫曼树得到哈夫曼编码：字符集中的每个字符作为一个叶子结点，各个字符出现的频度作为结点的权值，构造出哈夫曼树（可以将树的左指针看作二进制的0，右指针看作二进制的1）。
哈夫曼编码可以用于数据的压缩。
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧