《数据结构zmz5二叉树》由会员分享，可在线阅读，更多相关《数据结构zmz5二叉树（44页珍藏版）》请在金锄头文库上搜索。
1、主讲：郑梦泽信息工程学院请安静 第六章 树和二叉树（上）请安静 6.1树的定义和基本术语1数据的逻辑 结构 2、数据的存储结构 3、对数据的操作：检索、排序、插入、删除、修改A线性结构 B非线性结构A 顺序存储B 链式存储 线性表栈队列树形结构图形结构数据结构的三个主要问题 Data StructureData Structure树的逻辑结构树的逻辑结构 ?一对多（一对多（1 1：n n）五子棋游戏.树的实例/ (root)libuseretcbinmathdsswyintaoxieStack.cppQueue.cppTree.cpp人类的族谱各种社会关系各类分类编码编译程序的语法树Inter
2、net中的DNS（域名系统）UNIX文件系统结构树的实例树是一类重要的非线性数据结构，是 以分支关系定义的层次结构v定义：树(tree)是n(n0)个结点的有限集，其中：ln=0，称为空树l有且仅有一个特殊的结点，称为树的根(root)l当n1时，其余结点可分为m(m0)个互不相交的子集 T1,T2,Tm，其中每一个集合本身又是一棵树，称为根的 子树(subtree)v特点：l树中至少有一个结点根l树的定义是递归定义的，各子树也满足上面定义。树的定义 线性结构 树型结构 第一个数据元素 (无前驱)根结点 (无前驱)最后一个数据元素 (无后继)多个叶子结点 (无后继)其它数据元素 (一个前驱、一
3、个后继)其它数据元素 (一个前驱、多个后继)A只有根结点的树 ABCDEFGHIJKLM有子树的树 根 子树 叶子叶子叶子 ADT Tree 数据对象D: D是具有相同特性的数据元素的集合数据关系R: 若D为空集，则称为空树否则:(1) 在D中存在唯一的称为根的数据元素root；(2) 当n1时，其余结点可分为m (m0)个互不相交的有限集T1, T2, , Tm，其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树基本操作：查找类操作插入类操作删除类操作 ADT Tree树的抽象数据类型定义基本操作：TreeEmpty(T) 初始条件：树T已存在 操作结果：空树，返回 TRUE;否
4、则 FALSE TreeDepth(T) 初始条件：树T已存在 操作结果：返回 T 的深度查找类：Root(T) 初始条件：树T已存在 操作结果：返回T的根 Value(T, cur_e) 初始条件：树T已存在,cur_e是T中结点 操作结果：返回cur_e 的值 Parent(T, cur_e) 初始条件：树T已存在,cur_e是T中结点 操作结果：若cur_e是T中非根结点,返回其双亲;否则,返回空树的抽象数据类型定义LeftChild(T, cur_e) 初始条件：树T已存在,cur_e是T中结点 操作结果：若cur_e是T中非叶子结点,返回其最左孩子;否则,返回空RightChild(
5、T, cur_e) 初始条件：树T已存在,cur_e是T中结点 操作结果：若cur_e是T中非叶子结点,返回其最右孩子;否则,返回空TraverseTree(T, visit() 初始条件：树T已存在 操作结果：按某种次序对T 的每个元素调用函数visit()查找类：基本操作：树的抽象数据类型定义插入类：InsertChild(如果2in,则其左孩子是2i (3)如果2i+1n,则结点i无右孩子;如果2i+1n,则其右孩子是2i+1 123114589126710完全二叉树性质二叉树性质小结二叉树的第 i 层上至多有2i-1 个结点 性质1： 性质2：深度为 k 的二叉树上至多含 2k-1 个
6、结点 性质3：对任何一棵二叉树T，如果其叶子结点数为 n0，度为2的结点数为n2，则n0=n2+1 性质4： 具有n个结点的完全二叉树的深度为 log2n+1 性质5：对完全二叉树有： (1) 如果i1,则其双亲是i/2 (2)如果2in,则结点i无左孩子;否则其左孩子是2i (3)如果2i+1n,则结点i无右孩子;否则其右孩子是 2i+1 课堂讨论：课堂讨论： 二叉树是不是树的特殊情况？二叉树是不是树的特殊情况？ 答：答：不是！它是单独定义的一种树状结构，并非一不是！它是单独定义的一种树状结构，并非一 般树的特例。般树的特例。 它的子树有顺序规定它的子树有顺序规定，分为，分为左子树左子树和和
7、右子树右子树。不能。不能 随意颠倒。随意颠倒。：满二叉树和满二叉树和完全二叉树完全二叉树有什么区别？有什么区别？ 答：答：满二叉树是完全二叉树的一个特例。满二叉树是完全二叉树的一个特例。 完全二叉树最底层却允许在右边缺少连续若干个结完全二叉树最底层却允许在右边缺少连续若干个结 点。点。5. 5. 深度为深度为9 9的完全二叉树中至少有的完全二叉树中至少有 个结点。个结点。) )9 9) )8 8) ) ) )9 91 14.4.深度为深度为k k 的二叉树的结点总数，最多为的二叉树的结点总数，最多为 个。个。) )k-1k-1 ) log) log2 2k k) ) k k ) )k k3.
8、3. 树中各结点的度的最大值称为树的树中各结点的度的最大值称为树的 。) ) 高度高度 ) ) 层次层次) ) 深度深度 ) ) 度度课堂讨论：课堂讨论：二叉树的存储结构 顺序存储结构链式存储结构一、完全二叉树一、完全二叉树 实现：按结点层次编号， 依次存放二叉树中的数据 元素（用数组实现）A A B B C C D D E E F F G G H HI I11 22 33 44 55 66 77 88 99A AB BC CGGE EI ID DHHF F问：顺序存储后能否唯一对应一颗二叉树？问：顺序存储后能否唯一对应一颗二叉树？ 有规律：有规律：下标值为下标值为i i的结点，其左孩子的下标
9、值必为的结点，其左孩子的下标值必为 2i2i，其右孩子的下标值必为其右孩子的下标值必为2i2i1 1（即性质即性质5 5）二叉树的存储结构顺序存储结构不是完全二叉树怎么办？ 特点：结点间关系蕴含在其存储位置中 浪费空间,k层需要长度多少的数 组？ abcdefg1 2 3 4 5 6 7 8 9 10 11 a b c d e 0 0 0 0fg该存储结构能否反映结点之间的关系？0二叉树的存储结构顺序存储结构适于适于满二叉树满二叉树 和和完全二叉完全二叉 树树补补“虚结点虚结点” ！A A B BC CD DE EF F思考：将该二叉树进行顺序存储将该二叉树进行顺序存储二叉树的存储结构顺序存储
10、结构思考：请画出下列二叉树的图1 2 3 4 5 6 7 8 9 10 11 a b c 0 d e f0 0g h0二叉树的存储结构顺序存储结构1 2 3 4 5 6 7 8 9 10 11 12 a b c d 0 e 0 0 00 00 f二叉链表 lchild data rchild ABCDEFG在n个结点的二叉链表中，有n+1个空指针域ABC DE FG二叉树的存储结构链式存储结构typedef struct BitNode TElemType data;struct BitTNode *lchild, *rchild; BitNode, *BitTree;一、计算题：一、计算题：
11、 1 1）高度为）高度为h h的完全二叉树，最多有几个结点，最少几个？的完全二叉树，最多有几个结点，最少几个？ 2 2）完全二叉树中编号为）完全二叉树中编号为1111的结点的左右孩子是？的结点的左右孩子是？ 3 3）某二叉树共有）某二叉树共有8 8个叶子，度为个叶子，度为2 2的结点数为？的结点数为？ 4 4）某二叉树共有）某二叉树共有5151个结点，它的深度是？个结点，它的深度是？ 二、画图题：二、画图题： 1 1）深度为）深度为4 4、结点数为、结点数为7 7的二叉树；的二叉树； 2 2）深度为）深度为4 4、结点数为、结点数为1010的完全二叉树；的完全二叉树； 3 3）深度为）深度为3 3的满二叉树的满二叉树 4 4）深度为）深度为3 3、度为、度为4 4的树；的树； 三、问答题：三、问答题： 1 1）结点）结点H H的兄弟？祖先？孩子？的兄弟？祖先？孩子？ 2 2）结点）结点G G的堂兄弟？双亲？的堂兄弟？双亲？ 3 3）度为）度为2 2的结点有哪些？的结点有哪些？ 4 4）叶子的结点有哪些？）叶子的结点有哪些？作业： ABCDEFGHIJKLM第三题图
