首页 > 其他 > 详细

二叉树

时间：2020-05-26 21:47:10 阅读：56 评论：0 收藏：0 [点我收藏+]

二叉树是一类非常重要的特殊的树形结构

二叉树的定义

在二叉树中，每个结点至多有2个儿子，并且有左、右之分。

位于左边的孩子叫做左孩子

位于右边的孩子叫做右孩子

二叉树的性质

若二叉树的层次从 1 开始计数, 则，在二叉树的第i 层最多有 2^i－1个结点。( i>=1)

高度为 k 的二叉树最多有2^k-1个结点

具有n (n>=1) 个结点的二叉树的高度最多为n

对任何一棵二叉树, 如果其叶结点有n₀个, 度为2的结点有n₂ 个, 则有n₀＝n₂＋1

两种特殊的二叉树

满二叉树:一棵高度为h且有2h-1个结点的二叉树。

完全二叉树 (也叫近似满二叉树 ):若将满二叉树最后一层的结点，从右向左连续缺若干结点，就是完全二叉树。

二叉树的存储结构（重点）

二叉树的顺序存储结构

二叉树的链式存储结构

二叉树的遍历

先序遍历中序遍历后序遍历

① 访问根结点 ① 按中序遍历左子树 ① 按后序遍历左子树

② 按先序遍历左子树 ② 访问根结点 ② 按后序遍历右子树

③ 按先序遍历右子树 ③ 按中序遍历右子树 ③ 访问根结点

由遍历序列确定二叉树

两种遍历序列的组合	是否能唯一确定二叉树
先序 + 中序	是
后序 + 中序	是
先序 + 后序	否

原文：https://www.cnblogs.com/lxzw/p/12968514.html

踩

(0)

赞

(0)

举报

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)

最新文章

更多>

教程昨日排行

更多>

友情链接

汇智网 PHP教程插件网

关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com

© 2014 bubuko.com 版权所有

打开技术之扣，分享程序人生！