高中信息技术 数据与数据结构 用抽象数据类型表示二叉树 课件.pptxVIP

用抽象数据类型表示二叉树信息技术选择性必修1|数据与数据结构|第四章第三节课前回顾数组链表√×查找插入删除×√3二叉树的抽象数据类型目录1树4二叉树的基本操作方法2二叉树1Partone树树形结构树形结构树的定义：n(n=0)个结点的有限集合结点数n=0时——空树结点数n0时——有且仅有一个根结点+m个互不相交的有限结点集（m棵子树，m=0）12345761289101113142Parttwo二叉树树二叉树……二叉树定义二叉树定义：结点度数不超过2的树；每个节点的左子树的根节点被称为左孩子，右子树的根节点被称为右孩子。7123456特殊的二叉树1.满二叉树：一颗高度为h，且含有2h-1个结点的二叉树为满二叉树。5723416123456特殊的二叉树2.完全二叉树：假设一个高度为h、有n个结点的二叉树，当且仅当其每个结点都与高度为h的满二叉树中编号1~n的结点一一对应时，称为完全二叉树。4553417212366特殊的二叉树2.完全二叉树：假设一个高度为h、有n个结点的二叉树，当且仅当其每个结点都与高度为h的满二叉树中编号1~n的结点一一对应时，称为完全二叉树。152346二叉树的存储结构1.顺序存储：用一组连续的存储单元依次自上而下、自左而右存储完全二叉树上的结点元素。012345123456数组152346二叉树的存储结构1.顺序存储：用一组连续的存储单元依次自上而下、自左而右存储完全二叉树上的结点元素。0123456123456数组123二叉树的存储结构顺序存储弊端：空间利用率不高，比较适合完全二叉树。0123456123数组二叉树的存储结构2.链式存储：用链表来存放一棵二叉树，二叉树中每个结点用链表的一个链结点来存储。datanextlchilddatarchild二叉树的存储结构2.链式存储：用链表来存放一棵二叉树，二叉树中每个结点用链表的一个链结点来存储。typedefstructBiNode{TElemTypedata;structBiNode*lchild,*rchild;//左右孩子指针}BiNode,*BiTree;lchilddatarchild532146二叉树的存储结构2.链式存储：用链表来存放一棵二叉树，二叉树中每个结点用链表的一个链结点来存储。123645小结3Partthree二叉树的抽象数据类型参考定义ADT二叉树{ 数据：采用任何一种方式存储二叉树，其存储类型用BinTreeType标识符表示，该类型的一个二叉树用BT标识符表示。二叉树节点所保存的数据类型用ElemType表示。 操作：voidInitBTree(BinTreeTypeBT) //初始化二叉树，把它置为一课空树voidCreateBTree(BinTreeTypeBT) //建立对应的存储结构 boolEmptyBTree(BinTreeTypeBT) //判断一棵二叉树是否为空，若是则返回true，否则返回false voidTraverseBTree(BinTreeTypeBT) //按照一定的次序遍历一棵二叉树，使得每个节点的值均被访问一次 boolFindBTree(BinTreeTypeBT,ElemTypenode) //从二叉树中查找值为node的节点，若存在，返回true，否则返回false intBTreeDepth(BinTreeTypeBT) //求一棵二叉树的深度 voidClearBTree(BinTreeTypeBT) //清楚二叉树中的所有节点，使之变成一棵空树 …………}ADT二叉树4Partfour二叉树的基本操作方法根节点N左子树L右子树R二叉树的遍历遍历：按照一定的次序访问树中所有节点，并且每个节点的值仅被访问一次的过程。根节点N左子树L右子树R二叉树的遍历遍历：按照一定的次序访问树中所有节点，并且每个节点的值仅被访问一次的过程。先序遍历中序遍历后序遍历根节点N左子树L右子树R二叉树的遍历遍历：按照一定的次序访问树中所有节点，并且每个节点的值仅被访问一次的过程。先序遍历中序遍历后序遍历根节点N左子树L右子树R二叉树的遍历遍历：按照一定的次序访问树中所有节点，并且每个节点的值仅被访问一次的过程。先序遍历中序遍历后序遍历CAB二叉树的遍历先序遍历先序遍历若二叉树为非空：（1）访问根节点（2）先序遍历左子树（3）先序遍历右子树中序遍历后序遍历ABCADBEC二叉树的遍历先序遍历先序遍历若二叉树为非空：（1）访问根节点（2）先序遍历左子树（3）先序遍历右子树中序遍历后序遍历ABDEC二叉树的遍历算法实