二叉树
定义
- 二叉树是n（n≥0）个结点的有限集合：
① 或者为空二叉树，即n=0。
② 或者由一个根结点和两个互不相交的被称为根的左子树
和右子树组成。左子树和右子树又分别是一棵二叉树。
* 1.每个结点最多有两棵子树。
* 2.左右子树有顺序二叉树的五种基本形态：
- 1.空树
- 2.只有一个根结点
- 3.根结点只有左子树
- 4.根结点只有右子树
- 5.根结点既有左子树又有右子树
特殊二叉树
- 1.斜树
- 2.满二叉树:
- 3.完全二叉树
二叉树的性质
- 1.非空二叉树上叶子结点数等于度为2的结点数加1
- 2.非空二叉树上第K层上至多有2^k−1个结点（K≥1）
- 3.高度为H的二叉树至多有2^H-1个结点（H≥1）
- 4.具有N个（N>0）结点的完全二叉树的高度为 [log2(N+1)]或[log2N] +1。
- 定义二叉树:
struct TreeNode {
int data;
TreeNode *left, *right;
TreeNode(){}
TreeNode(int _data, TreeNode* _left, TreeNode* _right):data(_data), left(_left), right(_right){}
};二叉树的存储结构
顺序存储
- 二叉树的顺序存储结构就是用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素。
链式存储
- 二叉树每个结点最多两个孩子，所以设计二叉树的结点结构时考虑两个指针指向该结点的两个孩子。
二叉树的遍历
- 先序遍历：
1）访问根结点；
2）先序遍历左子树；
3）先序遍历右子树。
* 递归
* 非递归- 中序遍历：
1）中序遍历左子树；
2）访问根结点；
3）中序遍历右子树。
* 递归
* 非递归- 后序遍历：
1）后序遍历左子树；
2）后序遍历右子树；
3）访问根结点。
* 递归
* 非递归- 层次遍历：
若树为空，则什么都不做直接返回。
否则从树的第一层开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。
- 例子：
// 前序遍历: 根 -> 左 -> 右
void printPostorder(struct TreeNode* node) {
if (node == NULL)
return;
// 根
cout << node->data << "";
// 左
printPostorder(node->left);
// 右
printPostorder(node->right);
}
// 中序遍历: 左 -> 根 -> 右
void printInorder(struct TreeNode* node) {
if (node == NULL)
return;
// 左
printInorder(node->left);
// 根
cout << node->data << " ";
// 右
printInorder(node->right);
}
// 后序遍历: 左 -> 右 -> 根
void printPreorder(struct TreeNode* node) {
if (node == NULL)
return;
// 左
printPreorder(node->left);
// 右
printPreorder(node->right);
// 根
cout << node->data << " ";
}
// 层次遍历
void printLevelOrder(struct TreeNode* node) {
queue<TreeNode *> q;
if(!node) q.push(node);
while(!q.empty()) {
// 当前的长度是上一层的个数
int len = q.size();
for(int i = 0; i < len; i ++) {
TreeNode * tmp = q.top();
q.pop();
cout << tmp->data << " ";
if(tmp->left) q.push(tmp->left);
if(tmp->right) q.push(tmp->right);
}
}
}
// 迭代的前序遍历, root left right
void iterativePreorder(struct TreeNode *root) {
if(root == NULL) return;
stack<TreeNode *> sta;
sta.push(root);
while(!sta.empty()) {
// 注意先进后出, 所以先right后left
TreeNode * tmp = sta.top();
sta.pop();
cout << tmp->data << " ";
if(tmp->right) sta.push(tmp->right);
if(tmp->left) sta.push(tmp->left);
}
}线索二叉树
- N个结点的二叉链表，每个结点都有指向左右孩子的
结点指针，所以一共有2N个指针，而N个结点的二叉
树一共有N-1条分支，也就是说存在2N-(N-1)=N+1个空指针。比如左图二叉树中有6个结点，那么就有7个空
指针。
大量的空余指针能否利用起来？
- 指向前驱和后继的指针称为线索，加上线索的二叉链表就称为线索链表，相应的二叉树就称为线索二叉树
- 对二叉树以某种次序遍历使其变为线索二叉树的过程就叫做线索化
哈夫曼树和哈夫曼编码
- 算法的描述如下：
1）将这N个结点分别作为N棵仅含一个结点的二叉树，构成森林F。
2）构造一个新结点，并从F中选取两棵根结点权值最小的树作为新结点的左、右子树，并且将新结点的权值
置为左、右子树上根结点的权值之和。
3）从F中删除刚才选出的两棵树，同时将新得到的树加入F中。
4）重复步骤2）和3），直至F中只剩下一棵树为止。
