文档章节

二叉树的性质

fengsehng
 fengsehng
发布于 2016/11/09 09:11
字数 870
阅读 2
收藏 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面试题汇总》微信订阅号。每天推送经典面试题和面试心得技巧

微信订阅号二维码如下:

这里写图片描述

© 著作权归作者所有

共有 人打赏支持
fengsehng
粉丝 4
博文 284
码字总数 214494
作品 0
朝阳
程序员
二叉树的性质以及二叉树的遍历(非递归)(c语言)(一)

二叉树的性质: 性质 1 在二叉树的第i层上至多有2^(i-1)个结点(i>=1)。 性质 2 深度为k的二叉树至多有2^k-1个结点,(k>=1)。 性质 3 任何一颗二叉树,终端结点为n0,度为2的结点为n2,那...

奔跑的码农
2016/05/14
196
0
二叉树的基本概念

二叉树的定义 一棵二叉树是结点的一个有限集合,该集合或者为空,或者是由一个根节点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。 二叉树的5种基本形态,任意一棵二叉树都由这...

大胖和二胖
2016/11/29
15
0
数据结构基础(16) --树与二叉树

树的基本术语 1.结点:{数据元素+若干指向子树的分支} 2.结点的度:分支的个数(子树的个数) 3.树的度:树中所有结点的度的最大值 4.叶子结点:度为零的结点 5.分支结点:度大于零的结点(包含根和...

翡青
2015/01/11
0
0
数据结构与算法 二叉树

最近重新回顾了数据结构中的树,树是一种非线性数据结构,其概念也不少。大家在初次接触树的时候,可能觉得它很难;之所产生这种感觉主要是由于树有一大堆陌生的概念、性质等内容。而当我真正...

云时之间
2017/12/03
0
0
数据结构之树

数据结构之树 目录: 二叉树的结构 二叉树的性质 二叉树的遍历 二叉树的特例 二叉树典型程序 树是一种编程中常常用到的一种数据结构,它的逻辑是:除了根结点之外每个结点只有一个父结点,根...

花开半夏qb
2016/11/29
0
0

没有更多内容

加载失败,请刷新页面

加载更多

同样是工作3年程序员,为什么别人每月25K你却只有15K?

你有没有静下心来思考过:同样是做了x年Java开发,为什么你的技术比别人差很多?为什么别人每月26K你却只有15K? 其实技术水平的高低和个人智商关系不大(毕竟能做Java编程开发大家都不会差)...

Java填坑之路
24分钟前
3
0
跨域问题:解决跨域的三种方案

当前端页面与后台运行在不同的服务器时,就必定会出现跨域这一问题,本篇简单介绍解决跨域的三种方案,部分代码截图如下,仅供参考: 方式一:使用ajax的jsonp 前端代码 服务器代码 使用该方...

rechardchensir
25分钟前
4
0
linux学习-1012

8.6 管道符和作业控制 8.7/8.8 shell变量 8.9 环境变量配置文件 扩展 bashrc和bash_profile的区别 http://ask.apelearn.com/question/7719 简易审计系统: http://www.68idc.cn/help/server/...

wxy丶
25分钟前
1
0
springboot dubbo 在程序初始化完成前 使用回声测试对服务依赖检测

<dubbo:consumer timeout="10000" check="false" /><dubbo:service delay="-1" /> @Component@Order(2)public class PrkServiceInit implements ApplicationListener {private Logge......

林伟琨
27分钟前
3
0
“网红架构师”解决你的Ceph 运维难题

Q1. 环境预准备 绝大多数MON创建的失败都是由于防火墙没有关导致的,亦或是SeLinux没关闭导致的。一定一定一定要关闭每个每个每个节点的防火墙(执行一次就好,没安装报错就忽视): CentOS s...

编程SHA
31分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部