加载中…
个人资料
_陌上花开7_
_陌上花开7_
  • 博客等级:
  • 博客积分:0
  • 博客访问:68,244
  • 关注人气:29
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

二叉树

(2013-06-01 07:28:15)
标签:

二叉树

森林

转换

结构存储

遍历

分类: 数据结构
二叉树是n(n>=0)个结点的有限集合,该集合或者为空集(称为空二叉树),或者由一个根结点和两棵互不相交的,分别称为根结点的左子树和右子树的二叉树组成。
特点:①每个结点最多有两棵子树,所以二叉树中不存在度大于2的结点
②二叉树是有序的,其次序不能任意颠倒,即使树中某个结点只有一棵子树,也要区分它是左子树还是右子树。
1、斜树
所有结点都只有左子树的二叉树称为左斜树,所有结点都只有右子树的二叉树称为右斜树;左斜树和右斜树统称为斜树。
2、满二叉树
在一棵二叉树中,如果所有分支结点都存在左子树和右子树,并且所有叶子都在同一层上,这样的二叉树称为满二叉树。特点是①叶子只能出现在最下一层;②只有度为0和度为2的结点。
3、完全二叉树
对一棵具有n个结点的二叉树按层序编号,如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中的位置完全相同,则这棵二叉树称为完全二叉树。显然一棵满二叉树必然是完全二叉树。完全二叉树的特点①叶子结点只能出现在最下两层,且最下层的叶子结点都集中在二叉树左侧连续的位置;②如果有度为1的结点,只可能有一个,且该结点只有左孩子。
二叉树的基本性质
1、二叉树的第i层最多有2的(i-1)次方个结点(i>=1);
2、在一棵深度为k的二叉树中,最多有2的k次方-1个及诶单,最少有k个结点;
3、在一棵二叉树中如果叶子结点的个数为n0,度为2的结点个数为n1,则n0=n1+1
4、具有n个结点的完全二叉树的深度为[log2(n)]+1,即2的n次方取对数后取整,然后再加1
5、对一棵具有n个结点完全二叉树的结点从1开始按层序编号,则对于任意编号为i(1<=i<=n)的结点(简称为结点i)有:
(1)如果i>1,则结点i的双亲的编号为[i/2];否则结点i是根结点,无双亲;
(2)如果2i<=n,则结点i的左孩子的编号为2i;否则结点i无左孩子;
(3)如果2i+1<=n,z则该结点i的右孩子的编号为2i+1;否则结点i为右孩子;

ADT BiTree

Data

    二叉树是由一个根节点和两棵互不相交的左右子树构成

    二叉树中的结点具有相同的数据类型及层次关系

Operation

 InitBiTree

   前置条件:无

   输入:无

   功能:初始化一棵二叉树

   输出:无

   后置条件:构造一棵空的二叉树

DestroyBiTree

   前置条件:二叉树已存在

   输入:无

   功能:销毁一棵二叉树

   输出:无

   后置条件:释放二叉树占用的存储空间

PreOrder

   前置条件:二叉树已存在

   输入:无

   功能:前序遍历二叉树

   输出:二叉树的前序遍历序列

   后置条件:二叉树保持不变

 

InOrder

   前置条件:二叉树已存在

   输入:无

   功能:二叉树的中序遍历二叉树

   输出:二叉树树的中序遍历序列

   后置条件:二叉树树保持不变

PostOrder

   前置条件:二叉树已存在

   输入:无

   功能:后序遍历树

   输出:二叉树的后序遍历序列

   后置条件:二叉树保持不变

 

InOrder

   前置条件:二叉树已存在

   输入:无

   功能:二叉树的中序遍历二叉树

   输出:二叉树的中序遍历序列

   后置条件:二叉树保持不变

LeverOrder

   前置条件:二叉树已存在

   输入:无

   功能:二叉树的层序遍历二叉树

   输出:二叉树的层序遍历序列

   后置条件:二叉树保持不变

endADT

二叉树的遍历操作

1、前序遍历

若二叉树为空,则空操作返回;否则

(1)问回根节点;

