文章目录
1.定义
1.二叉树：一颗二叉树由结点的有限集合组成，这个集合或者为空，或者由一个根结点及两颗不相交的二叉树组成。
<font color="#ff0000">注意</font>：左右子树不相交，说明它们没有公共的节点，公共的节点意思是数值相同，指针域也相同。
2.满二叉树：满二叉树的每一个结点或者是一个分支结点（非叶结点），并恰好有两个非空子结点。或者是叶结点。
1
3.完全二叉树：从根结点起每一层从左至右填充，一颗高度为d的完全二叉树除了底层（最后一层，即d-1层）以外，每一层都是满的。底层的叶子结点集中在左边的若干位置上。
2
2.名词区分
<font color="#ff0a0a0">高度，深度，层数</font>：
结点M的深度(depth)就是从根结点到M的路径长度。数的高度(height)等于最深结点的深度加1，任何深度为d的结点的层数也是d，根结点的层数和深度都是0
3.一些定理和结论
-
一棵有
个结点的二叉树的形态总共有
4
（详细介绍：卡特兰数及其应用） -
满二叉树定理：非空满二叉树的叶结点数等于其分支结点数加1
（简单理解：假设一棵有n-1个分支结点的二叉树满足上面的结论，当某棵二叉树有n个分支结点时，选中一个分支结点，这个分支结点的左右子结点都是叶子结点，然后把这2个叶子结点都删掉（后果是删了一个分支结点，删了一个叶子结点），形成的新的二叉树满足之前的归纳假设，所以原二叉树也满足结论。）推论：一颗非空二叉树空子树的数目等于 其结点数目加1
4.遍历
先根遍历
2
(图片来源：https://images.app.goo.gl/fdMEerRMHvwLd46Z7)
后根遍历和中根遍历也是顾"名"思"义"的。
(1)由中根遍历和先根遍历确定树的唯一形态
简要思路（证明）
代码：
下面代码中用哈希表查找上面证明中m的值，查找的时间复杂度是O(1),否则顺序查找会要O(n)的时间，n为结点个数。
算法（构造唯一树）的整体时间复杂度是O(n)
#include <stdio.h>
#include <stdlib.h>
#define LEN sizeof(Tree)
#define NULLKEY -32768
typedef struct Tree {
char element;
Tree* left;
Tree* right;
};
void preOrder(Tree* root) {
if (root == NULL)return;
printf("%c ", root->element);
preOrder(root->left);
preOrder(root->right);
}
void inOrder(Tree* root) {
if (root == NULL)return;
inOrder(root->left);
printf("%c ", root->element);
inOrder(root->right);
}
void postOrder(Tree* root) {
if (root == NULL)return;
postOrder(root->left);
postOrder(root->right);
printf("%c ", root->element);
}
void freeAll(Tree* root) {
if (root == NULL)return;
freeAll(root->left);
freeAll(root->right);
free(root);
}
typedef struct
{
int* elem; //基址
int count; //当前数据元素个数
}HashTable;
int Search(char* Array, HashTable* hashTable, int data);
//核心函数
Tree* strucrTree(char* pre, char* in, int start,int end,HashTable& ht) {
//index记录先根遍历的父节点位置，最开始是根结点
static int index = 0;
if (start > end)
return NULL;
Tree* root = (Tree*)malloc(sizeof(Tree));
root->element = pre[index++];
root->left = NULL;
root->right = NULL;
if (start == end)
return root;
//in_index记录index对应节点在中根遍历中的位置
int in_index = Search(in,&ht, pre[index]);
root->left = strucrTree(pre, in, start, in_index - 1, ht);
root->right = strucrTree(pre, in, in_index+1, end , ht);
return root;
}
int m = 0; // 哈希表长度
/*初始化*/
int Init(HashTable* hashTable,int size)
{
int i;
m = 2*size;
hashTable->elem = (int*)malloc(m * sizeof(int)); //申请内存
hashTable->count = m;
for (i = 0; i < m; i++)
{
hashTable->elem[i] = NULLKEY;
}
return 1;
}
/*哈希函数*/
int Hash(int data)
{
return data % m;
}
/*插入*/
void Insert(HashTable* hashTable, int key,int value)
{
int hashAddress = Hash(key); //求哈希地址
//发生冲突
while (hashTable->elem[hashAddress] != NULLKEY)
{
//利用开放定址的线性探测法解决冲突
hashAddress = (++hashAddress) % m;
}
//插入值
hashTable->elem[hashAddress] = value;
}
/*查找*/
int Search(char* Array,HashTable* hashTable, int data)
{
int hashAddress = Hash(data); //求哈希地址
//发生冲突
while (Array[hashTable->elem[hashAddress]] != data)
{
//利用开放定址的线性探测法解决冲突
hashAddress = (++hashAddress) % m;
if (hashTable->elem[hashAddress] == NULLKEY || hashAddress == Hash(data)) return -1;
}
//查找成功
return hashTable->elem[hashAddress];
}
int main() {
char preorder[8] = { '1','2','4','6','5','7','3','8' };
char inorder[8] = { '6','4','2','5','7','1','3','8' };
int length = sizeof(inorder);
Tree* root = (Tree*)malloc(LEN);
HashTable hashtable;
Init(&hashtable, length);
for (int i = 0; i < length; ++i) {
Insert(&hashtable, inorder[i],i);
}
root = strucrTree(preorder, inorder, 0,length-1, hashtable);
preOrder(root);
freeAll(root);
}
5.二叉树的应用
1.二叉检索树
2.表达式树
3.利用最大堆实现优先队列
4.最小堆和哈夫曼编码
6.Reference
1.《数据结构与算法分析（C++版）（第三版）》第5章 二叉树
2.https://images.app.goo.gl/fdMEerRMHvwLd46Z7
网友评论