数据结构二叉树

数据结构二叉树第1页，共44页，2023年，2月20日，星期六数据结构请安静§6.1树的定义和基本术语第2页，共44页，2023年，2月20日，星期六

1．数据的逻辑结构

2、数据的存储结构3、对数据的操作：检索、排序、插入、删除、修改A．线性结构

B．非线性结构A顺序存储

B链式存储线性表栈队列树形结构图形结构数据结构的三个主要问题DataStructure树的逻辑结构??一对多（1：n）第3页，共44页，2023年，2月20日，星期六五子棋游戏……..……..…...…...…...…...树的实例第4页，共44页，2023年，2月20日，星期六/(root)libuseretcbinmathdsswyintaoxieStack.cppQueue.cppTree.cpp人类的族谱各种社会关系各类分类编码编译程序的语法树Internet中的DNS（域名系统）UNIX文件系统结构树的实例第5页，共44页，2023年，2月20日，星期六

树是一类重要的非线性数据结构，是以分支关系定义的层次结构定义：树(tree)是n(n≥0)个结点的有限集，其中：n=0，称为空树有且仅有一个特殊的结点，称为树的根(root)当n>1时，其余结点可分为m(m>0)个互不相交的子集T1,T2,……Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree)特点：树中至少有一个结点——根树的定义是递归定义的，各子树也满足上面定义。树的定义第6页，共44页，2023年，2月20日，星期六~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~线性结构树型结构第一个数据元素

(无前驱)

根结点

(无前驱)最后一个数据元素

(无后继)多个叶子结点

(无后继)其它数据元素(一个前驱、一个后继)其它数据元素(一个前驱、多个后继)第7页，共44页，2023年，2月20日，星期六A只有根结点的树ABCDEFGHIJKLM有子树的树根子树叶子叶子叶子第8页，共44页，2023年，2月20日，星期六ADT