(2)前序遍历根节点的左子树;

(3)前序遍历根节点的右子树;

 

2、中序遍历

若二叉树为空,则空操作返回;否则

(1)中序遍历根节点的左子树;

(2)访问根节点;

(3)中序遍历根节点的右子树;

 

3、后序遍历

若二叉树为空,则空操作返回;否则

(1)后序遍历根节点的左子树;

(2)后序遍历根节点的右子树;

(3)访问根节点;

 

4、层序遍历

二叉树的层序遍历,是指从二叉树的第一层(根节点)开始,从上至下逐层遍历,在同一层中,则按照从左到右的顺序对结点逐个访问。

二叉树的存储结构及实现

1、顺序存储

用一维数组存储二叉树中的结点,并充分利用逻辑关系——父子关系

说明:就是按照完全二叉树编号,然后把编号存储到一维数组中,添加的原来没有结点用空来表示,显然这样会造成存储空间的浪费。

2、二叉链表

基本思想:令二叉树的每个结点对应一个链表结点,链表结点除了存放与二叉树结点有关的数据信息外,还要设置只是左右孩子的指针。结构如lchild+data+rchild

data为数据域,存放该节点的数据信息;

lchild为左指针域,存放指向左孩子的指针,当左孩子不存在时为空节点;

rchild为右指针域,存放指向右孩子的指针,当右孩子不存在时为空结点;

3、三叉链表

二叉链表可以直接找到孩子结点,单不容易找到其双亲结点,改进如下:

lchild+data+rchild+parent

前三个域和二叉链表的结点结构相同,parent域指向该结点的双亲结点的指针。

4、线索链表

指向前驱和后继结点的指针称为线索,加上线索的二叉树称为线索二叉树,相应地,加上线索的二叉链表称为线索链表。结构是:Itag+lchild+data+rchild+rtag

若Itag=0,lchild指向该结点的左孩子       若trag=0 rchild指向该结点的右孩子

若Itag=1,lchild指向该结点的前驱         若trag=1 rchild指向该结点的后继

树、森林、二叉树的转换

树转换成二叉树

1、加线——树中所有相邻兄弟之间加一条连线;

2、去线——对树中的每个结点,只保留它与第一个孩子结点之间的连线,删去它与其他孩子结点之间的连线

3、层次调整—— 以根结点为轴心,将树顺时针转动一定的角度,使之层次分明

在二叉树中,左分支上的各结点在原来的树中都是父子关系,而右分支上的各结点在原来的树中是兄弟关系。由于树的根节点没有兄弟,所以转换后,二叉树根节点的右子树必为空。

森林转换成二叉树

森林是若干棵树的集合,将森林中的每棵树转换成二叉树,再将每棵树的根结点视为兄弟,方法如下:

1、将森林中的每棵树都转换成二叉树

2、从第二棵二叉树开始,一次把最后一棵二叉树的根节点作为前一棵二叉树根结点的右孩子,当所有二叉树连起来后,此时所得到的的二叉树就是由森林转换得到的二叉树。

二叉树转换成树或者森林

树和二叉树都可以转换成二叉树,二者不同的是树转换成的二叉树,其根结点无右子树,而森林转换后的二叉树,其根结点有右子树。显然这一转换是可逆的,即可以根据二叉树的根结点有无右子树,将一棵二叉树还原为森林,具体转换方法如下“

1、加线——若某结点x是其双亲y的做左孩子,则把结点x的右孩子、右孩子的右孩子、……都与结点y用线连接起来;

2、去线——删去原二叉树中所有的双亲结点与右孩子结点的连线;

3、层次调整——整理由1、2两部所得的树或森林,使其层次分明。

森林的遍历

森林有两种遍历方法:前序(根)遍历和后序(根)遍历

前序遍历森林即为前序遍历森林中的每一棵树

后序遍历森林即为后序遍历森林中的每一棵树



0

阅读 评论 收藏 转载 喜欢 打印举报/Report
前一篇:
后一篇:类继承
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

    < 前一篇
    后一篇 >类继承
      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有