欢迎来到天天文库
浏览记录
ID:28798980
大小:257.50 KB
页数:4页
时间:2018-12-14
《计算机备考资料:数据结构基本概念(五)》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、数据结构:基本概念(五) Ø二叉树的基本性质 性质1二叉树的第i层上最多有2i-1个结点(i≥1)。 性质2在一棵深度为k的二叉树中,最多有2k-1个结点,最少有k个结点。 性质3在一棵二叉树中,如果叶子结点的个数为n0,度为2的结点个数为n2,则 n0=n2+1。 性质4具有n个结点的完全二叉树的深度为。 性质5对一棵具有n个结点的完全二叉树中的结点从1开始按层序编号,则对于任意的编号为i(1≤i≤n)的结点(简称为结点i),有: ⑴如果i>1,则结点i的双亲的编号为;否则结点i是根结点,无双亲; ⑵如果2i≤n,则结点i的左孩子的编号为2i;否则结点i无左孩子; ⑶如果
2、2i+1≤n,则结点i的右孩子的编号为2i+1;否则结点i无右孩子。 Ø二叉树的存储 包括:二叉树的顺序存储和二叉树的链式存储。 二叉链表的存储结构定义如下: structBiNode { ElemTypedata; BiNode*lchild,*rchild; }*root;//root表示二叉链表的头指针 structTriNode { ElemTypedata; TriNode*lchild,*rchild,*parent;//parent指向该结点的双亲 }*root;//三叉链表的头指针 Ø遍历的含义 所谓遍历就是无重复无遗漏地访问。二叉树的遍历是指从根
3、结点出发,按照某种次序访问二叉树中的所有结点,使得每个结点被访问一次且仅被访问一次。 Ø二叉树的遍历次序定义 前序遍历(或称前根遍历、先序遍历) 若二叉树为空,则空操作返回;否则 ⑴访问根结点; ⑵前序遍历根结点的左子树; ⑶前序遍历根结点的右子树。 中序遍历(或称中根遍历) 若二叉树为空,则空操作返回;否则 ⑴中序遍历根结点的左子树; ⑵访问根结点; ⑶中序遍历根结点的右子树。 后序遍历(或称后根遍历) 若二叉树为空,则空操作返回;否则 ⑴后序遍历根结点的左子树; ⑵后序遍历根结点的右子树; ⑶访问根结点。 层序遍历 二叉树的层序遍历是从二叉树的第一层(根
4、结点)开始,从上至下逐层遍历,在同一层中,则按从左到右的顺序对结点逐个访问。文后寄语:book118是一个专注于电子文档的在线分享平台,用户在此平台上不但可以自由交换文档,还可以分享最新的行业资讯。book118制定了严格的文档审核策略,以保证文档来源的合法性,对有可能引起知识产权纠纷的文档,网站不予收录。同时,道客巴巴采用了行业领先的文档加密及保护技术,最大程度上保证用户上传的文档的版权不被非法侵犯。注册1、会员信息是您在book118网站的身份标识,注册后,您可以浏览文档、在线阅读或下载,建立并管理自己的文档信息库;2、打开网站的首页,点击页面上方的信息条文字"【免费注册】",在用户注册页
5、面,输入用户名、密码、电子邮件、验证码,阅读"服务协议",并选中"同意"复选框,最后点击"注册"按钮;3、也可以在"登录"页面,点击"新用户注册"按钮,进入用户注册页面;
此文档下载收益归作者所有