二叉树
- 树的概念及结构
- 二叉树概念及结构
- 二叉树的概念
- 二叉树的存储结构
- 二叉树的顺序结构及实现
- 大根堆和小根堆
- 堆的实现及其各个接口
- 堆的初始化和空间销毁
- 入堆
- 删除堆顶元素
- 返回堆顶元素
- 返回堆的大小
- 判断堆是否为空
- 二叉树的链式实现
- 二叉树的初始化
- 二叉树的创建
- 前序遍历
- 中序遍历
- 后序遍历
- 二叉树的销毁
- 二叉树的大小
- 二叉树第k层的大小
- 二叉树查找数据
树的概念及结构
树是一种非线性的数据结构，是由n个有限结点组成的具有一个层次关系的集合，把称为树是因为把它倒着看很像一颗树。
- 有一个特殊的结点，称为根节点，根节点没有前驱结点
- 除根结点之后，其余的结点都是互不相交的集合，每一个集合都是一颗结构与树类似的子树。
- 树是递归定义的
像这样，就被称为树。
子树一旦相交，就不再叫做树，而是另一种特殊的数据结构—图
除此之外，树还有一些性质。
节点的度：一个节点含有的子树的个数称为该节点的度，如1的度为2
叶节点或终端节点：度为0的节点称为叶节点，如4，5，6，7都是叶节点
非终端节点或分支节点：度不为0的节点 ，如1，2，3
双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点 ，如1是2的父节点
孩子节点或子节点：一个节点含有的子树的根节点，如2是1的孩子节点
兄弟结点：具有同一个父节点的子树，如2和3就互为兄弟结点
树的度：树最大的节点的度称为树的度，如树的度为2
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
树的高度或深度：树中节点的最大层次； 如上图：树的高度为3
堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：4和6
节点的祖先：从根到该节点所经分支上的所有节点；如上图：1是所有节点的祖先
子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是1的子孙
森林：由m（m>0）棵互不相交的树的集合称为森林
那么树是怎么表示的呢？
树的结构就有点复杂了，用线性表定义树的话呢，会面临一个问题：就是一个节点可能有n个子树，那么定义多少个接口来存储该节点和子树的关系呢？这个不太好解决。于是，有大佬相出了解决办法：孩子兄弟表示法，孩子表示法等等，在这里讲解一下孩子兄弟表示法。
struct Node
{
struct Node* left_child; //左孩子
struct Node* right_child;//右兄弟
int data;//数据
}
就比如上图中的树，
这样存，不管有多少个子树，都可以存储，left存左二子，right存兄弟。
二叉树概念及结构
二叉树的概念
二叉树是一种特殊的树形结构，它有一个根节点以及每个节点最多有两个子节点(一个左孩子，一个右孩子)
性质：
- 因为每个节点最多两个孩子，所以二叉树的最大的度不超过2
- 左儿子是左儿子，右儿子是右儿子，有顺序之分
- 叶子节点没有子节点
- 每一层上的节点数目都不超过2的n - 1次方，根节点为第一层
- 对于深度为k的二叉树来说，最多有2的n次方-1个节点，最少有k个节点
- 对任何一棵二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为n2，则有n0 = n2 + 1
- 若规定根节点的层数为1，具有n个结点的满二叉树的深度**，**h= log(n + 1). (ps： 是log以2为底，n+1为对数)
特殊的二叉树
满二叉树：深度为k且有2的k次方-1个节点的二叉树称为满二叉树
完全二叉树：对于深度为k的二叉树来说，除了第k层节点从左到右连续排列外，其余层节点都连续的排列
二叉树的存储结构
提到存储结构，肯定是顺序结构和链式结构。
-
二叉树的顺序结构就是利用数组去存储，一般使用数组只适合完全二叉树，因为不是完全二叉树会有空间的浪费(完全二叉树会使得数组中的每一个位置都存的有元素，而非完全二叉树会造成空间的浪费，想一想为什么)
-
链式存储：定义一个结构体，结构体中 有两个结构体指针，一个存数据，一个指针用来指向左二子，一个指针用来指向右儿子。
typedef char TreeDataType; typedef struct BinaryTreeNode { TreeDataType val; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BTNode;
二叉树的顺序结构及实现
普通的二叉树不适合用数组来存储数据，因为可能会造成大量的空间浪费，而完全二叉树比较适合使用顺序结构存储。
提到完全二叉树，就不得不提到堆这一概念，堆是一个数据结构而不是管理内存的一块区域分段。
大根堆和小根堆
大根堆就是每个节点的值都大于等于父节点的值，根节点的值最大
小根堆就是每个节点的值都小于等于父节点的值，根节点的值最小
堆的实现及其各个接口
实现堆，还是结构体那一套。
typedef struct Heap
{
int capacity;
HeapDataType* val;
int count;
}Heap;
void HeapInit(Heap* ps);//初始化
void HeapDestory(Heap* ps);//销毁空间
void HeapPush(Heap* ps, HeapDataType x);//入堆
void HeapPop(Heap* ps);//出堆
HeapDataType HeapTop(Heap* ps);//返回堆顶元素
int HeapSize(Heap* ps);//堆的大小
bool HeapEmpty(Heap* ps);//堆是否为空
堆的初始化和空间销毁
之前的链表，顺序表，双链表等数据结构会的话相信堆的初始化和销毁难不倒各位。
void HeapInit(Heap* ps)
{
ps->capacity = 4;
ps->count = 0;
ps->val = (HeapDataType*)malloc(sizeof(HeapDataType) * ps->capacity);
}
void HeapDestory(Heap* ps)
{
ps->capacity = ps->count = 0;
free(ps->val);
ps->val = NULL;
}
入堆
入堆之前要检查数组的空间是否够用，够用则直接加入数据，不够则扩容。
void HeapPush(Heap* ps, HeapDataType x)
{
assert(ps);
if (ps->capacity == ps->count)
{
ps->capacity *= 2;
HeapDataType* tmp = (HeapDataType*)realloc(ps->val, sizeof(HeapDataType) * ps->capacity);
if (tmp == NULL)
{
perror("malloc fail");
exit(-1);
}
}
ps->val[ps->count++] = x;
HeapJustUp(ps->val, ps->count);
}
但是光加入数据可不行，要进行向上调整，把数据调整成小根堆或者大根堆，但是调整是有前提的，左右子树必须是一个堆，才不会导致堆内数据乱。所以我们每加入一个数据调整一次，即可做到堆是一个大堆或者小堆。
void HeapJustUp(HeapDataType* a, int n)
{
int parent = n - 2 >> 1;
int child = n - 1;
while (parent >= 0)
{
if (child + 1 < n && a[child + 1] > a[child])
{
child++;
}
if (a[parent] < a[child])
{
std::swap(a[parent], a[child]);
child = parent;
parent = child - 1 >> 1;
}
else
{
break;
}
}
}
向上调整堆，要找到父亲和孩子，父亲就是元素的总个数-2之后在/2，孩子就是元素总个数-1.
因为是向上调整，父亲节点的下标会慢慢变小，所以循环条件可以设置成parent>=0，有了循环条件，还要比较左右孩子哪个大，然后在让孩子和父亲比较，最后更新父亲下标和孩子下标即可。
删除堆顶元素
删除堆顶元素就是让堆顶元素和堆底元素进行一个交换，然后元素个数-1.交换完成之后，要进行向下调整，向下调整要求左右子树是大根堆或者小根堆，在入堆这一步，我们已经完成了这个操作，所以可以直接调整。
void HeapPop(Heap* ps)
{
assert(ps);
assert(ps->count);
std::swap(ps->val[0], ps->val[ps->count--]);
HeapJustDown(ps->val, 0, ps->count);
}
那么向下调整是怎么调的呢？
因为要把堆顶元素调到下面，所以从下标为0的位置开始向下调整。
0的位置就是父亲节点，然后要找到儿子节点child = parent * 2 + 1，然后判断左右孩子哪个大，在判断父亲节点和孩子节点的大小关系，更新下标即可。
void HeapJustDown(HeapDataType* a, int parent, int n)
{
int child = parent * 2 + 1;
while (child <= n)
{
if (child + 1 < n && a[child] < a[child + 1])
{
child++;
}
if (a[parent] < a[child])
{
std::swap(a[parent], a[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
返回堆顶元素
HeapDataType HeapTop(Heap* ps)
{
assert(ps);
return ps->val[0];
}
返回堆的大小
int HeapSize(Heap* ps)
{
assert(ps);
return ps->count;
}
判断堆是否为空
bool HeapEmpty(Heap* ps)
{
assert(ps);
return ps->count == 0;
}
二叉树的链式实现
typedef char TreeDataType;
typedef struct BinaryTreeNode
{
TreeDataType val;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
BTNode* TreeInit();//初始化
BTNode* BinaryTreeCreate();//创建二叉树
void BinaryTreeDestory(BTNode* root);//销毁二叉树
int BinaryTreeSize(BTNode* root);//二叉树的大小
int BinaryTreeLeveKSize(BTNode* root, int k);//第k层有多少个元素
BTNode* BinaryTreeFind(BTNode* root, TreeDataType x);//查找数据
void PrevOrder(BTNode* root);//前序遍历
void InOrder(BTNode* root);//中序遍历
void PosOrder(BTNode* root);//后序遍历
二叉树的初始化
BTNode* TreeInit()
{
BTNode* root = (BTNode*)malloc(sizeof(BTNode));
root->val = 0;
root->left = NULL;
root->right = NULL;
return root;
}
二叉树的创建
BTNode* Creat(BTNode* t)
{
TreeDataType ch;
cin >> ch;
if (ch == '-1')
{
t = NULL;
}
else
{
t->val = ch;
Creat(t->left);
Creat(t->right);
}
}
----------------------------------------------------------
BTNode* BuyNode(TreeDataType x)
{
BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);
}
newnode->val = x;
newnode->left = NULL;
newnode->right = NULL;
return newnode;
}
BTNode* BinaryTreeCreate()
{
BTNode* newnode1 = BuyNode('A');
BTNode* newnode2 = BuyNode('B');
BTNode* newnode3 = BuyNode('C');
BTNode* newnode4 = BuyNode('D');
BTNode* newnode5 = BuyNode('E');
BTNode* newnode6 = BuyNode('F');
BTNode* newnode7 = BuyNode('G');
newnode1->left = newnode2;
newnode1->right = newnode3;
newnode2->left = newnode4;
newnode4->left = newnode7;
newnode3->left = newnode5;
newnode3->right = newnode6;
return newnode1;
}
两种方法创建二叉树，第一种方法是用前序遍历的方法创建二叉树，第二种是自己手动创建一个二叉树。
前序遍历
二叉树的前序遍历是先访问根节点，在访问左子树，在访问右子树，是以递归的形式进行的
void PrevOrder(BTNode* root)
{
if (root == NULL)
{
cout << "NULL ";
return;
}
cout << root->val << ' ';
PrevOrder(root->left);
PrevOrder(root->right);
}
中序遍历
二叉树的中序遍历是先访问左子树，在访问根节点，然后右子树，同样是以递归的形式进行的。
void PrevOrder(BTNode* root)
{
if (root == NULL)
{
cout << "NULL ";
return;
}
cout << root->val << ' ';
PrevOrder(root->left);
PrevOrder(root->right);
}
后序遍历
先左子树，在右子树，最后根节点
void InOrder(BTNode* root)
{
if (root == NULL)
{
cout << "NULL ";
return;
}
InOrder(root->left);
cout << root->val << ' ';
InOrder(root->right);
}
二叉树的销毁
二叉树的创建是用的先序遍历，而二叉树的销毁则用的是后续遍历
void BinaryTreeDestory(BTNode* root)
{
if (!root)
{
return;
}
BinaryTreeDestory(root->left);
BinaryTreeDestory(root->right);
free(root);
}
二叉树的大小
二叉树的大小很好判断，想一想一个树很深，很多叶子，每个子树上都有一个小领导，小领导来查他管理的地区的叶子，然后层层向上汇报，直到汇报给最大的领导，就可以完成了。
int BinaryTreeSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
int l = BinaryTreeSize(root->left);
int r = BinaryTreeSize(root->right);
return l + r + 1;
}
二叉树第k层的大小
第k层的大小该怎么判断呢，还是用上面的办法，找到第k层的小领导，让他把第k层的情况汇报给你即可
int BinaryTreeLeveKSize(BTNode* root, int k)
{
if (root == NULL)
{
return 0;
}
if (k == 1)
{
return 1;
}
int l = BinaryTreeLeveKSize(root->left, k - 1);
int r = BinaryTreeLeveKSize(root->right, k - 1);
return l + r;
}
二叉树查找数据
查找数据，从左子树找，从右子树找，依次递归即可
BTNode* BinaryTreeFind(BTNode* root, TreeDataType x)
{
if (root == NULL)
{
return NULL;
}
if (root->val == x)
{
return root;
}
BTNode* l = BinaryTreeFind(root->left, x);
if (l)
{
return l;
}
BTNode* r = BinaryTreeFind(root->right, x);
if (r)
{
return r;
}
return NULL;
}
