数据结构---循环队列---树的基本概念
目录
一、队列
1.1.队列
1.创建循环队列（顺序结构）
2.判断队满
3.判断队空
4.进队
5.出队
6.销毁
二、树
2.1.树的特点
2.2.基本概念
1.根节点
2.分支节点
3.叶节点
4.层
5.深度
6.高度
7.度
2.3.二叉树
1.特点
2.遍历方式
2.4.满二叉树
2.5.完全二叉树
三、总结
一、队列
1.1.队列
非循环队列，假设一直进队当队存满时，会出现假溢出显现，为了避免，故此有了循环队列；
循环队列，开始头和尾都指向同一个位置。在出队入队的过程中，head和tail都会再次回到最开始的位置。因此，head==tail时，队列为空；tail%len+1 == head时， 队列满。元素从队尾入队，tail = (tail+1) % len；元素从队头出队，head = （head+1）% len；
队列的元素个数，假设由最大容量为n，并预留一个空位置来判断满的标志，则队列元素为：（tail-head+n）% n；
1.创建循环队列（顺序结构）
SeqQueue *CreateSeqQueue(int MaxLen)
{
SeqQueue *pTmpQueue = NULL;
pTmpQueue = malloc(sizeof(SeqQueue));
if (NULL == pTmpQueue)
{
return NULL;
}
pTmpQueue->Head = pTmpQueue->Tail = 0;
pTmpQueue->Len = MaxLen;
pTmpQueue->pData = malloc(sizeof(DataType) * MaxLen);
if (NULL == pTmpQueue->pData)
{
return NULL;
}
return pTmpQueue;
}2.判断队满
int IsFullSeqQueue(SeqQueue *pTmpQueue)
{
return (pTmpQueue->Tail + 1) % pTmpQueue->Len == pTmpQueue->Head ? 1 : 0;
}3.判断队空
int IsEmptySeqQueue(SeqQueue *pTmpQueue)
{
return pTmpQueue->Head == pTmpQueue->Tail ? 1 : 0;
}4.进队
int EnterSeqQueue(SeqQueue *pTmpQueue, DataType TmpData)
{
if (IsFullSeqQueue(pTmpQueue))
{
return -1;
}
pTmpQueue->pData[pTmpQueue->Tail] = TmpData;
pTmpQueue->Tail = (pTmpQueue->Tail + 1) % pTmpQueue->Len;
return 0;
}5.出队
DataType QuitSeqQueue(SeqQueue *pTmpQueue)
{
DataType TmpData;
TmpData = pTmpQueue->pData[pTmpQueue->Head];
pTmpQueue->Head = (pTmpQueue->Head + 1) % pTmpQueue->Len;
return TmpData;
}6.销毁
int DestroySeqQueue(SeqQueue **ppTmpQueue)
{
free((*ppTmpQueue)->pData);
free(*ppTmpQueue);
*ppTmpQueue = NULL;
return 0;
}二、树
2.1.树的特点
只有一个前驱，但可以有很多后继；
2.2.基本概念
1.根节点
没有前驱；
2.分支节点
既有前驱又有后继；
3.叶节点
没有后继；
4.层
根节点为第一层，往后逐层+1；
5.深度
根节点到叶子节点的最大层数；
6.高度
从叶子节点到根节点经过的最大节点数；
7.度
节点后继的个数；
2.3.二叉树
1.特点
所有节点的度最大为2；
2.遍历方式
前序遍历、中序遍历、后序遍历、层次遍历
2.4.满二叉树
每一次节点达到最大个数；
2.5.完全二叉树
所有节点展开后，节点编号排列连续；
二叉树第k层最多有2^(k-1)个节点；
满二叉树有k层，则所有节点数为 2^k -1
三、总结
循环队列的循环思想很重要，也要知道为啥要使用循环队列，循环队列是如何实现循环的，如何判断队空，对满；树呢，二叉树是用的最多的，其中要分清满二叉树和完全二叉树；还有就是满二叉树中的节点个数的计算。