文章目录
- 一.什么是树
- 二.什么是二叉树
- 三.二叉树的访问次序
- 四.特殊的二叉树
- 五.求结点个数
- 六.平衡二叉树
- 总结
一.什么是树
树是由一个集合以及在该集合上定义的一种关系构成的。 集合中的元素称为树的节点,所定义的关系称为父子关系。 父子关系在树的节点之间建立了一个层次结构。 在这种层次结构中有一个节点具有特殊的地位,这个节点称为该树的根节点,或称为树根。
结点
结点是数据结构中的基础,是构成复杂数据结构的基本组成单位。
结点的度
结点拥有的子树数目称为结点的度。
二.什么是二叉树
二叉树是
n(n>=0)
个结点的有限集合,该集合或者为空集(称为空二叉树),或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成。
特点
1.每一个节点最多有两棵子数,及二叉树不存在度大于二的节点
2.二叉树的子树有左右之分,其子树的次序不能够颠倒
3.任何一个二叉树都有三部分,根节点左子树右子树
结构
typedef int BTDataType;
typedef struct Binary TreeNode
{
struct Binary TreeNode* left;//左孩子
struct Binary TreeNode* right;//右孩子
BTDataType data;//数据
}BTNode;
三.二叉树的访问次序
3.1前序遍历 (根结点 > 左子树 > 右子树)
主要是利用了函数递归的方法去遍历,先根节点左子树右子树不断地去调用自己
void PreOrder(BTNode* root)
{
if (root == NULL)
return;
printf("%d", root->data);//根
PreOrder(root->left);//左子树
PreOrder(root->right);//右子树
}
3.2中序遍历和后序遍历
void MidOrder(BTNode* root)
{
if (root == NULL)
return;
MidOrder(root->left);//左子树
printf("%d", root->data);//根
MidOrder(root->right);//右子树
}
void afterOrder(BTNode* root)
{
if (root == NULL)
return;
afterOrder(root->left);//左子树
afterOrder(root->right);//右子树
printf("%d", root->data);//根
}
3.3层序遍历
前中后序遍历其实也叫深度优化遍历,序遍历叫广度优化遍历
我们利用队列来实现层序遍历
核心思路:上一层带下一层的
先创造一个队列,如果跟节点不为空的话,把根节点放入这个队列中,循环的判断条件被列中没有元素就停下来,有元素就继续去队列投元素,放入树的头,然后再删去队列这个元素,然后把删去元素所对应的左子树和右子树放入,一层一层的遍历
void LeveOrder(BTNode* root)
{
//创建队列
Queue q;
Queue Init(&q);
//如果根节点不为空,在队列里放入
if (root != NULL)
{
QueuePush(&q, root);
}
while (!QueueEmpty(&q))
{
//删去元素所对应的左子树和右子树放入一层一层的遍历
BTNode* front = QueueFront(&q);
QueuePop(&q);
printf("%c", front->data);
if (front->left != NULL)
{
QueuePush(&q, front->left);
}
if (front->right != NULL)
{
QueuePush(&q, front->right);
}
}
printf("\n");
QueueDestory(&q);
}
四.特殊的二叉树
4.1满二叉树
假设一个满二叉树的高为h,则它的总结点个数为N,则高为2^0+2^1+....+2^(h-1)=N,h=log2(N+1)
4.2完全二叉树
特征:1.前n-1层是满的。2.最后一层不满,但最后一层从左往右都是连续的
特别公式:对于任何一颗二叉树,如果度为零的叶子节点个数为n0,度为二的分支节点个数为n2则n0=n2+1。
例:存在一个2n个结点的完全二叉树,则它的叶子结点大小的个数为__
完全二叉树度为1的结点个数要么是1个,要么没有。设度为0的结点为x0,度为1的为x1,度为二的为x2,所以说套入两个公式,x0+x1+x2=2n,x0=x2+1.可以算出2x0+x1-1=2n,又因为完全二叉树所以x1为0或者1,带入可得n或者2n+1/2
五.求结点个数
其实二叉树还有一个平衡结构,叫做平衡二叉树,需要非常灵活的掌握函数递归和分治的思想,所以我们先来利用递归和分治思想来求一下结点
5.1求叶子结点的个数
利用递归和分治的思想
int TreeLeafsize(BTNode* root)
{
if (root == NULL)
return 0;
//如果左子树和右子树都为空说明找到了一个叶子结点,返回1
if (root->left == NULL && root->right == NULL)
return 1;
//利用函数递归的思路,先左子树在右
return TreeLeafsize(root->left) + TreeLeafsize(root->right);
}
5.2求总结点个数
void Treesize(BTNode* root, int* psize)
{
if (root == NULL)
{
return;
}
//是结点就加加
else
{
(*psize++);
}
//也是递归,分治先左子树在右子树
Treesize(root->left,psize);
Treesize(root->right,psize);
}
六.平衡二叉树
定义:平衡二叉树也叫AVL树,它或者是一颗空树,或者具有以下性质的二叉排序树:它的左子树和左子树的高度之差(平衡因子)的绝对值不超过1,且它的左子树和右子树都是一颗平衡二叉树。
6.1二叉树的深度
分治思路:如果为空高度直接为零,非空就分解子问题,先求左右指数的深度,我的深度等于左右,质数深度大的大小,加1。
int maxDepth(BTNode* root)
{
if (root == NULL)
return 0;
int leftDepth = maxDepth(root->left);
int rightDepth= maxDepth(root->right);
//左边的深度如果大于右边的话,就加1反之右边加1
return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
6.2平衡树的判断
bool isBalaned(BTNode* root)
{
//第一种情况,如果为空的话就是的
if (root == NULL)
return true;
//利用深度函数来求出左右子树的深度
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
//利用递归判断高度差的绝对值不超过1,左右都要是平衡二叉(递归)
return abs(leftDepth - rightDepth) < 2 && isBalaned(root->left) && isBalaned(root->right);
}
总结
这只是初次学习二叉树,它的内容可不只有这些,还要深度的还需要不断的学习积累才可实现