二叉树
什么是树
树是一种非线性结构。树有一个特殊的节点，叫做根节点。根节点是一个树的起点，除根节点外，它下面的节点被分为很多的分支。以每个分支节点为起点又可以构成一个树，称为子树。由根节点及子树构成的结构称为树
树的相关概念
节点的度：该节点直接相连了几个节点，就是几度。 叶子节点：度为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。
链式二叉树
二叉树类型的创建
ctypedef int BTDataType;
typedef struct BinaryTreeNode
{
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
BTDataType data;
}BTNode;二叉树的遍历
前序遍历：
先访问根节点，再访问左子树，最后访问右子树；每个子树又可以分为根，左树，右树。不断的递归，直到每个子树的根为空。
cvoid BinaryTreePrevOrder(BTNode* root)
{
if (root == NULL)
{
printf("# ");
return;
}
printf("%d ", root->data);
BinaryTreePrevOrder(root->left);
BinaryTreePrevOrder(root->right);
}中序遍历：
先访问左子树，再访问根节点，最后访问右子树
cvoid BinaryTreeInOrder(BTNode* root)
{
if (root == NULL)
{
printf("# ");
return;
}
BinaryTreeInOrder(root->left);
printf("%d ", root->data);
BinaryTreeInOrder(root->right);
}后序遍历：
先访问右子树，再访问左子树，最后访问根节点
cvoid BinaryTreePostOrder(BTNode* root)
{
if (root == NULL)
{
printf("# ");
return;
}
BinaryTreePostOrder(root->left);
BinaryTreePostOrder(root->right);
printf("%d ", root->data);
}二叉树节点的个数
先访问根，不为空就加1，然后访问左右子树。为空就返回0
cint BinaryTreeSize(BTNode* root)
{
if (root == NULL)
return 0;
else
return 1+ BinaryTreeSize(root->left)+ BinaryTreeSize(root->right);
}查找数据为X的节点
先查找根节点，然后再分别查找左右子树，当为空的时候返回空，当节点的数据为x时，则返回该节点的地址。然后把左右子树按上面的方式继续查找。
cBTNode* 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的节点为叶子节点，那我们就查找左右孩子为空的节点。
cint 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。 上述是归的条件。递就是按这个逻辑继续查找左，右子树。
cint 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就是树的高度。这个就是不断递归的过程。
cint 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;
}二叉树的层序遍历
用一个队列储存节点，当一个节点出队时，它的孩子节点入队。这样就实现了层序遍历。
cvoid 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");
}判断二叉树是不是完全二叉树
按照层序遍历，如果是完全二叉树，当出队列的节点为空的时候，后面所有的节点都是空，反之不是完全二叉树。
cbool 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;
}腾讯云开发者
