树
树一个有n(n >= 0)个节点组成一个有限集合
1 有且仅有一个被称为根节点(root)的节点
2 当n > 1,除了根节点之外，剩余的m个节点互不相交，分别都是一颗颗的树
这些树我们称为子树，每一个节点实际上都是一棵树(子树)的根
树的每一个节点都包含两个部分
1 数据元素
2 节点和节点之间的关系，不像原先的链表，关系都是一个方向上面
1个节点可能有n个节点和它有关系(因此它就不是一个线性表)
每个节点的关系数量我们称为这个节点的度
度：出度(我可以到别人)，树里面我们暂时只考虑出度 入度(别人到我)
在树里面如果一个节点和别人没有关系了(出度为0)，这种节点我们称之为终端节点(叶子节点)
树的层次(深度)：从根开始，根为第一层，根的儿子为第二层，儿子的儿子为第三层......不能乱了辈分
二叉树 -- 一种树的形态，每个节点的度(出度)最多只有2，如果你的树满足这一点
这棵树就被称为二叉树，二叉树我们就可以分大小两边
根据这个大小我们可以分为左右关系，左边的被称为左儿子
右边的被称为右儿子
二叉树有5种形态
1 空树
2 只有一个根节点
3 只有一个左儿子
4 只有一个右儿子
5 有左右儿子
二叉树的基本性质
1 在二叉树的第i(i从1开始)层上面最多有 2 ^ (i - 1)
2 深度为k的二叉树最多有 2 ^ k - 1 个节点
3 对于任何一个二叉树，有如下关系
n0为度为0的节点个数 n1为度为1的节点个数 n2为度为2的节点个数
n为总节点数
n = n2 + n1 + n0
n = 分支数(出度的个数) + 1
分支数 = 2 * n2 + 1 * n1
n = 2 * n2 + 1 * n1 + 1
so:
2 * n2 + 1 * n1 + 1 = n2 + n1 + n0
-> n2 + 1 = n0
->这个性质对于任何一个多叉树都是适用的
假设你是一个m叉树
n = n0 + n1 + n2 + n3 + .... + nm
n = 分支数(出度的个数) + 1
分支数 = m * nm + (m - 1) * n(m - 1) + .... + 3 * n3 + 2 * n2 + 1 * n1
n0 + n1 + n2 + n3 + .... + nm = m * nm + (m - 1) * n(m - 1) + .... + 3 * n3 + 2 * n2 + 1 * n1 + 1
n0 = 1 + n2 + 2n3 + 3n4 + .... + (m - 1)nm ----> 可以直接套公式的
二叉树的两种特殊的形态
满二叉树：深度为k的二叉树有 2 ^ k - 1 个节点，这颗二叉树就是一颗满二叉树
不增加深度的情况，不能往这棵树里面添加节点
完全二叉树：
1 除去最后一层是一个满二叉树
2 最下面的那一层所有的节点都是尽左排，一个节点的左边是不能添加新的节点
满二叉树是一个特殊的完全二叉树
4 对于一个有n个节点的完全二叉树从上到下，从左往右，从1开始进行编号
根为1 根的左儿子为2 根的右儿子为3 ......
假设有一个节点的编号为 i
则，这个节点的父节点的编号为 i / 2
如果它有左儿子，那么它左儿子的编号为 2 * i
如果它有右儿子，那么它右儿子的编号为 2 * i + 1
5 具有n个节点的完全二叉树的深度为 log2(n) 向下取整 + 1
假设深度为k
2 ^ (k - 1) <= n < 2 ^ k
计算机如何来使用二叉树
首先我们应该要保存二叉树
1 数据
2 左右儿子(关系)
1 顺序结构来保存二叉树
由于完全二叉树是可以表示左右儿子关系和父亲关系的
因此完全二叉树才能用数组存储
就是上面的第4个性质
如果这棵树不是完全二叉树呢？数组保存不了，因此需要将不是完全二叉树的二叉树补全为完全二叉树
才能使用数组保存，这么一来浪费就有点多了
因此顺序结构存储二叉树就不是那么方便
2 链式结构保存
1 有数据域
2 有指针域 -> 至少要有两个指针 lchild rchild
struct TreeNode
{
Tree_Datatype data;//树的数据
struct TreeNode * lchild;//指向它的左儿子
struct TreeNode * rchild;//指向它的右儿子
};
二叉树的遍历：
遍历:根据某一种规则对集合里面所有元素的访问(必须访问1次，并且只能访问一次)
二叉树的遍历有三种(左边在右边的前面)
1 先序(根)遍历 -> 根 左 右
首先:先访问根节点
再次：以相同的规则继续访问根节点的左儿子
最后：以相同的规则继续访问根节点的右儿子
2 中序(根)遍历 -> 左 根 右
首先以相同的规则访问它的左孩子
访问根节点
最后以相同的规则继续访问根节点的右儿子
3 后序(根)遍历 -> 左 右 根
首先以相同的规则访问它的左孩子
再以相同的规则继续访问根节点的右儿子
访问根节点
练习：
一棵二叉树的先序为：EBADCFHGIKJ
中序为:ABCDEFGHIJK
请画出这棵树
先中序、中后序能确定这棵树
但是先后序不一定能确定这棵树
建立一棵二叉树：建立树之前我们需要先确定左边是什么关系，右边是什么关系
这种确定关系的二叉树我们叫二叉排序树
一般是根绝大小来进行确定的
一般左边为小右边为大
示例代码为左小右大
.h与.c
#ifndef __LISTTREE_H__
#define __LISTTREE_H__
#include <stdio.h>
#include <stdlib.h>
#include "ListStack.h"
#include "ArrayQueue.h"
typedef char ListTreeDataType;
//树的节点类型
typedef struct ListTreeNode
{
ListTreeDataType _data;
int _cnt;//记录这个元素的访问次数
//int _datanum;
struct ListTreeNode * _lchild,* _rchild;
}ListTreeNode;
//将这数据加入到这棵树里面去
ListTreeNode * ListTree_Add(ListTreeNode *root,const ListTreeDataType data);
//我想以递归的形式插入数据 你应该要怎么思考
ListTreeNode * ListTree_Insert(ListTreeNode *root,const ListTreeDataType data);
//遍历这棵树
//先序
void ListTree_PreOrder(ListTreeNode *root);
//中序
void ListTree_MidOrder(ListTreeNode *root);
//后序
void ListTree_PostOrder(ListTreeNode *root);
//求树高 层次
int ListTree_Level(ListTreeNode *root);
//以非递归的形式写先序中序后序 -> 利用栈
void ListTree_PreOrder_Stack(ListTreeNode *root);
//非递归的中序 和先序比较只需要改一点点 先序是入栈前访问，中序是出栈访问
void ListTree_MidOrder_Stack(ListTreeNode *root);
//非递归的后序访问
void ListTree_PostOrder_Stack(ListTreeNode *root);
//树的层次遍历 利用队列 我们在层次遍历的时候可以确定辈分，并且我可以求得这个数的宽度
//问怎么求宽度？ 在一层里面最多元素的元素个数就是数的宽度
int ListStack_LevelOrder(ListTreeNode *root);
//写一个销毁函数
void ListTree_Destory(ListTreeNode **root);
#endif#include "ListTree.h"
//这个节点建立出来是一个独立的节点
static ListTreeNode *ListTree_Node_create(const ListTreeDataType data)
{
ListTreeNode * ptr = (ListTreeNode *)calloc(1,sizeof(ListTreeNode));//创建节点
ptr ->_data = data;
return ptr;
}
//将这数据加入到这棵树里面去
ListTreeNode * ListTree_Add(ListTreeNode *root,const ListTreeDataType data)
{
if(!root)//如果这棵树为空的，则data就是根节点
{
return ListTree_Node_create(data);
}
//寻找插入位置 大的往右边去 小的往左边去 相等(树里面是没有相同的两个节点的)
//相等的情况我们有两种解决办法 1 直接丢弃 2 节点里面弄一个num表示这个数据有几个
//现在按第一种解决方案 直接丢弃
ListTreeNode * ptr = root;//有一个遍历指针 去找我们的插入位置
while(1)
{
if(data > ptr ->_data)//数据比较大 往右边找
{
if(ptr ->_rchild == NULL)//找到插入位置了
{
ptr ->_rchild = ListTree_Node_create(data);
break;
}
ptr = ptr ->_rchild;
}
else if(data < ptr ->_data)//数据比较小 往左边找
{
if(ptr ->_lchild == NULL)//找到插入位置了
{
ptr ->_lchild = ListTree_Node_create(data);
break;
}
ptr = ptr ->_lchild;
}
else//直接丢弃不要了
{
break;
}
}
return root;
}
//遍历这棵树
//先序
void ListTree_PreOrder(ListTreeNode *root)
{
if(!root)
return;
//首先:先访问根节点
printf("%c ",root ->_data);
///再次：以相同的规则继续访问根节点的左儿子
ListTree_PreOrder(root ->_lchild);
//最后：以相同的规则继续访问根节点的右儿子
ListTree_PreOrder(root ->_rchild);
}
//中序
void ListTree_MidOrder(ListTreeNode *root)
{
if(!root)
return;
//首先以相同的规则访问它的左孩子
ListTree_MidOrder(root ->_lchild);
//访问根节点
printf("%c ",root ->_data);
//最后以相同的规则继续访问根节点的右儿子
ListTree_MidOrder(root ->_rchild);
}
//后序
void ListTree_PostOrder(ListTreeNode *root)
{
if(!root)
return;
//首先以相同的规则访问它的左孩子
ListTree_PostOrder(root ->_lchild);
//再以相同的规则继续访问根节点的右儿子
ListTree_PostOrder(root ->_rchild);
//访问根节点
printf("%c ",root ->_data);
}
//求树高 层次
int ListTree_Level(ListTreeNode *root)
{
if(!root)
return 0;
//树高 = 左右儿子中间最高的那个高度 + 1
int h_l = ListTree_Level(root ->_lchild);
int h_r = ListTree_Level(root ->_rchild);
return h_l > h_r ? h_l + 1 : h_r + 1;
}
//销毁就是一个后序
static void ListTree_Destory_shixian(ListTreeNode *root)
{
if(!root)
return;
ListTree_Destory_shixian(root ->_lchild);
ListTree_Destory_shixian(root ->_rchild);
//销魂它自己
root ->_lchild = root ->_rchild = NULL;
printf("free %c\n",root ->_data);
free(root);
}
//写一个销毁函数
void ListTree_Destory(ListTreeNode **root)
{
ListTree_Destory_shixian(*root);
//让那边置空
*root = NULL;
}
//我想以递归的形式插入数据 你应该要怎么思考
ListTreeNode * ListTree_Insert(ListTreeNode *root,const ListTreeDataType data)
{
if(!root)//如果这棵树为空的，则data就是根节点
{
return ListTree_Node_create(data);
}
//如果数据比较小 我就一相同的规则插入到它的左子树上面去
if(root ->_data > data)
{
root ->_lchild = ListTree_Insert(root ->_lchild,data);
}
//如果数据比较大 我就一相同的规则插入到它的右子树上面去
else if(root ->_data < data)
{
root ->_rchild = ListTree_Insert(root ->_rchild,data);
}
return root;
}
//以非递归的形式写先序中序后序 -> 利用栈
void ListTree_PreOrder_Stack(ListTreeNode *root)
{
if(!root)
return;
//我需要一个栈
ListStack * st = ListStack_init(100);
//总纲：入栈前访问，数据先访问再入栈
ListTreeNode * ptr = root;
while(1)
{
//1 将左边的所有全部入栈(从根开始，根的左孩子，根的左孩子的左孩子，根的左孩子的左孩子的左孩子....一直弄到没有左孩子为止)
while(ptr)
{
printf("-%c ",ptr ->_data);
ListStack_push(st,(LS_DataType)ptr);
ptr = ptr ->_lchild;
}
if(ListStack_empty(st))// 栈空退出
break;
//2 出栈，转到出栈元素的右孩子回到第一步
ptr = (ListTreeNode *)ListStack_top(st);//先获取栈顶元素
ListStack_pop(st);//出栈
ptr = ptr ->_rchild;//转到它的右孩子
}
printf("\n");
ListStack_destory(&st,NULL);
}
//非递归的中序 和先序比较只需要改一点点 先序是入栈前访问，中序是出栈访问
void ListTree_MidOrder_Stack(ListTreeNode *root)
{
if(!root)
return;
//我需要一个栈
ListStack * st = ListStack_init(100);
//总纲：入栈前访问，数据先访问再入栈
ListTreeNode * ptr = root;
while(1)
{
//1 将左边的所有全部入栈(从根开始，根的左孩子，根的左孩子的左孩子，根的左孩子的左孩子的左孩子....一直弄到没有左孩子为止)
while(ptr)
{
ListStack_push(st,(LS_DataType)ptr);
ptr = ptr ->_lchild;
}
if(ListStack_empty(st))// 栈空退出
break;
//2 出栈，转到出栈元素的右孩子回到第一步
ptr = (ListTreeNode *)ListStack_top(st);//先获取栈顶元素
ListStack_pop(st);//出栈
printf("+%c ",ptr ->_data);
ptr = ptr ->_rchild;//转到它的右孩子
}
printf("\n");
ListStack_destory(&st,NULL);
}
//非递归的后序访问
void ListTree_PostOrder_Stack(ListTreeNode *root)
{
if(!root)
return;
//我需要一个栈
ListStack * st = ListStack_init(100);
//后序是它的左右孩子都访问完毕之后太轮到他访问
//因此我们需要叠加一个访问的次数
ListTreeNode * ptr = root;
while(1)
{
//1 将左边所有全部入栈，入栈的时候访问次数置1
while(ptr)
{
ptr ->_cnt = 1;//让它的左孩子先弄完
ListStack_push(st,(LS_DataType)ptr);
ptr = ptr ->_lchild;
}
//LOOP:
//栈空退出
if(ListStack_empty(st))// 栈空退出
break;
//2 出栈，出栈的时候就有情况了
ptr = (ListTreeNode *)ListStack_top(st);//先获取栈顶元素
ListStack_pop(st);//出栈
// 如果出栈元素的访问次数是1 说明它的右边还没有弄完，将它的右边弄完之后才能轮到它
//因此需要将它的访问次数 ++,然后将它入栈，转到这个入栈元素右边回到第1步
if(ptr ->_cnt == 1)
{
ptr ->_cnt++;
ListStack_push(st,(LS_DataType)ptr);
ptr = ptr ->_rchild;
}
else
{
//如果出栈元素的访问次数变成了2，说明它的左右两边全部弄完了，轮到它访问了 访问之
printf("=%c ",ptr ->_data);//访问它的时候说明左右孩子都弄完了 所有不能回到第1步
//而第一步的循环条件是 while(ptr) 我将ptr = null,第一步就过掉了
ptr = NULL;
//goto LOOP;//这也可以
}
}
printf("\n");
ListStack_destory(&st,NULL);
}
//树的层次遍历 利用队列 我们在层次遍历的时候可以确定辈分，并且我可以求得这个数的宽度
//问怎么求宽度？ 在一层里面最多元素的元素个数就是数的宽度
//返回树宽
int ListStack_LevelOrder(ListTreeNode *root)
{
if(!root)
return 0;
ArrayQueue * qu = ArrayQueue_init(100);
//1 将根节点入队
ArrayQueue_push(qu,(AQ_DataType)root);
int shangyibei = 1;//老祖宗有一个 就是根节点 这个n是确定这一辈里面有多少人
int xiayibei = 1;
int max = shangyibei;
int beifen = 1;
while(1)
{
shangyibei = xiayibei;//下一辈的人转成长辈
xiayibei = 0;//下一辈的人就变成0了
printf("第%d辈:",beifen);
for(int i = 0;i < shangyibei;i++)//为了将长辈这一波的人全部出去 为了确定它的下一辈有多少人 一个长辈确定两个孩子
{
//2 出队，将出队元素的左右孩子全部入队(左右需要存在才能入队)
ListTreeNode * ptr = (ListTreeNode * )ArrayQueue_front(qu);
ArrayQueue_pop(qu);
printf("%c ",ptr ->_data);
if(ptr ->_lchild)
{
xiayibei++;
ArrayQueue_push(qu,(AQ_DataType)ptr ->_lchild);
}
if(ptr ->_rchild)
{
xiayibei++;
ArrayQueue_push(qu,(AQ_DataType)ptr ->_rchild);
}
//循环第二步就可以了 队空退出
}
if(ArrayQueue_empty(qu))
break;
printf(" ");
beifen++;
if(xiayibei > max)//更新最大值
max = xiayibei;
}
printf("\n");
ArrayQueue_destory(&qu,NULL);
return max;
}