数据结构与算法——C语言和Java语言描述 ppt及答案和其他资源8二叉树的建立
9页1、创 建 二 叉 树,6.2二叉树 (Binary Tree),二叉树的定义 一棵二叉树是结点的一个有限集合,该集合或者为空,或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。每个结点最多只有2个孩子。,若i = 1,则该结点为根,无双亲结点 若i 1,则该结点的双亲结点编号为i /2 若2i n,则有编号为2i 的左孩子,否则没有左孩子 若2i+1 n,则有编号为2i+1的右孩子,否则没有右孩子 若 i 为奇数,且i != 1,则其左兄弟编号为i-1 若 i 为偶数,且i != n,则其右兄弟编号为i+1,性质5 如果将一棵有n个结点的完全二叉树自顶向下,同一层自左向右连续给结点编号 1, 2, , n,那么,对于编号为i (1 i n) 的结点,则有以下关系:,二叉树的顺序存储结构,用一组连续的的存储单元存放二叉树中的元素,即按满二叉树的形式存放在一维数组中 结点的编号恰好与数组元素的下标相对应 根据二叉树性质5,结点在一维数组中的相对位置隐含着结点之间的关系 适用于满二叉树和完全二叉树,根据二叉树性质5,在数组中可以方便地由某结点的下标找到它们的双亲结点,或
2、左、右孩子结点,存储示例,(a)完全二叉树的数组表示,(b)一般二叉树的数组表示,由于在顺序存储结构中是以结点在数组中的相对位置表示结点之间的关系,因此,一般二叉树也必须以完全二叉树的形式来存储,可能会造成存储空间的浪费。,单支树就是一个极端情况。例如,深度为k 的单支二叉树,它只有k个结点却需要2k-1个存储单元。,最常用的是二叉链表和三叉链表 二叉链表的每个结点有一个数据域和两个指针域,一个指针指向左孩子,另一个指向右孩子。,二叉树的链式存储结构,结点结构描述为: typedef struct btnode ElemType data; /* 数据域*/ struct btnode *lchild; /* 左孩子指针域*/ struct btnode *rchild; /* 右孩子指针域*/ BTNode;,/以先根遍历创建二叉树,AB#D#C# void Creat(BiTree *bt) Elemtype ch; printf(“请输入字符AB#D#C#:“); scanf(“%c“,else *bt=(BiTree)malloc(sizeof(btNode);/分配根节点 if(!*bt) printf(“分配节点失败n“);exit(0); (*bt)-data=ch; Creat( ,
《数据结构与算法——C语言和Java语言描述 ppt及答案和其他资源8二叉树的建立》由会员E****分享,可在线阅读,更多相关《数据结构与算法——C语言和Java语言描述 ppt及答案和其他资源8二叉树的建立》请在金锄头文库上搜索。
逍遥游复习 知识点整理
近现代法德关系史 高三展示课3稿
当代大学生人生信仰及追求的调查研究
长相思 纳兰性德-ppt课件
课件:危机意识 一
英语ppt演讲关于阿甘正传
发达国家基础教育改革的动向与趋势 修改版
中国民间美术 课件.ppt
生物质发电技术与系统 课程ppt 第1章 生物质发电技术现状及发展趋势 2学时 -----2016
现代信号处理思考题 含答案
执业药师继续教育 抑郁症的药物治疗 100分
小学生的成长档案模板不用修改 万能型
增订六版 现代汉语 上册 第二章文字 思考与练习答案
国家财政ppt课件
加拿大英语介绍
六年级统计图的选择课件
中学生成长档案ppt
中国现代文学史期末复习整理
lohi和hihilo训练对女子赛艇运动员运动能力影响的比较研究
风雨贾平凹阅读答案
2024-04-11 25页
2024-04-11 37页
2024-04-11 28页
2024-04-11 31页
2024-04-11 36页
2024-04-11 29页
2024-04-11 22页
2024-04-11 27页
2024-04-11 34页
2024-04-11 32页