提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  后端

当前栏目

二叉树的详细实现(含递归展开图)

二叉树递归 实现 详细 展开
2023-06-13 09:14:59 时间

一、二叉树

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);//销毁内存
}

相关文章