- 什么是树
- 树的相关概念
- 什么是二叉树
- 特殊的二叉树
- 二叉树的性质
- 链式二叉树
- 二叉树类型的创建
- 二叉树的遍历
- 前序遍历:
- 中序遍历:
- 后序遍历:
- 二叉树节点的个数
- 查找数据为X的节点
- 查找叶子节点的个数
- 第k层节点的个数
- 二叉树的高度
- 二叉树的层序遍历
- 判断二叉树是不是完全二叉树
什么是树
树的相关概念树是一种非线性结构。树有一个特殊的节点,叫做根节点。根节点是一个树的起点,除根节点外,它下面的节点被分为很多的分支。以每个分支节点为起点又可以构成一个树,称为子树。由根节点及子树构成的结构称为树
什么是二叉树节点的度:该节点直接相连了几个节点,就是几度。
叶子节点:度为0的节点
分支节点:度不为0的节点
父亲节点:该节点有连接下一层的节点 ,该节点即为父节点
子节点:父节点连的节点为子节点
兄弟节点:有共同父节点的节点,互称为兄弟节点。
树的度:节点中度最大的,就是树的度。
节点的层次:如果定义根节点为第 1层,那么根的子节点为第二层,依次类推。
树的的高度(深度):节点的最大层数为树的深度。
堂兄弟节点:处于同一层的节点。
节点的祖先:从根到该节点所经分支的全部节点。
子孙:以某节点为根的子树中任意一个节点都称为该节点的子孙
森林:多颗树构成的集合称为森林。
特殊的二叉树一个二叉树是节点的集合,该集合可以为空,也可以由根节点连接左右子树构成。
二叉树的特点:
1.每个节点的度最大为2。
2.二叉树有左右子树,因此是有序的,左右不能颠倒
二叉树的性质满二叉树:每一层的节点数都达到最大。
完全二叉树:除最后一层外,每一层的节点数都达到最大,且最后一层的节点都位于左部。
链式二叉树 二叉树类型的创建若根节点为第一层,那么二叉树的第i层最多有2(i-1)个节点,总节点数最多有2h-1。
对于任意一个二叉树,如果度为0的节点有n0,那么度为2的节点n2=n0-1。
对一个完全二叉树进行编号,编号的规则:自上而下,自左而右。
那么,第i个节点对应的左节点为2i+1,右节点为2i+2,对应的父节点为(i-1)/2。
typedef int BTDataType;
typedef struct BinaryTreeNode
{
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
BTDataType data;
}BTNode;
二叉树的遍历
前序遍历:
先访问根节点,再访问左子树,最后访问右子树;每个子树又可以分为根,左树,右树。不断的递归,直到每个子树的根为空。
void BinaryTreePrevOrder(BTNode* root)
{
if (root == NULL)
{
printf("# ");
return;
}
printf("%d ", root->data);
BinaryTreePrevOrder(root->left);
BinaryTreePrevOrder(root->right);
}
中序遍历:
先访问左子树,再访问根节点,最后访问右子树
void BinaryTreeInOrder(BTNode* root)
{
if (root == NULL)
{
printf("# ");
return;
}
BinaryTreeInOrder(root->left);
printf("%d ", root->data);
BinaryTreeInOrder(root->right);
}
后序遍历:
先访问右子树,再访问左子树,最后访问根节点
void BinaryTreePostOrder(BTNode* root)
{
if (root == NULL)
{
printf("# ");
return;
}
BinaryTreePostOrder(root->left);
BinaryTreePostOrder(root->right);
printf("%d ", root->data);
}
二叉树节点的个数
先访问根,不为空就加1,然后访问左右子树。为空就返回0
int BinaryTreeSize(BTNode* root)
{
if (root == NULL)
return 0;
else
return 1+ BinaryTreeSize(root->left)+ BinaryTreeSize(root->right);
}
查找数据为X的节点
先查找根节点,然后再分别查找左右子树,当为空的时候返回空,当节点的数据为x时,则返回该节点的地址。然后把左右子树按上面的方式继续查找。
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
return NULL;
if (root->data == x)
return root;
BTNode* ret1=BinaryTreeFind(root->left,x);
if (ret1)
return ret1;
BTNode* ret2 = BinaryTreeFind(root->right, x);
if (ret2)
return ret2;
return NULL;
}
查找叶子节点的个数
出度为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);
}
第k层节点的个数
我们把根看成第k层,那么实际上的第k层就是第一层。
如果节点为空就返回0,如果k为1就是到了第k层了,返回1。
上述是归的条件。递就是按这个逻辑继续查找左,右子树。
int BinaryTreeLevelKSize(BTNode* root, int k)
{
if (root == NULL)
return 0;
if (k == 1)
return 1;
return BinaryTreeLevelKSize(root->left, k - 1)+ BinaryTreeLevelKSize(root->right, k - 1);
}
二叉树的高度
要求树的高度就是求路径最大的。
我们可以先比较左右子树的高度,然后最大的子树的高度加1就是树的高度。这个就是不断递归的过程。
int TreeDepth(BTNode* root)
{
if (root == NULL)
return 0;
int ret1 = TreeDepth(root->left);
int ret2 = TreeDepth(root->right);
if (ret1 > ret2)
return ret1+1;
else
return ret2+1;
}
二叉树的层序遍历
用一个队列储存节点,当一个节点出队时,它的孩子节点入队。这样就实现了层序遍历。
void BinaryTreeLevelOrder(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root)
QueuePush(&q, root);
while (!QueueEmpty(&q))
{
BTNode* cur = QueueFront(&q);
QueuePop(&q);
if (cur == NULL)
printf("# ");
else
{
printf("%d ", cur->data);
QueuePush(&q, cur->left);
QueuePush(&q, cur->right);
}
}
QueueDestroy(&q);
printf("n");
}
判断二叉树是不是完全二叉树
按照层序遍历,如果是完全二叉树,当出队列的节点为空的时候,后面所有的节点都是空,反之不是完全二叉树。
bool BinaryTreeComplete(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root)
QueuePush(&q, root);
while (!QueueEmpty(&q))
{
BTNode* cur = QueueFront(&q);
QueuePop(&q);
if (cur == NULL)
break;
else
{
QueuePush(&q, cur->left);
QueuePush(&q, cur->right);
}
}
while (!QueueEmpty(&q))
{
BTNode* cur = QueueFront(&q);
QueuePop(&q);
if (cur != NULL)
{
QueueDestroy(&q);
return false;
}
}
QueueDestroy(&q);
return true;
}



