数据结构与算法-二叉树性质

x
用微信扫描二维码
分享至好友和朋友圈

  链表通常可以提供比数组更大的灵活性,但是由于链表是线性结构,所以很难使用它们来组织对象的分层结构。虽然栈和队列反映了某些层次,但它们是一维的。为了避免这种限制,我们来探究一种新的数据结构,称为树,树由节点和弧组成。

  就像这样:

  

   图1-1

  与自然界的树不同,数据结构中的树是倒过来的:根在顶部,叶子(末端节点)在底部。根是一个没有父节点只有子节点的节点,而叶节点没有子节点或者子节点是空结构。一颗树中非叶子节点我们称之为非终端节点,包括根节点。

  每个节点都可以从根节点经一个唯一的弧序列到达,此弧序列被称之为路径,路径中弧的数量称之为路径的长度。节点的层次是从根节点到该节点的路径的长度加1,也就是该路径上节点的数量。树的高度(深度)是树中节点的最大层次。空结构是空树,所以空树高度为0。只有一个根节点的树的高度是1,而且该树比较特殊,它是“节点既是根也是叶子”的唯一情况。在一棵树中,如果某个节点拥有n个子节点,那么我们称该节点的度为n。树在极端情况下可以退化为链表,这种树的高度为唯一叶节点的层次。

  就像这样:

  

   图1-2

  什么是二叉树呢?上面说的都是树的概念,节点下面可以有多个子节点,而二叉树对此做了限制。二叉树是节点可以包含最多两个子节点的树,每一个子节点都区分左子节点或右子节点。例如图1-1中13和23节点分别是根节点的左右子节点。我们进一步对二叉树进行划分:

  完美二叉树

  在一棵二叉树中,如果每个非终端节点都有两个子节点,并且所有叶子节点位于同一层次,那么称之为完美二叉树。

  就像这样:

  

   图1-3

  其中非终端节点包括15/13/23,它们都有两个子节点,并且所有叶子节点都位于第3层。可以看到,完美二叉树左右子树是完美对称的。对于完美二叉树,有以下特性:

  1、第i+1层的节点数为2^i

  2、如果完美二叉树高度为n,那么总的节点数为2^n - 1

  3、如果完美二叉树中叶子节点为m,非终端节点为k,那么m=k+1

  4、如果完美二叉树中某节点下标为n,那么它的左节点下标为2n+1,右节点下标为2n+2

  证明:

  1、性质1可以用数学归纳法来证明,假设完美二叉树中第i层节点数为2^(i-1),我们只要推导出第i+1层节点数为2^i即可。从定义出发,已知第i层的节点都有两个左右子节点,那么第i+1层的节点数为(2^(i-1))*2,也就是2^i,证明完毕

  2、性质2由性质1衍生出来,对于高度为n的完美二叉树,节点总数为2^0+2^1+......+2^(n-1),也就是2^n - 1,证明完毕

  3、性质3也是由数学归纳法证明的,假设高度为n的完美二叉树中非终端节点数为k,叶子节点为m,并且m=k+1,只要推导出高度为n+1的完美二叉树也符合这种情况即可。假设该树非终端节点数为k1,叶子节点数为m1,可以计算出k1=k+m,m1=2*m,那么m1-k1=2*m-(k+m)=m-k=1,即m1=k1+1,证明完毕

  4、性质4的证明比较麻烦,假设完美二叉树第n层存在一个节点下标为i,那么第n层剩余节点个数(包括i节点)为(2^n-1)-i,即2^n-i-1,我们记为k,假设i节点左节点下标为j,那么在第n+1层中j节点之前(不包括j节点)节点数为2^(n+1-1)-2*k=2^n-2*k,我们记为m,那么j-i=m+k=2^n-2*k+k=2^n-k=2^n-(2^n-i-1)=i+1,即j-i=i+1,那么j=2i+1,证明完毕

  完全二叉树

  对于高度为K的,有n个结点的二叉树,当且仅当其每一个结点都与高度为K的完美二叉树中编号从0至n-1的结点一一对应时称之为完全二叉树.

  完满二叉树

  在一棵二叉树中,只存在度为0或者2的节点,称该树为完满二叉树

  我们知道,在二叉树中只存在度为0或1或2的节点,记为n0,n1,n2,那么二叉树中节点总数n可以记为n=n0+n1+n2。在所有二叉树中存在一个重要的性质:n0=n2+1。该性质可以用数学归纳法证明,假设在一棵二叉树p中,度为2的节点个数为n2,那么n0=n2+1,我们只要证明在度为2的节点个数为n2+1的二叉树q中,该性质不变即可。想象在二叉树p中,我们为某个叶子节点添加左右节点,那么该二叉树变为q,并且度为2的节点个数增加了1,而叶子节点也增加了1,n0依然比n2大1。想象在二叉树p中,为某个度为1的节点添加一个子节点,那么该二叉树变为q,并且度为2的节点个数增加了1,而叶子节点也增加了1,n0依然比n2大1。证明完毕

  到目前为止,我们已经了解完美二叉树、完全二叉树、完满二叉树,对于完美二叉树有4个性质,而完全二叉树、完满二叉树有1个。也许有同学会觉得二叉树还有其他性质,事实上,其他性质完全可以用以上性质直接或间接推导出来,性质记得越少越不容易忘记。

  二叉树不是停留在学术上的数据结构,我们是要在程序中实现二叉树,并且运用它的性质来满足软件开发需求。第一步,我们首先要遍历二叉树,能够遍历才能对节点进行操作。遍历二叉树的方法在下一篇进行探讨。

  数据结构与算法-栈与队列

特别声明:本文为网易自媒体平台“网易号”作者上传并发布,仅代表该作者观点。网易仅提供信息发布平台。

跟贴 跟贴 1 参与 5
© 1997-2019 网易公司版权所有 About NetEase | 公司简介 | 联系方法 | 招聘信息 | 客户服务 | 隐私政策 | 广告服务 | 网站地图 | 意见反馈 | 不良信息举报

软件开发快速学习

学习软件开发必备技能

头像

软件开发快速学习

学习软件开发必备技能

4

篇文章

48

人关注

列表加载中...
请登录后再关注
x

用户登录

网易通行证/邮箱用户可以直接登录:
忘记密码