(
课件网) 用抽象数据类型表示二叉树 信息技术选择性必修1 | 数据与数据结构 | 第四章第三节 课前回顾 数 组 链 表 查 找 插 入 删 除 √ × √ × 3 二叉树的抽象数据类型 1 树 4 二叉树的基本操作方法 2 二叉树 目录 1 树 Part one 树形结构 树形结构 1 3 5 10 7 2 9 11 8 6 4 12 13 14 树的定义：n(n>=0)个结点的有限集合 结点数n>0时———有且仅有一个根结点 + m个互不相交的有限结点集 （m棵子树，m>=0） 结点数n=0时———空树 2 二叉树 Part two 二叉树定义 树 …… 二叉树 二叉树定义：结点度数不超过2的树；每个节点的左子树的根节点被称为左孩子，右子树的根节点被称为右孩子。 特殊的二叉树 1. 满二叉树：一颗高度为h，且含有2h-1个结点的二叉树为满二叉树。 1 2 3 4 5 7 6 特殊的二叉树 2. 完全二叉树：假设一个高度为h、有n个结点的二叉树，当且仅当其每个结点都与高度为h的满二叉树中编号1~n的结点一一对应时，称为完全二叉树。 1 2 3 4 5 6 1 2 3 4 5 7 6 特殊的二叉树 2. 完全二叉树：假设一个高度为h、有n个结点的二叉树，当且仅当其每个结点都与高度为h的满二叉树中编号1~n的结点一一对应时，称为完全二叉树。 1 2 3 4 5 7 6 1 2 3 4 5 6 二叉树的存储结构 1. 顺序存储：用一组连续的存储单元依次自上而下、自左而右存储完全二叉树上的结点元素。 1 2 3 4 5 6 1 2 3 4 5 6 数组 0 1 2 3 4 5 二叉树的存储结构 1. 顺序存储：用一组连续的存储单元依次自上而下、自左而右存储完全二叉树上的结点元素。 1 2 3 4 5 6 1 2 3 4 5 6 数组 0 1 2 3 4 5 6 二叉树的存储结构 顺序存储弊端： 1 2 3 1 2 3 数组 0 1 2 3 4 5 6 空间利用率不高，比较适合完全二叉树。 二叉树的存储结构 2. 链式存储：用链表来存放一棵二叉树，二叉树中每个结点用链表的一个链结点来存储。 data next lchild data rchild 二叉树的存储结构 2. 链式存储：用链表来存放一棵二叉树，二叉树中每个结点用链表的一个链结点来存储。 lchild data rchild typedef struct BiNode{ TElemType data; struct BiNode *lchild,*rchild; //左右孩子指针 }BiNode,*BiTree; 二叉树的存储结构 2. 链式存储：用链表来存放一棵二叉树，二叉树中每个结点用链表的一个链结点来存储。 1 2 3 4 5 6 1 2 3 4 5 6 小结 3 二叉树的抽象数据类型 Part three 参考定义 ADT 二叉树 { 数据：采用任何一种方式存储二叉树，其存储类型用BinTreeType标识符表示，该类 型的一个二叉树用BT标识符表示。二叉树节点所保存的数据类型用ElemType表示。 操作： void InitBTree(BinTreeType &BT) //初始化二叉树，把它置为一课空树 void CreateBTree(BinTreeType &BT) //建立对应的存储结构 bool EmptyBTree(BinTreeType &BT) //判断一棵二叉树是否为空，若是则返回true，否则返回false void TraverseBTree(BinTreeType &BT) //按照一定的次序遍历一棵二叉树，使得每个节点的值均被访问一次 bool FindBTree(BinTreeType &BT , ElemType &node) //从二叉树中查找值为node的节点，若存在，返回true，否则返回false int BTreeDepth(BinTreeType &BT) //求一棵二叉树的深度 void ClearBTree(BinTreeType &BT) //清楚二叉树中的所有节点，使之变成一棵空树 ………… }ADT 二叉树 4 二叉树的基本操作方法 Part four 二叉树的遍历 遍历：按照一定的次序访问树中所有节点，并且每个节点的值仅被访问一次的过程。 根节点 N 左子树 L 右子树 R 先序遍历 中序遍历 后序遍历 二叉树的遍历 遍历：按照一定的次序访问树中所有节点，并且每个节点的值仅被访问一次的过程。 根节点 N 左子树 L 右子树 R 先序遍历 中序遍历 后序遍历 二叉树的 ... ...