Tree{数据对象D:D是具有相同特性的数据元素的集合

数据关系R:若D为空集，则称为空树 否则:(1)在D中存在唯一的称为根的数据元素root；

(2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm，其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树

基本操作：

查找类操作

插入类操作

删除类操作}ADT

Tree树的抽象数据类型定义第9页，共44页，2023年，2月20日，星期六基本操作：TreeEmpty(T)

初始条件：树T已存在

操作结果：空树，返回TRUE;否则FALSETreeDepth(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中非根结点,返回其双亲;否则,返回空树的抽象数据类型定义第10页，共44页，2023年，2月20日，星期六LeftChild(T,cur_e)

初始条件：树T已存在,cur_e是T中结点操作结果：若cur_e是T中非叶子结点,返回其最左孩子;否则,返回空RightChild(T,cur_e)

初始条件：树T已存在,cur_e是T中结点操作结果：若cur_e是T中非叶子结点,返回其最右孩子;否则,返回空TraverseTree(T,visit())初始条件：树T已存在

操作结果：按某种次序对T的每个元素调用函数visit()查找类：基本操作：树的抽象数据类型定义第11页，共44页，2023年，2月20日，星期六插入类：InsertChild(&T,&p,i,c)

初始条件：树T存在,p指向T中结点,1≤i

≤p指结点度+1,非空树c与T不相交操作结果：将以c为根的树插入为T中p指结点的第i棵子树CreateTree(&T,definition)

初始条件：definition给出树的定义操作结果：按definition构造树TAssign(T,cur_e,value)

初始条件：树T已存在,cur_e是T中结点操作结果：结点cur_e赋值为valueInitTree(&T)

操作结果：构造空树T基本操作：树的抽象数据类型定义第12页，共44页，2023年，2月20日，星期六DeleteChild(&T,&p,i)

初始条件：树T存在,p指向T中结点,1≤i

≤p指结点度操作结果：删除T中p指结点的第i棵子树ClearTree(&T)

初始条件：树T已存在

操作结果：将树T清为空树DestroyTree(&T)

初始条件：树T已存在

操作结果：销毁树T删除类：基本操作：树的抽象数据类型定义第13页，共44页，2023年，2月20日，星期六结点(node)——表示树中的元素，以及构造元素之间关系的指针结点的度(degree)——结点拥有的子树数树的度——一棵树中最大的结点度数叶子(leaf)——度为0的结点，终端结点分支结点——度不为0的结点，非终端结点孩子(child)——结点子树的根称为该结点的孩子双亲(parents)——孩子结点的上层结点叫该结点的双亲树的基本术语第14页，共44页，2023年，2月20日，星期六兄弟(sibling)——同一双亲的孩子祖先——从根到该结点所经分支上的所有结点子孙（后裔）——一个节点所有子树上的节点节点的层次(level)——从根结点算起，根为第一层，它的孩子为第二层……堂兄弟——同一层的结点深度(depth)——树中结点的最大层次数,又称高度树的基本术语第15页，共44页，2023年，2月20日，星期六森林(forest)——m(m0)棵互不相交的树的集合无序树——子树之间不存在确定的次序关系有序树——各子树从左至右有严格的次序，不能互换，最左边的节点称为第一个孩子，最右边的节点称为最后一个孩子任何一棵非空树是一个二元组

Tree=（root，F）其中：root

被称为根结点

F

被称为子树森林树的基本术语第16页，共44页，2023年，2月20日，星期六树的表示JIACBDHGFEKLM图形表示法嵌套集合表示法广义表表示法凹入表示法第17页，共44页，2023年，2月20日，星期六GCKLEFBMHJIDA嵌套集合表示法

图型表示法

树的表示JIACBDHGFEKLM第18页，共44页，2023年，2月20日，星期六(A(B(E(k,L),F),C(G),D(H(M),I,J)))括号(广义表)表示法

图型表示法

树的表示JIACBDHGFEKLM第19页，共44页，2023年，2月20日，星期六图型表示法

ABCDEFGHIJKLM凹入表示法

树的表示JIACBDHGFEKLM第20页，共44页，2023年，2月20日，星期六结点A的度：结点B的度：结点M的度：叶子：结点A的孩子：结点B的孩子：结点I的双亲：结点L的双亲：结点B，C，D为结点K，L为树的度：结点A的层次：结点M的层次：树的深度：结点F，G为结点A是结点F，G的结点F，G是A结点的ABCDEFGHIJKLM320B,C,DE,F3144K,L,F,G,M,I,JDE兄弟兄弟堂兄弟祖先子孙请同学回答第21页，共44页，2023年，2月20日，星期六数据结构请安静§6.2二叉树第22页，共44页，2023年，2月20日，星期六6.2二叉树为何要重点研究每结点最多只有两个“叉”的树？二叉树的结构最简单，规律性最强；可以证明，所有树都能转换为唯一的一棵二叉树与其对应，不失一般性。6.2.1二叉树的定义6.2.2二叉树的性质6.2.3二叉树的存储结构第23页，共44页，2023年，2月20日，星期六定义：二叉树是n(n0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成特点每个结点至多有二棵子树(不存在度大于2的结点)子树有左、右之分，且其次序不能任意颠倒基本形态空二叉树左、右子树均非空DRL只有根结点二叉树D右子树为空DL左子树为空DR二叉树的定义第24页，共44页，2023年，2月20日，星期六有关二叉树下列说法正确的是（）A．二叉树的度为2 B．一棵二叉树的度可以小于2C．二叉树中至少有一个结点的度为2D．二叉树中任何一个结点的度都为2问：一棵度为2的树和一棵二叉树有何区别？试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。二叉树的定义第25页，共44页，2023年，2月20日，星期六二叉树的抽象数据类型定义ADTBinaryTree{数据对象D:数据关系R:基本操作P：}ADTBinaryTree若D=Φ，则R=Φ；若D≠Φ，则R={H}；存在二元关系：①root唯一//关于根的说明②Dl∩Dr=Φ//关于子树不相交的说明③……//关于二元关系的说明

④……

//关于左子树和右子树的说明D是具有相同特性的数据元素的集合。//至少有20个第26页，共44页，2023年，2月20日，星期六性质1：在二叉树的第i

层上至多有___个结点(i≥1)

第一层：第二层：第三层：第i层：只有一个根结点：21-1=20=1；二叉树上每个结点至多有两棵子树，则第i层的结点数=2i-1

。二叉树的性质最多：202

=21=2；最多：212

=22=4；2i-1第27页，共44页，2023年，2月20日，星期六二叉树的性质思考：具有n个节点的二叉树的深度最小________，最大________∵高度h的二叉树最多有2h-1个节点（性质2）∴n≤2h-1∴h≥

log2(n+1)

解答：性质2：123114589121367101415深度为k的二叉树上至多含____个结点（k≥1）证明：基于上一条性质，深度为k的二叉树上的结点数至多为

20+21++2k-1=2k-1

2k-1第28页，共44页，2023年，2月20日，星期六性质3：对任何一棵二叉树T，如果其叶子结点数为n0，度为2的结点数为n2，则n0=n2+1证明：设n1为度为1的节点数∵二叉树中所有节点的度≤2∴结点总数n=n0+n1+n2∵除根节点外，其余节点都是“别人”的孩子又∵叶子（n0）没有孩子！∴所有的孩子数n-1=n1+2n2∴

n=n1+2n2+1=n0+n1+n2∴n0=n2+1123456二叉树的性质第29页，共44页，2023年，2月20日，星期六满二叉树定义：特点：每一层上的结点数都是最大结点数123114589121367101415满二叉树及其编号指的是深度为k且含有2k-1个结点的二叉树特殊形式的二叉树第30页，共44页，2023年，2月20日，星期六完全二叉树定义：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为~特点叶子结点只可能在最后层和倒数第二层上出现特殊形式的二叉树第31页，共44页，2023年，2月20日，星期六1231145891213671014151231145891267101234567123456üü完全二叉树中可能有度为1的结点吗？?第32页，共44页，2023年，2月20日，星期六性质4：123114589126710证明：设完全二叉树的深度为k根据第二条性质得

n≤2k-1

且(2k-1-1)+1≤n即log2n<k≤log2n+1因为k只能是整数，因此，k=

log2n

+1。

完全二叉树性质具有n个结点的完全二叉树深度为_________log2n+1第33页，共44页，2023年，2月20日，星期六性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i(1in)，有：

(1)如果i=1,则结点i是二叉树的根,如果i>1,则其双亲是i/2(2)如果2i>n,则结点i无左孩子;如果2in,则其左孩子是2i(3)如果2i+1>n,则结点i无右孩子;如果2i+1n,则其右孩子是2i+1123114589126710完全二叉树性质第34页，共44页，2023年，2月20日，星期六二叉树性质小结二叉树的第i

层上至多有2i-1

个结点

性质1：性质2：深度为k的二叉树上至多含2k-1个结点性质3：对任何一棵二叉树T，如果其叶子结点数为n0，度为2的结点数为n2，则n0=n2+1

性质4：具有n个结点的完全二叉树的深度为

log2n+1

性质5：对完全二叉树有：(1)如果i>1,则其双亲是i/2(2)如果2i>n,则结点i无左孩子;否则其左孩子是2i(3)如果2i+1>n,则结点i无右孩子;否则其右孩子是2i+1第35页，共44页，2023年，2月20日，星期六课堂讨论：①二叉树是不是树的特殊情况？答：不是！它是单独定义的一种树状结构，并非一般树的特例。它的子树有顺序规定，分为左子树和右子树。不能随意颠倒。②：满二叉树和完全二叉树有什么区别？答：满二叉树是完全二叉树的一个特例。完全二叉树最底层却允许在右边缺少连续若干个结点。第36页，共44页，2023年，2月20日，星期六5.深度为9的完全二叉树中至少有

个结点。Ａ)２9

Ｂ)２8

Ｃ)９Ｄ)２9－14.深度为k的二叉树的结点总数，最多为

