0

0

二叉树的5个性质

藏色散人

藏色散人

发布时间:2019-06-05 09:37:03

|

15526人浏览过

|

来源于php中文网

原创

二叉树的5个性质

二叉树具有以下五个性质: 

1. 在二叉树的第i(i>=1)层最多有2^(i - 1)个结点。 

2. 深度为k(k>=0)的二叉树最少有k个结点,最多有2^k-1个结点。 

3. 对于任一棵非空二叉树,若其叶结点数为n0,度为2的非叶结点数为n2,则n0 = n2 +1。 

4. 具有n个结点的完全二叉树的深度为int_UP(log(2,n+1))。 

5. 如果将一棵有n个结点的完全二叉树自顶向下,同一层自左向右连续给结点编号1,2,3,......,n,然后按此结点编号将树中各结点顺序的存放于一个一维数组,并简称编号为i的结点为结点i( i>=1 && i

(1)若 i= 1,则结点i为根,无父结点;若 i> 1,则结点 i 的父结点为结点int_DOWN(i / 2); 

(2)若 2*i

(3)若2*i<=n,则结点i的右子女为结点2*i+1; 

(4)若结点编号i为奇数,且i!=1,它处于右兄弟位置,则它的左兄弟为结点i-1; 

(5)若结点编号i为偶数,且i!=n,它处于左兄弟位置,则它的右兄弟为结点i+1; 

(6)结点i所在的层次为 int_DOWN(log(2,i))+1。

三顾购物系统化妆品版
三顾购物系统化妆品版

本版本采用三顾购物平台,适合应用于化妆品销售。一、商品管理 商品发布:支持4种自定义价格,自定义商品字段完美支持多种行业应用,商品显示属性控制,不限上传商品图片,每个商品均有5帧幻灯片支持,拥有新品、特价、推荐等属性,可自定义随意编写商品介绍。商品管理:按各种属性查看商品列表、库存及价格,管理具体商品。商品评论:管理审核删除回复网友对商品的评级及评论。另支持品牌管理、单位管理、赠品管理等。二、订单

下载

部分性质的证明

性质1可以通过数学归纳法得到证明

性质2证明: 

由性质1可知,k层的最大节点总数可表示为2^0+2^ 1+……+2^ (k-1) = 2^k- 1;

性质3证明: 

首先,由节点的角度看n1+n2+n0=n,设此为(1)式; 

再从边的角度看,n2下接两条边,n1下接一条边,n个节点两两相连一共需要n-1条边,可得2*n2+n1=n-1,此为(2)式; 

由(1)式-(2)式,可得 

n0-n2=1。

相关专题

更多
C++ 高级模板编程与元编程
C++ 高级模板编程与元编程

本专题深入讲解 C++ 中的高级模板编程与元编程技术,涵盖模板特化、SFINAE、模板递归、类型萃取、编译时常量与计算、C++17 的折叠表达式与变长模板参数等。通过多个实际示例,帮助开发者掌握 如何利用 C++ 模板机制编写高效、可扩展的通用代码,并提升代码的灵活性与性能。

10

2026.01.23

php远程文件教程合集
php远程文件教程合集

本专题整合了php远程文件相关教程,阅读专题下面的文章了解更多详细内容。

29

2026.01.22

PHP后端开发相关内容汇总
PHP后端开发相关内容汇总

本专题整合了PHP后端开发相关内容,阅读专题下面的文章了解更多详细内容。

21

2026.01.22

php会话教程合集
php会话教程合集

本专题整合了php会话教程相关合集,阅读专题下面的文章了解更多详细内容。

21

2026.01.22

宝塔PHP8.4相关教程汇总
宝塔PHP8.4相关教程汇总

本专题整合了宝塔PHP8.4相关教程,阅读专题下面的文章了解更多详细内容。

13

2026.01.22

PHP特殊符号教程合集
PHP特殊符号教程合集

本专题整合了PHP特殊符号相关处理方法,阅读专题下面的文章了解更多详细内容。

11

2026.01.22

PHP探针相关教程合集
PHP探针相关教程合集

本专题整合了PHP探针相关教程,阅读专题下面的文章了解更多详细内容。

8

2026.01.22

菜鸟裹裹入口以及教程汇总
菜鸟裹裹入口以及教程汇总

本专题整合了菜鸟裹裹入口地址及教程分享,阅读专题下面的文章了解更多详细内容。

55

2026.01.22

Golang 性能分析与pprof调优实战
Golang 性能分析与pprof调优实战

本专题系统讲解 Golang 应用的性能分析与调优方法,重点覆盖 pprof 的使用方式,包括 CPU、内存、阻塞与 goroutine 分析,火焰图解读,常见性能瓶颈定位思路,以及在真实项目中进行针对性优化的实践技巧。通过案例讲解,帮助开发者掌握 用数据驱动的方式持续提升 Go 程序性能与稳定性。

9

2026.01.22

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
关于我们 免责申明 举报中心 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号 技术交流群
PHP中文网订阅号
每天精选资源文章推送

Copyright 2014-2026 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号