目录
树与二叉树
1.树的定义
树是n（n>=0）个结点构成的有限集合。
·当n=0时，称为空树
·树中有一个特殊的结点被称作“根（root）”，其余结点可以分为m个不相交的有限集，其中每一个 集合都是一颗树，被称为原来树的子树。（对于空树来说）
2.树的有关术语
（1）结点：树中独立的单元格，包含一个数据元素及若干指向子树的分支。
（2）结点的度：结点的子树个数
（3）树的度：树中最大的结点的度，上图树的度为3.
（4）叶子结点：树中度为0的节点，叶子是这一类结点的总称。上图中的E、F、G、D都是叶子节点。
（5）双亲结点：有子树的结点，是其子树的双亲结点。上图的A就是B、C、D的双亲结点
（6）子结点：上图B、C、D是A的子结点
（7）兄弟结点：上图B、C、D互为兄弟结点
（8）结点的层次：根结点在1层，其他结点的层次等于其父节点的层次+1
(9) 树的深度：所有结点中最大的层次就是树的深度
（10）森林：m棵不相交的树的集合
3.二叉树（BinaryTree）
二叉树是特殊的树，该树每个结点的度<=2。
二叉树的性质：
1.二叉树在第k层上最多有2^(k-1）个结点
2.深度为k的二叉树最多有2^k-1个结点
3.一颗二叉树如果度为0的结点有N0个，度为2的结点有N2个，则N0=N2+1
特殊的二叉树
·满二叉树：
深度为k且一共有2^k-1个结点，第i层的节点树为2^(i-1)
·完全二叉树
深度为k，前k-1层每层都是满结点，最后退成结点从左向右连续排列
二叉树的存储结构
顺序存储结构
用数组存储二叉树，按从上到下，从左到右顺序存储。（比较适合满二叉树和完全二叉树）
对于普通的二叉树，存储起来空元素的结点就会导致空间的浪费
链式存储结构
这里最常用的存储类型就是运用两指针
1.两指针分别是左右孩子
2.两指针分别是左孩子和右兄弟
二叉树以及对应接口的实现
1.二叉树架构搭建
typedef char BTDataType;//利于适用于多种类型的数据操作
typedef struct BinaryTree
{
BTDataType val;
struct BinaryTree*left;
struct BinaryTree*right;//左右孩子指针
}BTNode;
2.二叉树的创建
BTNode* BTbyNode(BTDataType x)
{
BTNode*newnode=(BTNode*)malloc(sizeof(BTNode));
if(newnode==NULL)
{
perror("malloc fail!!!");
return NULL;
}
newnode->val=x;
newnode->left=NULL;
newnode->right=NULL;
return newnode;
}
BTNode* CreateTree()
{
BTNode* l1 = BTByNode(1);
BTNode* l2 = BTByNode(2);
BTNode* l3 = BTByNode(3);
BTNode* l4 = BTByNode(4);
BTNode* l5 = BTByNode(5);l1->left = l4;
l1->right = l2;
l2->left = l3;
l4->right = l5;return l1;
}
3.二叉树的销毁
void TreeDestroy(BTNode*root)
{
if(root==NULL)
return ;
TreeDestroy(root->left);
TreeDestroy(root->right);
free(root);
//root==NULL//这里是局部变量，在函数内部置空没有用，要在调用销毁函数的下面置空root
}
4.二叉树的前中后序
关于二叉树非常重要的一个思想就是分治思想，将大问题转化成多个小问题去解决。换成二叉树也就是，将根节点问题不断转化给左右子树
void PrevOrder(BTNode*root)//前序----根---左---右
{
if(root==NULL)
return ；
printf("%c ",root->val);
PrevOrder(root->left);
PrevOrder(root->right);
}
void InOrder(BTNode*root)//中序----左---根---右
{
if(root==NULL)
return ;
InOrder(root->left);
printf("%c ",root->val);
InOrder(root->right);
}
void PostOrder(BTNode*root)//后序----左---右---根
{
if(root==NULL)
return ;
PostOrder(root->left);
PostOrder(root->right);
printf("%c ",root->val);
}
5.求树的节点个数
int BinaryTreeSize(BTNode* root)
{
return root==NULL?0:BinaryTreeSize(root->left)
+BinaryTreeSize(root->right)+1;
}
6.求叶子结点个数(无左右孩子，度为0)
int BinaryTreeleafSize(BTNode* root)
{
if(root==NULL)
return 0;
if(root->left==NULL&&root->right==NULL)
return 1；
return BinaryTreeleafSize（root->left）+BinaryTreeleafSize(root->right);
}
7.求树的深度
int BinaryTreeHeight(BTNode* root)
{
if(root==NULL)
return 0;
int h1=BinaryTreeHeight(root->left);
int h2=BinaryTreeHeight(root->right);
return h1>h2?h1:h2;
}
8.二叉树的层序遍历
顾名思义就是一层一层从左到右遍历
用一个队列来实现当一个根节点出队列，就将它的左右结点入队列，直到队列中无元素
void TreeLevelOrder(BTNode* root)
{
Queue q;//创建一个队列对象
QueueInit(&q);//队列初始化
if(root)
QueuePush(&q,root);//将根结点指针入队列
while(!QueueEmpty(&q))//判断队列是否为空，为空说明遍历结束
{
BTNode*front=QueueFront(&q);//取队首元素,防止下面出队首元素找不到根结点位置
QueuePop(&q);//将队首元素出队列
if(front)
{
printf("%c ",front->val);
QueuePush(&q,front->left);
QueuePush(&q,front->right);//将左右孩子入队列
}
}
TreeDestroy(root);
root==NULL;
}
拓展知识
知道一个树的结点数量，怎么算出该树的可能有几种情况
我们定义f(n)表示结点数为n的二叉树的情况数
零个结点也是一种情况，所以f(0)=1;
一个结点时，只有一种情况，则f(1)=1;
两个结点时，有两种情况，根结点一个，剩下结点左右孩子各一种情况，则f(2)=f(1)+f(1)=2;
三个结点时，根节点一个节点，剩下结点分为三种情形：
1.左子树两个结点右子树零个
2.右子树两个结点左子树零个
3.左右子树各一个节点
则f(3)=f(2)*f(0)+f(1)*f(1)+f(0)*f(2)
经过推算得到f(n)=f(n-1)*f(0)+f(n-2)*f(1)+…+f(0)*f(n-1)
上述式子可以化简成（2n)! / ( n! (n+1)! )在数学中被称为卡特兰数
有了上述式子知道结点数就能轻松算出树可能存在的情况数
