- 1、本文档共151页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
数据结构2叉树教学ppt
第六章 树和二叉树;6.1 树的类型定义;6.1
树的类型定义;数据对象 D:; 基本操作:; Root(T) // 求树的根结点 ;InitTree(T) // 初始化置空树 ; ClearTree(T) // 将树清空 ;A;(1) 有确定的根;
(2) 树根和子树根之间为有向关系。;基 本 术 语;结点:;(从根到结点的)路径:;任何一棵非空树是一个二元组
Tree = (root,F)
其中:root 被称为根结点,
F 被称为子树森林;对比树型结构和线性结构的结构特点;~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~;6.2
二叉树的类型定义
; 二叉树或为空树;或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。;二叉树的五种基本形态:; 二叉树的主要基本操作:; Root(T); Value(T, e); Parent(T, e);
LeftChild(T, e); RightChild(T, e);
LeftSibling(T, e); RightSibling(T, e);
BiTreeEmpty(T); BiTreeDepth(T);
PreOrderTraverse(T, Visit());
InOrderTraverse(T, Visit());
PostOrderTraverse(T, Visit());
LevelOrderTraverse(T, Visit());; InitBiTree(T);
Assign(T, e, value);
CreateBiTree(T, definition);
InsertChild(T, p, LR, c);;ClearBiTree(T);
DestroyBiTree(T);
DeleteChild(T, p, LR);;二叉树的重要特性; 性质 1 : 在二叉树的第 i 层上至多有2i-1 个结点。 (i≥1);性质 2 : 深度为 k 的二叉树上至多含 2k-1 个结点(k≥1); 性质 3 : 对任何一棵二叉树,若它含有n0 个叶子结点、n2 个度为 2 的结点,则必存在关系式:n0 = n2+1;两类特殊的二叉树:; 性质 4 : 具有 n 个结点的完全二叉树的深度为 ? log2n? +1;性质 5 :;6.3
二叉树的存储结构;#define MAX_TREE_SIZE 100
// 二叉树的最大结点数
typedef TElemType
SqBiTree[MAX_TREE_SIZE];
// 0号单元存储根结点
SqBiTree bt;;例如:;二、二叉树的链式存储表示;A;typedef struct BiTNode { // 结点结构
TElemType data;
struct BiTNode *lchild, *rchild;
// 左右孩子指针
} BiTNode, *BiTree;;root; typedef struct TriTNode { // 结点结构
TElemType data;
struct TriTNode *lchild, *rchild;
// 左右孩子指针
struct TriTNode *parent; //双亲指针
} TriTNode, *TriTree;;结点结构:; typedef struct BPTNode { // 结点结构
TElemType data;
int *parent; // 指向双亲的指针
char LRTag; // 左、右孩子标志域
} BPTNode
typedef struct BPTree{ // 树结构
BPTNode nodes[MAX_TREE_SIZE];
int num_node; // 结点数目
int root; // 根结点的位置
} BP
您可能关注的文档
- 散文阅读_理清思路.ppt
- 散而不乱-气脉中贯.ppt
- 散文阅读4-家乡的竹林.ppt
- 敬业和乐业教学ppt.ppt
- 数与代数-常见的量.ppt
- 教育理念的碰撞和交融[学员用].ppt
- 数位神经管理_周龙麒.ppt
- 数值分析[研究生]第3章数值积分与数值微分二.ppt
- 教科版思品八下第1单元第2课哭泣的自然[共35张PPT].ppt
- 数字图像信息和处理技术.ppt
- 北师大版小学数学三年级上册《寄书》教学设计.docx
- 统编版(部编版)语文二年级上册《雪孩子》教学设计.docx
- 统编版(部编版)语文二年级上册《八角楼上》教学设计.docx
- 北师大版小学数学三年级上册《长方形周长》教学设计.docx
- 北师大版小学数学三年级上册《丰收了》教学设计.docx
- 统编版(部编版)语文二年级上册《夜宿山寺》教学设计.docx
- 统编版(部编版)语文二年级上册《风娃娃》教学设计.docx
- 统编版(部编版)语文二年级上册《朱德的扁担》教学设计.docx
- 统编版(部编版)语文二年级上册《难忘的泼水节》教学设计.docx
- 统编版(部编版)语文二年级上册《纸船和风筝》教学设计.docx
文档评论(0)