当前位置:   article > 正文

【数据结构】树和二叉树的定义 |二叉树的基本特点和性质 |存储与遍历 |递归

【数据结构】树和二叉树的定义 |二叉树的基本特点和性质 |存储与遍历 |递归

专栏文章:数据结构学习笔记
作者主页:格乐斯

前言

树和二叉树的定义
二叉树的基本特点和性质
二叉树的存储与遍历

树的定义

  1. 树是n(n>=0)个结点的有限集合;

    若n=0,称为空树;

    若n>0,称为非空树,非空树有且仅有一个结点被称为根;

  2. 除根结点以外的结点可分为m(m>0)个互不相交的有限集,其中每个集合本身也是一棵树,称为根的子树。

  3. 树的定义也涉及到树,某种程度上这体现了递归的思想;实际上对树进行遍历也使用了递归算法

树的基本术语

  • 根结点:非空树中无前驱结点的结点
  • 结点的度:结点拥有的子树数量
  • 非终端结点或分支结点:度不等于0
  • 叶子或终端结点:度等于0
  • 兄弟结点:前驱结点为同一结点的结点
  • 堂兄弟结点:在同一层的结点
  • 双亲结点:孩子结点的前驱结点
  • 孩子结点:双亲结点的后继结点
  • 树的度:各结点的度的最大值
  • 树的深度:树中结点的最大层次
  • 有序树:结点各子树从左至右有序,不能互换(左优先)
  • 无序树:结点各子树可互换位置
  • 森林:n棵互不相交的树的集合;树是只有一棵树的森林;森林不一定是树

二叉树的定义

二叉树是特殊的树,对于非空二叉树:除根结点以外的结点分为两个互不相交子集,分别称为左子树和右子树,而它们本身又是二叉树

简而言之,二叉树的结点最多只能有两个子树

二叉树基本特点

  • 结点的度不超过2
  • 有序树

完全二叉树

只有最后一层的结点有可能不满,且结点全部集中在左边

满二叉树

深度为k,且有(2^k) -1个结点的二叉树;

特点:每层结点都满;叶子结点全部在最底层;每一结点位置都有元素;满二叉树是完全二叉树的特例

二叉树性质

性质1

二叉树的第i层上至多有2^(i-1)个结点(i>=1)

**证明:**假设该二叉树是满二叉树

第一层只有1个结点,也就是根结点:2^(1-1)=1

第二层有2个结点:2^(2-1)=2

第三层有4个结点:2^(3-1)=4

根据归纳法可得:第i层有2^(i-1)个结点

性质2

深度为k的二叉树至多有(2^k) -1个结点(k>=1)

证明:对性质1的公式进行等比数列求和可得结果

性质3

对于任何一棵二叉树,假设终端结点(度为0)数为n0,度为1的结点数为n1,度为2的结点数为n2,则n0=n2-1

证明:总结点数 n=n1+n2+n0 ;

n1下接一条边,n2下接两条边, 则2*n2+n1=n-1;

两式相减得n0-n2=1

性质4

具有n个结点的完全二叉树深度为[log2(n+1)] 或 [log2n]+1 (中括号[ ] 意为向下取整)

证明:完全二叉树的结点数n一定少于等于相同深度的满二叉树的结点数(2^k) -1,即n<=(2^k) -1,可得k=[log2(n+1)]

性质5

对于一个有n个结点的完全二叉树,从上至下、从左至右对结点进行编号,则编号为i的结点,有以下几种情况:

1、若2i>n,则结点i为叶子结点,无左孩子;否则左孩子结点为2i

2、若2i+1>n,则结点i无右孩子;否则右孩子结点为2i+1

3、若i=1,则结点i为二叉树的根结点,无双亲;若

i>1,则双亲为 [i/2] (结果向下取整)

二叉树的存储与遍历

二叉树的存储

二叉树的顺序存储

按满二叉树的结点层次编号,依次存放二叉树中的数据元素;一般使用数组存储数据元素。

在这里插入图片描述

typedef struct
{
    TElemType *data;
    int length;
    int NumberofNodes;
}BiTree;
BiTree BT;

bool InitBinaryTree(BiTree &BT)
{
    BT.numberofnodes=8;
    BT.data=new TElemType[NumberofNodes];
    if(!BT) return false;
    BT.length=0;
    return true;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

特点:

结点间关系蕴含在其存储位置中

缺点是存储普通二叉树浪费空间,尤其是单支树;非常适用于存储满二叉树和完全二叉树,两者空间利用率都是百分百

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述


二叉树的链式存储

  1. 二叉链表
    在这里插入图片描述

    typedef struct BiNode
    {
        TElemType data;
        struct BiNode *left,*right;  //左孩子和右孩子指针    
    }BiNode,*BiTree;
    
    • 1
    • 2
    • 3
    • 4
    • 5
  2. 三叉链表

    在这里插入图片描述

    typedef struct TriNode
    {
        TElemType data;
        struct TriNode *left,*right,*parent;
    }TriNode,*TriTree;
    
    • 1
    • 2
    • 3
    • 4
    • 5

二叉树的遍历

遍历(Traversal),是指沿着某条搜索,依次对树(或图)中每个结点均做一次访问。

遍历是二叉树插入、删除、修改、查找和排序操作的前提、基础和核心。

二叉树的遍历方式分为三种

  • DLR 先序遍历,即先根再左再右
  • LDR 中序遍历,即先左再根再右
  • LRD 后序遍历,即左根再右再根

tips:先中后都指的是根节点在遍历中的位置

在这里插入图片描述

如上图二叉树,三种遍历方式的路径:

先序:A->B->D->C->E->G->F

中序:D->B->A->E->G->C->F

后序:D->B->G->E->F->C->A


遍历算法的实现

  1. 先序遍历每个结点并打印以当前结点为根结点的二叉树
//先序遍历
bool PreOrderTraverse(BiTree T)
{
    if(T==NULL) return true;  //遍历到空结点终止递进,开始回归
    print(T);  //打印以T为根结点的二叉树
    PreOrderTraverse(T->left);   //左子树递归
    PreOrderTraverse(T->right);  //右子树递归
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

二叉树递归灵魂三问:

  • 找到整个递归的终止条件,递归在什么时候结束?
  • 求返回值,应该给上一级返回什么信息?
  • 本级递归应该做什么?

  1. 求出二叉树的最大深度
int deepth(TreeNode *root)
{
    if(root==NULL) return 0;  //空结点终止递进
    int left=deepth(root->left);  //遍历左子树并求其深度
    int right=deepth(root->right);//遍历右子树并求其深度
    return 1+Max(left,right); //返回本级二叉树的深度
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

  1. 二叉树叶子结点的个数
int LeadCount(BiTree T)
{
    //空树返回0
    if(T==NULL) return 0;
    //叶子结点返回1
    if(T->left==NULL && T->right==NULL) return 1;
    //否则返回本级二叉树的叶子结点个数
    return LeadCount(T->left) s+ LeadCount(T=>right);
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

总结

本文主要介绍了以下几点:

  • 树和二叉树的定义
  • 二叉树的基本特点和性质
  • 二叉树的存储与遍历

文章到这结束啦,感谢阅读~

如果文章的论述或代码等出现错误,欢迎前来指正!

如果你觉得文章写的还不错,记得点赞收藏评论三连~ ❤

img

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/盐析白兔/article/detail/600893
推荐阅读
相关标签
  

闽ICP备14008679号