首页 > 其他 > 详细

二叉树

时间：2014-06-30 09:57:19      阅读：311      评论：0      收藏：0      [点我收藏+]
1. 定义
二叉树(BinaryTree)是n(n≥0)个结点的有限集，它或者是空集(n=0)，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。
二叉树的5中基本形态：
 bubuko.com,布布扣


满二叉树：一棵深度为k且有bubuko.com,布布扣个结点的二又树称为满二叉树，每一层上的结点数都达到最大值。


完全二叉树：若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。
特点：
（1）满二叉树是完全二叉树，完全二叉树不一定是满二叉树
（2）在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树是一棵完全二叉树。
（3）在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子。


2. 性质
1) 二叉树第i层上的结点数目最多为bubuko.com,布布扣(i≥1)。
2) 深度为k的二叉树至多有bubuko.com,布布扣个结点(k≥1)。
3) 在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1。
4) 具有n个结点的完全二叉树的深度为bubuko.com,布布扣。 
5) 如果对一棵有n个结点的完全二叉树的结点按层序编号，对任一结点i（bubuko.com,布布扣 ），有如下情况：
A. 如果i=1，则i为二叉树的根，无双亲；如果bubuko.com,布布扣 ，则其双亲PARENT(i)是结点bubuko.com,布布扣 。
B. 如果bubuko.com,布布扣 ，则结点i无左孩子（即i为叶子结点），否则其左孩子LCHILD(i)为2i。
C. 如果 bubuko.com,布布扣，则结点i无右孩子，否则其右孩子RCHILD(i)为2i+1。


3. 存储结构
1) 二叉链表表示法

 bubuko.com,布布扣


2) 三叉链表（带双亲指针的二叉链表）
 bubuko.com,布布扣

4. 二叉树遍历
1) 先序遍历
若二叉树非空，则依次执行如下操作：
A. 访问根结点；
B. 遍历左子树；
C. 遍历右子树。


2) 中序遍历
若二叉树非空，则依次执行如下操作：
A. 遍历左子树；
B. 访问根结点；
C. 遍历右子树。


3) 后序遍历
若二叉树非空，则依次执行如下操作：
A. 遍历左子树；
B. 遍历右子树；
C. 访问根结点。


4) 层次遍历
若二叉树非空，则从上到下，从左到右一次遍历二叉树中的每个结点。


5. 主要操作（二叉链表作为存储结构）
1) 初始化
 bubuko.com,布布扣

2) 销毁
 bubuko.com,布布扣

3) 根据输入的先序序列构建二叉树
 bubuko.com,布布扣

4) 计算二叉树深度
 bubuko.com,布布扣

5) 统计二叉树中叶子结点个数
 bubuko.com,布布扣

6) 复制二叉树
bubuko.com,布布扣

7) 先序遍历
 bubuko.com,布布扣

8) 中序遍历（递归和非递归版本）

 bubuko.com,布布扣

bubuko.com,布布扣

 
9) 后序遍历
 bubuko.com,布布扣

10) 层次遍历（利用队列完成）

 bubuko.com,布布扣



6. 树的常用存储结构
孩子兄弟表示法：链表中结点的两个指针分别指向该结点的第一个孩子和下一个兄弟结点。定义如下：
 bubuko.com,布布扣
注意树、森林与二叉树的转换，存在一一对应的关系。

二叉树,布布扣,bubuko.com

二叉树

原文：http://blog.csdn.net/yangping_peng/article/details/35556329
踩
(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 版权所有
打开技术之扣，分享程序人生！