11.二叉树基本理论 - 数据库编程

TOP

11.二叉树基本理论

2015-07-24 11:14:43 来源: 作者: 【大中小】浏览:3次

一、二叉树基本概念 1.定义 二叉树(Binary Tree)是n(n>=0)个结点的有限集合，该集合或者为空集(或称空二叉树)，或者由一个根节点和两颗互不相交的、分别称为根结点的左子树和右子树的二叉树组成。 2.二叉树特点 (1)每个结点最多有两颗子树，所以二叉树中不存在度大于2的结点; (2)左子树和右子树是有顺序的，次序不能任意颠倒; (3)即使树中某节点只有一颗子树，也要区分它是左子树还是右子树。另外，二叉树具有五种基本形态： a.空二叉树;b.只有一个根结点;c.根结点只有左子树;d.根结点只有右子树;e.根结点既有左子树又有右子树 3.特殊的二叉树 (1)斜树：所有的结点都只有左子树的二叉树称为左斜树;所有结点都是只有右子树的二叉树称为右斜树。特点：每一层都只有一个结点，结点的个数与二叉树的深度相同。 (2)满二叉树：在一颗二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。满二叉树特点：a)所有的叶子只能出现在最下一层且处于同一层; b)非叶子结点的度一定是2; c)在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。 (3)完全二叉树：对一颗具有n个结点的二叉树按层序编号，如果编号为i(1=
二、二叉树的性质 1.性质1：在二叉树的第i层上至多有2^(i-1)个结点(i>=1). 分析：计算二叉树某一层的结点数。这里的"至多"指的是，当该二叉树为满二叉树时，由数学归纳法论证可知，第i层有最多可以有2^(i-1)个结点。 2.性质2：深度为k的二叉树至多有2^k-1个结点(k>=1) 分析：计算二叉树结点总数。这里"深度为k"指有k层的二叉树，当该二叉树为满二叉树时，由数学归纳法论证可知，该二叉树至多有2^k-1个结点。 3.性质3：对任何一颗二叉树T，如果其终端结点数为n0,度为2的结点数为n2,则no=n2+1. 分析：一颗二叉树主要有n0个度为0的叶子结点、n1个度为1的结点、n2个度为2的结点组成。因此，该二叉树的结点总数n=n0+n1+n2(方程1).从二叉树中连接线数可知，由于根结点只有分支出去，没有分支进入，所有分支线总数减去1，即二叉树分支线总数=n-1=n1+2n2(方程2)(其中n1为度为1的结点数、n2为度为2的结点数)。联立方程得：n0=n2+1. 4.性质4：具有n个结点的完全二叉树的深度为「log2^n」+1 (「x」表示不大于x的最大整数)。分析：由性质2我们可以知道，深度为k的满二叉树的结点数n=2^k-1。由其倒推得到满二叉树的度数为k=log2^(n+1)。由于完全二叉树是满二叉树的一个子集，它的结点数一定少于等于同样度数的满二叉树的结点数2^k-1，但一定多于2^(k-1)-1。即满足2^(k-1)-12^(k-1)-1>=2^(k-1),所以2^(k-1)5.性质5：如果对一颗有n个结点的完全二叉树(其深度为「log2^n」+1)的结点按层序编号(从第1层到第「log2^n」+1 层，每层从左到右)，对任一结点i(1=
(1)如果i=1,则结点是i的二叉树的根，无双亲；如果i<1，则其双亲是结点[i/2]; (2)如果2i>n,则结点i无左孩子(结点i为叶子结点)；否则其左孩子是结点2i; (3)如果2i+1>n,则结点i无右孩子;否则其右孩子是结点2i+1. 三、二叉树的存储结构 1.二叉树顺序存储结构 由于二叉树是一种特殊的树，使得顺序存储结构得以实现。二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的存储位置，也就是数组的下标要能体现结点之间的逻辑关系，比如双亲与孩子的关系，左右兄弟的关系等。(k个结点，需要分配2^k-1个存储单元空间) 注意：顺序存储结构一般只用于完全二叉树。

2.二叉链表 (1)核心思想 二叉树每个结点最多有两个孩子，所有为它设计一个数据域和两个指针域，用来指向该结点的左右孩子，我们称为这样的链表为二叉链表。 (2)结点结构
其中，data为数据域，lchild和rchild都是指针域，分别存放指向左右孩子的指针 (3)二叉链表的结点结构定义代码 /*二叉树的二叉链表结点结构定义*/ typedef struct BiTNode /*结点结构*/ { TElemtype data; //结点数据 struct BiTNode *lchild,*rchild;//左右孩子指针 } BiTNode,*BiTree; (4)结构实例 >>二叉链表

>>三叉链表：parent指针域存放指向结点双亲的指针


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：MySQL日期类型DATETIME和TIMESTAMP	下一篇：SSD与HDD性能对比测试

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: