计算机备考资料：数据结构基本概念(五)

《计算机备考资料：数据结构基本概念(五)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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、也可以在"登录"页面，点击"新用户注册"按钮，进入用户注册页面;