个。Ａ)２k-1

Ｂ)log2k

Ｃ)２k－１Ｄ)２k3.树Ｔ中各结点的度的最大值称为树Ｔ的

。Ａ)高度Ｂ)层次Ｃ)深度Ｄ)度√√√课堂讨论：第37页，共44页，2023年，2月20日，星期六二叉树的存储结构顺序存储结构链式存储结构第38页，共44页，2023年，2月20日，星期六一、完全二叉树实现：按结点层次编号，依次存放二叉树中的数据元素（用数组实现）ABCDEFGHI[1][2][3][4][5][6][7][8][9]ABCGEIDHF问：顺序存储后能否唯一对应一颗二叉树？有规律：下标值为i的结点，其左孩子的下标值必为2i，其右孩子的下标值必为2i＋1（即性质5）二叉树的存储结构——顺序存储结构第39页，共44页，2023年，2月20日，星期六不是完全二叉树怎么办？特点：结点间关系蕴含在其存储位置中浪费空间,k层需要长度多少的数组？abcdefg

1234567891011abcde0000fg该存储结构能否反映结点之间的关系？?0二叉树的存储结构——顺序存储结构适于满二叉树和完全二叉树补“虚结点”！第40页，共44页，2023年，2月20日，星期六ABCDEF思考：将该二叉树进行顺序存储二叉树的存储结构——顺序存储结构第41页，共44页，2023年，2月20日，星期六思考：请画出下列二叉树的图