妙语短篇a1原文:第二十三课 二叉树的存储结构
来源:百度文库 编辑:偶看新闻 时间:2024/06/01 12:31:52
教学目的: 掌握二叉树的两种存储结构
教学重点: 链式存储结构
教学难点: 链式存储二叉树的基本操作
授课内容:
一、复习二叉树的定义
二叉树的基本特征:每个结点的度不大于2。
二、顺序存储结构
#define MAX_TREE_SIZE 100
typedef TElemType SqBiTree[MAX_TREE_SIZE];
SqBiTree bt;
结点编号123456789101112131415
结点值123450000670000
第i号结点的左右孩子一定保存在第2i及2i+1号单元中。
缺点:对非完全二叉树而言,浪费存储空间
三、链式存储结构
一个二叉树的结点至少保存三种信息:数据元素、左孩子位置、右孩子位置
对应地,链式存储二叉树的结点至少包含三个域:数据域、左、右指针域。
也可以在结点中加上指向父结点的指针域P。
对结点有二个指针域的存储方式有以下表示方法:
typedef struct BiTNode{
TElemType data;
struct BitNode *lchild,*rchild;
}BiTNode,*BiTree;
基于该存储结构的二叉树基本操作有:
Status CreteBiTree(BiTree &T);
//按先序次序输入二叉树中结点的值(一个字符),空格字符表示空树,
//构造二叉链表表示的二叉树T。
Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e));
//采用二叉链表存储结构,Visit是对结点操作的应用函数
//先序遍历二叉树T,对每个结点调用函数Visit一次且仅一次
//一旦visit()失败,则操作失败
Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e));
//采用二叉链表存储结构,Visit是对结点操作的应用函数
//中序遍历二叉树T,对每个结点调用函数Visit一次且仅一次
//一旦visit()失败,则操作失败
Status PostOrderTraverse(BiTree T,Status(*Visit)(TElemType e));
//采用二叉链表存储结构,Visit是对结点操作的应用函数
//后序遍历二叉树T,对每个结点调用函数Visit一次且仅一次
//一旦visit()失败,则操作失败
Status LevelOrderTraverse(BiTree T,Status(*Visit)(TElemType e));
//采用二叉链表存储结构,Visit是对结点操作的应用函数
//层序遍历二叉树T,对每个结点调用函数Visit一次且仅一次
//一旦visit()失败,则操作失败
四、总结本课内容
顺序存储与链式存储的优缺点。
教学重点: 链式存储结构
教学难点: 链式存储二叉树的基本操作
授课内容:
一、复习二叉树的定义
二叉树的基本特征:每个结点的度不大于2。
二、顺序存储结构
#define MAX_TREE_SIZE 100
typedef TElemType SqBiTree[MAX_TREE_SIZE];
SqBiTree bt;
结点编号123456789101112131415
结点值123450000670000
第i号结点的左右孩子一定保存在第2i及2i+1号单元中。
缺点:对非完全二叉树而言,浪费存储空间
三、链式存储结构
一个二叉树的结点至少保存三种信息:数据元素、左孩子位置、右孩子位置
对应地,链式存储二叉树的结点至少包含三个域:数据域、左、右指针域。
也可以在结点中加上指向父结点的指针域P。
对结点有二个指针域的存储方式有以下表示方法:
typedef struct BiTNode{
TElemType data;
struct BitNode *lchild,*rchild;
}BiTNode,*BiTree;
基于该存储结构的二叉树基本操作有:
Status CreteBiTree(BiTree &T);
//按先序次序输入二叉树中结点的值(一个字符),空格字符表示空树,
//构造二叉链表表示的二叉树T。
Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e));
//采用二叉链表存储结构,Visit是对结点操作的应用函数
//先序遍历二叉树T,对每个结点调用函数Visit一次且仅一次
//一旦visit()失败,则操作失败
Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e));
//采用二叉链表存储结构,Visit是对结点操作的应用函数
//中序遍历二叉树T,对每个结点调用函数Visit一次且仅一次
//一旦visit()失败,则操作失败
Status PostOrderTraverse(BiTree T,Status(*Visit)(TElemType e));
//采用二叉链表存储结构,Visit是对结点操作的应用函数
//后序遍历二叉树T,对每个结点调用函数Visit一次且仅一次
//一旦visit()失败,则操作失败
Status LevelOrderTraverse(BiTree T,Status(*Visit)(TElemType e));
//采用二叉链表存储结构,Visit是对结点操作的应用函数
//层序遍历二叉树T,对每个结点调用函数Visit一次且仅一次
//一旦visit()失败,则操作失败
四、总结本课内容
顺序存储与链式存储的优缺点。
以二叉树表作存储结构,试编写求二叉树高度的算法?
以二叉链表做为存储结构建立二叉树的源程序
二叉链表作存储结构
二叉树的顺序存储
在free pascal中,怎样用顺序存储结构输入一个二叉树?多谢!!
二叉树采用链接方法存储,编写一个计算一个二叉树的高度的算法
完全二叉树的顺序存储的先序遍历
pascal 二叉树的顺序结构的中序遍历
在采用链式存储结构存储的二叉树上,以bt指向根接点,p指向任一给定接点,求从根接点到给定接点之间路径。
”只有根结点的二叉树是线形结构”对么,为什么
表达式的二叉树
二叉树的遍历
关于“二叉树”的
二叉树的遍历
假设以二叉链表存储的二叉数中,每个结点所含数据结构元素均为单字母,试编写算法,按树状打印二叉树的算
二叉树的存储与遍历问题 我的程序有两个错误帮我找一下
完全二叉树和满二叉树的区别
完全二叉树和满二叉树的区别
数据结构的二叉树求助
数据结构的二叉树求助
数据结构的二叉树1
数据结构的二叉树2
二叉树的实验报告
C++二叉树的课程设计