大学数据结构之树和二叉树课件.pptVIP

6.1 树的定义与基本术语 树的基本概念 树的图解表示法 树的相关术语 树的基本操作 树的基本概念 树的图解表示法 树的图解表示法 树的相关术语 结点：包含一个数据元素及若干指向其他结点的分支信息。 结点的度：一个结点的子树个数称为此结点的度。 叶节点：度为0的结点，即无后继的结点，也称为终端结点。 分支结点：度不为0的结点，也称为非终端结点。 结点的层次：从根结点开始定义，根结点的层次为1，根的直接后继的层次为2，依此类推。 结点的层序编号：将树中的结点按从上层到下层、同层从左到右的次序排成一个线性序列，依次给它们编以连续的自然数。 树的相关术语 树的度：树中所有结点的度的最大值。 树的高度（深度）：树中所有结点的层次的最大值。 有序树：在树T中，如果各子树Ti之间是有先后次序的，则称为有序树。 森林：m(m=0)棵互不相交的树的集合。 同构：对两棵树，通过对结点适当地重命名，就可以使两棵树完全相等，则称这两棵树同构。 孩子结点：一个结点的直接后继称为该结点的孩子结点。 双亲结点：一个结点的直接前驱称为该结点的双亲结点。 树的相关术语 兄弟结点：同一双亲结点的孩子结点之间互称兄弟结点。 堂兄弟：父亲是兄弟关系或堂兄关系的结点称为堂兄弟结点。 祖先结点：一个结点的祖先结点是指从根结点到该结点的路径上的所有结点。 子孙结点：一个结点的直接后继和间接后继称为该结点的子孙结点。 前辈：层号比该结点小的结点，都称为该结点的前辈。 后辈：层号比该结点大的结点，都称为该结点的后辈。 树的相关术语 A、C、D的度各是多少？ 这棵树的度是多少？ 分支结点有哪些？ 叶结点有哪些？ B的孩子结点是谁？ D是谁的双亲结点？ B的子孙结点有哪些？ L的祖先结点是谁？ H的兄弟结点是谁？ M的结点层数是多少？ 这棵树的深度是多少？ 树的基本操作 树的基本操作 树的基本操作 6.2 二叉树 二叉树的定义与基本操作 二叉树的性质 二叉树的存储结构 二叉树的定义与基本操作 定义：把满足以下两个条件的树型结构叫做二叉树(Binary Tree)： 每个结点的度都不大于2； 每个结点的孩子结点次序不能任意颠倒。 例题：请分别画出三个结点的树和二叉树，试分析共有多少种不同画法？ 二叉树的基本操作 二叉树的基本操作 二叉树的性质 性质1 在二叉树的第i层上至多有2i-1个结点(i=1)。 性质2 深度为k的二叉树至多有2k-1个结点(k=1)。 性质3 对任意一棵二叉树T，若终端结点数为n0，而其 度数为2的结点数为n2，则n0=n2+1。 满二叉树和完全二叉树 二叉树的基本性质 二叉树的存储结构 顺序存储结构 二叉树顺序存储的类型定义 #define N 50 /*定义二叉树结点个数的最大值*/ typedef char DataType; typedef struct stree{ DataType tree[N]; /*定义一维数组存放二叉树的结点*/ int count; /*定义二叉树的实际结点个数*/ }SeqTree; 二叉树的顺序存储结构 二叉树的链式存储结构 链式存储结构 练习：请画出下面这棵二叉树的链式存储结构图。 二叉链表结点结构的定义 typedef char DataType; typedef struct node{ DataType data; /*数据域*/ struct node *Lchild; /*左孩子结点指针域*/ struct node *Rchild; /*右孩子结点指针域*/ }BiNode,*BiTree; 二叉树的链式存储结构 typedef char DataType; typedef struct node{ DataType data; /*数据域*/ struct node *Parent; /*双亲节点指针域*/ struct node *Lchild; /*左孩子结点指针域*/ struct node *Rchild; /*右孩子结点指针域*/ }TriNode,*TriTree; 练习：请画出下面这棵二叉树的链式存储结构图（要求使用三叉链表结构）。 课堂练习 深度为5的二叉树最多有多少个结点？其中第3层有多少个结点？ 如果一棵二叉树有5个度为1的结点，7个度为2的结点，问这棵二叉树共有多少个结点？ 一棵有49个结点的完全二叉树，问： 这棵树的深度是多少？ 编号为25的结点的左、右孩子结点的编号和双亲结点的编号分别是多少？ 如右