@TOC

一、二叉树

1. 概念

一颗二叉树是结点的有限集合，该集合或者为空，或者由一个根节点加上两棵别称为左子树和右子树的二叉树的组成

2.特点

每个结点最多有两棵子树，即二叉树不存在大于2的结点

二叉树的子树有左右之分其子树次序不能颠倒

3.特殊二叉树

1.满二叉树

一个二叉树，如果每一个层的结点都达到最大值，则这个二叉树就是满二叉树，也就是说如果一个二叉树的层数为k,结点总数为(2^k)-1，则就为满二叉树

在这里插入图片描述  

2.完全二叉树

对于深度为k的，有n个结点的二叉树，且仅当其每一个结点与深度为k的满二叉树中编号从1到n的结点，称为完全二叉树

在这里插入图片描述  

4.性质

性质1.

若规定根节点的层数为1，则一颗非空二叉树的第i层上最多有2^(i-1)个结点

  在这里插入图片描述  

性质2.

若规定根节点的层数为1，则深度为h的二叉树的最大结点数是(2^h)-1

在这里插入图片描述  

性质3.

对于任何一颗二叉树，如果度为0其叶结点个数为n0,度为2的分支节点个数为n2,则n0=n2+1

(有几个子树 ，度就为多少)

在这里插入图片描述

性质4.

若规定根节点的层数为1，具有n个结点的满二叉树的深度h=log N

2^h -1=N

2^h=N+1

h= log 2  N+1

但是由于大O渐进表示法的省略 ，时间复杂度化成 O(log N)

不太懂大O渐进表示法的 :时间复杂度与空间复杂度

二、二叉树整体实现

1.前序的实现

void  prevorder(BTnode* root)//前序  根 左子树 右子树
{
    if (root == NULL)
    {
        printf("NULL ");
        return;
    }
    printf("%c ", root->data);
    prevorder(root->left);
    prevorder(root->right);
}

递归展开图

在这里插入图片描述

2.中序的实现

void  inorder(BTnode* root)//中序 左子树 根 右子树
{
    if (root == NULL)
    {
        printf("NULL ");
        return;
    }
    inorder(root->left);
    printf("%c ", root->data);
    inorder(root->right);
}

递归展开图

在这里插入图片描述

3.后序的实现

void  postorder(BTnode* root)//后序 左子树 右子树 根
{
    if (root == NULL)
    {
        printf("NULL ");
        return;
    }
    postorder(root->left);
    postorder(root->right);
    printf("%c ", root->data);
}

递归展开图

在这里插入图片描述

4. 节点个数

int treesize(BTnode* root)//节点个数
{
    if (root == NULL)
    {
        return 0;
    }
    return treesize(root->left) + treesize(root->right) + 1;
}

递归展开图

在这里插入图片描述

5. 叶节点个数

int treeleafsize(BTnode* root)//叶子节点的个数
{
    if (root == NULL)
    {
        return 0;
    }
    if (root->left == NULL && root->right == NULL)//只有当左右子树都为NULL时才会返回1
    {
        return  1;
    }
     return treeleafsize(root->left)+ treeleafsize(root->right);
}

递归展开图

在这里插入图片描述

6.层序遍历

void levelorder(BTnode* root)//层序遍历 需要借助数据结构栈来实现
{
    queue q;
    queueinit(&q);//初始化栈
    if (root)
    {
        queuepush(&q, root);//将根结点入栈
    }
    while (!queueempty(&q))
    {
         datatype 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);//判断此时该结点的右子树是否为空 若不空则入栈
         }
    }
    queuedestroy(&q);//销毁内存
}

在这里插入图片描述