二叉树的性质
二叉树的性质
fengsehng 发表于2年前
二叉树的性质
  • 发表于 2年前
  • 阅读 1
  • 收藏 0
  • 点赞 0
  • 评论 0

移动开发云端新模式探索实践 >>>   

二叉树概述

在计算机科学中,二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。

性质概述

二叉树的每个结点至多只有二棵子树(不存在度大于2的结点),二叉树的子树有左右之分,次序不能颠倒。二叉树的第i层至多有2^{i-1}个结点;深度为k的二叉树至多有2^k-1个结点;对任何一棵二叉树T,如果其终端结点数为n_0,度为2的结点数为n_2,则n_0=n_2+1。

一棵深度为k,且有2^k-1个节点称之为满二叉树;深度为k,有n个节点的二叉树,当且仅当其每一个节点都与深度为k的满二叉树中,序号为1至n的节点对应时,称之为完全二叉树。

性质列举

(1) 在非空二叉树中,第i层的结点总数不超过 , i>=1;

(2) 深度为h的二叉树最多有 个结点(h>=1),最少有h个结点;

(3) 对于任意一棵二叉树,如果其叶结点数为N0,而度数为2的结点总数为N2,则N0=N2+1;

(4) 具有n个结点的完全二叉树的深度为

(5)有N个结点的完全二叉树各结点如果用顺序方式存储,则结点之间有如下关系:
若I为结点编号则 如果I>1,则其父结点的编号为I/2;
如果2*I<=N,则其左儿子(即左子树的根结点)的编号为2*I;若2*I>N,则无左儿子;
如果2*I+1<=N,则其右儿子的结点编号为2*I+1;若2*I+1>N,则无右儿子。

(6)给定N个节点,能构成h(N)种不同的二叉树。
h(N)为卡特兰数的第N项。h(n)=C(2*n,n)/(n+1)。

(7)设有i个枝点,I为所有枝点的道路长度总和,J为叶的道路长度总和J=I+2i

二叉树的相关术语:

树的结点:包含一个数据元素及若干指向子树的分支;
孩子结点:结点的子树的根称为该结点的孩子;
双亲结点:B 结点是A 结点的孩子,则A结点是B 结点的双亲;
兄弟结点:同一双亲的孩子结点; 堂兄结点:同一层上结点;
祖先结点: 从根到该结点的所经分支上的所有结点子孙结点:以某结点为根的子树中任一结点都称为该结点的子孙
结点层:根结点的层定义为1;根的孩子为第二层结点,依此类推;
树的深度:树中最大的结点层
结点的度:结点子树的个数
树的度: 树中最大的结点度。
叶子结点:也叫终端结点,是度为 0 的结点;
分枝结点:度不为0的结点;
有序树:子树有序的树,如:家族树;
无序树:不考虑子树的顺序;

我的微信二维码如下,欢迎交流讨论

这里写图片描述

欢迎关注《IT面试题汇总》微信订阅号。每天推送经典面试题和面试心得技巧

微信订阅号二维码如下:

这里写图片描述

  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 4
博文 284
码字总数 214494
×
fengsehng
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: