数据结构2(二叉树)

《数据结构2(二叉树)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1.6树与二叉树树的基本概念二叉树的定义及其存储结构二叉树的前序、中序和后序遍历1.6.1树的定义由一个或多个结点组成的有限集合。仅有一个根结点，结点间有明显的层次结构关系。ACGT2DHIT3JMBELKT1F现实世界中，能用树的结构表示的例子：学校的行政关系、书的层次结构、人类的家族血缘关系等。计算机科学与工程系办公室教研室实验室研究室行政办公室总支办公室计算机教研室软件教研室软件实验室综合实验室数字逻辑实验室组成原理试验室管理信息系统研究室知识工程研究室微机应用研究室NorthChinaElectricPowerUniversity树中的基本术语：ABCDEFGHIJKLM1.结点、结点

2、的度、树的度2.叶子结点、分支结点3.孩子、双亲、兄弟、堂兄弟、祖先、子孙4.结点的层次、树的深度5.有序树和无序树6.森林BCDEFGHIJKLM1.6.2二叉树（BinaryTree）1、二叉树的定义及其性质(1)二叉树的定义二叉树的五种基本形态二叉树一种特殊的树型结构，特点是树中每个结点只有两棵子树，且子树有左右之分，次序不能颠倒。空二叉树仅有根结点右子树为空左子树为空左右子树均非空因为树的每个结点的度不同，存储困难，使对树的处理算法很复杂。所以引出二叉树的讨论。二叉数是n(n0)个结点的有限集合。它或为空数(n=0),或由一个根结点和两棵分别称为根的左子树和右子树的互不相交的二叉数组

3、成。特别要注意：二叉树不是树的特殊情况。aabb两棵不同的二叉数NorthChinaElectricPowerUniversity具有三个结点的二叉树具有以下五种基本形态：A、二叉树的第i层上至多有2i-1（i1）个结点。(2)二叉树的基本性质423167891011121314155第三层上(i=3)，有23-1=4个节点。第四层上(i=4)，有24-1=8个节点。A、二叉树的第i层上至多有2i-1（i1）个结点。B、深度为h的二叉树中至多含有2h-1个结点。(2)二叉树的基本性质423167891011121314155此树的深度h=4，共有24-1=15个节点。A、二叉树的第i层上至

4、多有2i-1（i1）个结点。B、深度为h的二叉树中至多含有2h-1个结点。C、若在任意一棵二叉树中，有n0个叶子结点，有n2个度为2的结点，则：n0=n2+1(2)二叉树的基本性质423167891011121314155n0=8n2=7A、二叉树的第i层上至多有2i-1（i1）个结点。B、深度为h的二叉树中至多含有2h-1个结点。C、若在任意一棵二叉树中，有n0个叶子结点，有n2个度为2的结点，则：n0=n2+1D、具有n个结点的二叉树，其深度至少为log2n+1.(2)二叉树的基本性质（3）满二叉树423167891011121314155特点：每一层上都含有最大结点数。42316

5、7891011125非完全二叉树（4）完全二叉树423167891011125完全二叉树特点：除最后一层外，每一层都取最大结点数，最后一层结点都集中在该层最左边的若干位置。（5）树与二叉树的区别A．树的结点个数至少为1，而二叉树的结点个数可以为0。B．树中结点的最大度数没有限制，二叉树结点最大度数为2。C．树的结点无左、右之分，二叉树的结点子树有明确的左、右之分。树二叉树2、二叉树的存储结构(2)链式存储结构T[16]若父结点在数组中i下标处，其左孩子在2*i处，右孩子在2*i+1处。11ABcFED●●●●●●●●●1248910563712131415(1)顺序存储结构(1)顺序存储结构2

6、h-1=24-1=15用一组连续的存储单元存放二叉树的数据元素。结点在数组中的相对位置蕴含着结点之间的关系。0000FE000DC0BA15141312111098765432100一般二叉树必须按完全二叉树的形式存储，将造成存储的浪费。NorthChinaElectricPowerUniversity(2).二叉树的链式存储结构(二叉链表)链结点的构造为lchilddatarchild其中,data为数据域lchild与rchild分别为指向左、右子树的指针域.ABCDEFGIJABCDEFGJIBT^^^^^^^^^^1.6.3二叉树的遍历查找某个结点，或对二叉树中全部结点进行某种处理，就

7、需要遍历。（1）遍历定义及遍历算法遍历是指按某条搜索路线寻访树中每个结点，且每个结点只被访问一次。按先左后右的原则，一般使用三种遍历：二叉树为空时，执行空操作，即空二叉树已遍历完。否则：先序遍历(DLR):访问根结点，按先序遍历左子树，按先序遍历右子树。中序遍历(LDR):按中序遍历左子树，访问根结点，按中序遍历右子树。后序遍历(LRD):按后序遍历左子树，按后序遍历右子树，访问根结点。（2）遍历