树是一种非线性的数据结构,它是由n(n >= 0)个有限结点组成的一个具有层次关系的集合,把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。
结点的度:到底有多少个链接的子节点
叶子结点或终端结点:度为0的结点称为叶子结点,
相对于线性表,树的结构就复杂很多了。最常用的表示方法——孩子兄弟表示法。
文件系统的目录树,
树在实际当中,不太作为存储数据这个角度去用,因为意义不是很大。
主要用的是二叉树
现实中的二叉树
这还是个满二叉树
与普通的树最大的不同是它最多只有两个子树。
在实际中普通二叉树的增删查改没得意义。
有意义的是搜索二叉树。
搜索二叉树:任何一棵树,左子树都比跟要小,右子树都比根要大。在搜索树中查找一个数,最多查找高度次。时间复杂度O(N)。
引申:左右两边的结点数量比较均匀。
接着引出 ——平衡树
学习普通二叉树可以为后面学习复杂的有用的平衡树做铺垫。
1.若规定根结点的层数为1,则一棵非空二叉树的第i层上最多有2^(i-1)个结点
2.若规定根节点的层数是1,则深度为h的二叉树的最大节点数是2^-1
3.对于任何一棵二叉树,如果度为0其叶结点个数为n0,度为2的分支结点个数为n2,则有n0 = n2 +1(度为2的结点个数总是比度为0的结点个数多1)
4.若规定根节点的层数是1,具有n个结点的满二叉树的深度是h = log2 N +1(以2为底N的对数+1)
顺序结构存储就是使用数组来存储,一般使用数组只适合表示完全二叉树,因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储。二叉树顺序存储在物理上是一个数组,在逻辑上是一颗二叉树。
二叉树的链式存储结构是指,用链表来表示一棵二叉树,即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成,数据域和左右指针域,左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。链式结构又分为二叉链和三叉链,当前我们学习中一般都是二叉链,后面到高阶数据结构如红黑树等会用到三叉链。
任何一个二叉树由三个部分构成
1.根节点——2.左子树——3.右子树
分治算法:分而治之,大问题分成子问题,子问题再分成子问题,直到无法分割
前序遍历:根左右—— (上图:A-B-D-NULL-NULL-E-NULL-NULL-C-NULL-NULL)
中序遍历:左根右—— (NULL-D-NULL-B-NULL-E-NULL-A-NULL-C-NULL)
后序遍历:左右根—— (NULL-NULL-D-NULL-NULL-E-B-NULL-NULL-C-A)
typedef char BinaryTreeType;
typedef struct BinaryTreeNode
{
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
BinaryTreeType data;
}BTNode;
void PrevOrder(BTNode* root)
{
//如果树是空树就直接return
if (root == NULL )
{
printf("NULL ");
return;
}
printf("%c ", root->data);
PrevOrder(root->left);
PrevOrder(root->right);
}
void InOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
InOrder(root->left);
printf("%c ",root->data);
InOrder(root->right);
}
void PostOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%c ", root->data);
}
//构建一个简单的树
BTNode* A = (BTNode*)malloc(sizeof(BTNode));
A->data = 'A';
A->left = NULL;
A->right = NULL;
BTNode* B = (BTNode*)malloc(sizeof(BTNode));
B->data = 'B';
B->left = NULL;
B->right = NULL;
BTNode* C = (BTNode*)malloc(sizeof(BTNode));
C->data = 'C';
C->left = NULL;
C->right = NULL;
BTNode* D = (BTNode*)malloc(sizeof(BTNode));
D->data = 'D';
D->left = NULL;
D->right = NULL;
BTNode* E = (BTNode*)malloc(sizeof(BTNode));
E->data = 'E';
E->left = NULL;
E->right = NULL;
BTNode* F = (BTNode*)malloc(sizeof(BTNode));
F->data = 'F';
F->left = NULL;
F->right = NULL;
A->left = B;
A->right = C;
B->left = D;
B->right = E;
PrevOrder(A);
printf("\n");
方法一:因为我们要对同一个size进行++,所以要设置一个全局变量size进行++就完事了。
int size = 0;
void TreeSize(BTNode* root)
{
if (root == NULL)
{
return;
}
else
{
size++;
}
TreeSize(root->left);
TreeSize(root->right);
}
但是在进行多次调用的时候因为累加,调用前要先将他置成0。
TreeSize(A);
printf("结点个数%d",size);
size = 0;
TreeSize(B);
printf("结点个数%d", size);
但是这种方法不是线程安全的。引出我们的第二种方法。
方法二:传参
int size = 0;
void TreeSize(BTNode* root,int* psize)
{
if (root == NULL)
{
return;
}
else
{
(*psize)++;
}
TreeSize(root->left, psize);
TreeSize(root->right, psize);
}
调用
int Asize = 0;
TreeSize(A,&Asize);
printf("结点个数%d",Asize);
size = 0;
int Bsize = 0;
TreeSize(B, &Bsize);
printf("结点个数%d", Bsize);
方法三
分治
int TreeSize(BTNode* root)
{
return root == NULL ? 0:TreeSize(root->left) + TreeSize(root->right) + 1;
}
调用
printf("%d", TreeSize(A));
图解
叶子结点没有子结点,叶子结点就是度为0的结点。
int TreeLeafSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
if (root->left == NULL && root->right == NULL)
{
return 1;
}
return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}
流程:判断是否为空,为空返回0,不为空看左右孩子是否都为空,为空返回1,如果上面两个条件都不满足,分别计算左右孩子…孩子的孩子…递归返回相应的根结点。
前序中序后序遍历其实也叫深度优先遍历。
层序遍历本质上也叫做广度优先遍历,以根为主一层一层往下遍历。
用队列先进先出的性质,
核心思路:上一层带下一层。
void LevelOrder(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root)//不为空进队
{
QueuePush(&q, root);
}
while (!QueueEmpty(&q))//队列不为空就继续
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
printf("%c ", front->data);
if (front->left)
{
QueuePush(&q, front->left);
if (front->right)
{
QueuePush(&q, front->right);
}
}
}
printf("\n");
QueueDestory(&q);
}
上面是队列
相关链接——【线性表】之队列_半生瓜のblog-CSDN博客
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
/// 队列
//前置声明
struct BinaryTreeNode;
typedef struct BinaryTreeNode* QueueDataType;//存二叉树的结点
typedef struct QueueNode
{
struct QueueNode* next;
QueueDataType data;
}QueueNode;
//单链表除了尾插还要尾删,所以不会加这个
typedef struct Queue
{
QueueNode* tail;
QueueNode* head;
}Queue;
//初始化
void QueueInit(Queue* pq)
{
assert(pq);
pq->tail = pq->head = NULL;
}
//销毁
void QueueDestory(Queue* pq)
{
assert(pq);
QueueNode* cur = pq->head;
while (cur)
{
QueueNode* curNext = cur->next;
free(cur);
cur = curNext;
}
pq->head = pq->tail = NULL;
}
//队尾入
void QueuePush(Queue* pq, QueueDataType x)
{
assert(pq);
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
if (newnode == NULL)
{
printf("malloc is fail\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
if (pq->tail == NULL)
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
}
//队头出
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->head);//队列是不等于空的
if (pq->head->next == NULL)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
//先保存一下下一个结点
QueueNode* nextNode = pq->head->next;
free(pq->head);
pq->head = nextNode;
}
}
//队头数据
QueueDataType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->head);
return pq->head->data;
}
//队尾数据
QueueDataType QueueBack(Queue* pq)
{
assert(pq);
assert(pq->head);
return pq->tail->data;
}
//是否为空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->head == NULL;
}
//返回数据个数
int QueueSize(Queue* pq)
{
assert(pq);
int size = 0;
QueueNode* cur = pq->head;
while (cur)
{
size++;
cur = cur->next;
}
return size;
}
/// //
typedef char BinaryTreeType;
typedef struct BinaryTreeNode
{
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
BinaryTreeType data;
}BTNode;
//二叉树不学习增删查改,因为没得意义
//前序遍历
void PrevOrder(BTNode* root)
{
//如果树是空树就直接return
if (root == NULL )
{
printf("NULL ");
return;
}
printf("%c ", root->data);
PrevOrder(root->left);
PrevOrder(root->right);
}
//中序遍历
void InOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
InOrder(root->left);
printf("%c ",root->data);
InOrder(root->right);
}
//后序遍历
void PostOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%c ", root->data);
}
//结点的个数
/*因为我们要对同一个size进行++,
所以要设置一个全局变量size进行++就完事了,
但是在进行多次调用的时候因为累加,调用前要先将他置成0*/
//int size = 0;
//void TreeSize(BTNode* root)
//{
// if (root == NULL)
// {
// return;
// }
// else
// {
// size++;
// }
// TreeSize(root->left);
// TreeSize(root->right);
//}
//传参
//int size = 0;
//void TreeSize(BTNode* root,int* psize)
//{
// if (root == NULL)
// {
// return;
// }
// else
// {
// (*psize)++;
// }
// TreeSize(root->left, psize);
// TreeSize(root->right, psize);
//}
int TreeSize(BTNode* root)
{
return root == NULL ? 0:TreeSize(root->left) + TreeSize(root->right) + 1;
}
//叶子结点的个数
int TreeLeafSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
if (root->left == NULL && root->right == NULL)
{
return 1;
}
return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}
//层序遍历
void LevelOrder(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root)//不为空进队
{
QueuePush(&q, root);
}
while (!QueueEmpty(&q))//队列不为空就继续
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
printf("%c ", front->data);
if (front->left)
{
QueuePush(&q, front->left);
if (front->right)
{
QueuePush(&q, front->right);
}
}
}
printf("\n");
QueueDestory(&q);
}
int main(void)
{
//构建一个简单的树
BTNode* A = (BTNode*)malloc(sizeof(BTNode));
A->data = 'A';
A->left = NULL;
A->right = NULL;
BTNode* B = (BTNode*)malloc(sizeof(BTNode));
B->data = 'B';
B->left = NULL;
B->right = NULL;
BTNode* C = (BTNode*)malloc(sizeof(BTNode));
C->data = 'C';
C->left = NULL;
C->right = NULL;
BTNode* D = (BTNode*)malloc(sizeof(BTNode));
D->data = 'D';
D->left = NULL;
D->right = NULL;
BTNode* E = (BTNode*)malloc(sizeof(BTNode));
E->data = 'E';
E->left = NULL;
E->right = NULL;
BTNode* F = (BTNode*)malloc(sizeof(BTNode));
F->data = 'F';
F->left = NULL;
F->right = NULL;
A->left = B;
A->right = C;
B->left = D;
B->right = E;
LevelOrder(A);
printf("\n");
return 0;
}