第6章： 树1.ppt

前面我们学习的线性数据结构，每个元素都有唯一的前驱（第一个除外）和后继（最后一个除外），但是在现实应用中，一些问题的数据元素之间的关系就不这样简单，例如元素有多个前驱、多个后继。 本章学习一种非线性数据结构一树，数据元素之间是一种层次关系，元素有且只有一个前驱，但可以有多个后继。;例 人机对奕问题;第六章 树和二叉树; 树是一类重要的非线性数据结构，是以分支关系定义的层次结构 6.1 树的定义 定义 定义：树(tree)是n(n0)个结点的有限集T，其中： 有且仅有一个特定的结点，称为树的根(root) 当n1时，其余结点可分为m(m0)个互不相交的有限集T1,T2,……Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree) 特点： 树中至少有一个结点——根 树中各子树是互不相交的集合;A;A;6.2 二叉树 定义 定义：二叉树是n(n?0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成 特点 每个结点至多有二棵子树(即不存在度大于2的结点) 二叉树的子树有左、右之分，且其次序不能任意颠倒 基本形态;三个结点不同形态的二叉树(5种);6.2.2 二叉树的性质和特殊二叉树 1.二叉树的第i(i≥1)层最多有2i-1个结点;2.深度为k的二叉树最多有2k-1个结点;3.叶子的数目=度为2的结点数目+1 n0 = n2 + 1;4.满二叉树（full binary tree)---- 深度为k且有2k-1个结点的二叉树。;(1) n个结点的满二叉树的深度=log2(n+1) 设深度为k ∵ 2k - 1＝n 2k＝n + 1 ∴ k=log2(n+1) ;(2)顺序编号的满二叉树;● ? X ? = 不大于X的最大整数，取X的下限/地板 ● ? X ? = 不小于X的最小整数，取X的上限/天花板 例 ?3.1? = 3, ?3.9? = 3, ? 3 ? = 3 ?3.1? = 4, ?3.9? = 4 ? 3 ? = 3 5.完全二叉树（full binary tree)---- 深度为k的有n个结点的二叉树,当且仅当每一个结点 都与同深度的满二叉树中编号从1至n的结点一一对应,称 之为完全二叉树（其它教材称为“顺序二叉树”）。 例. 完全二叉树:;1;例 非完全二叉树:;6.2.3 二叉树的存储结构 1.顺序结构 (1) n个结点的完全二叉树，使用一维数组: typedef TElemType SqBiTree[MAX_TREE_SIZE]； 例.#define MAX_TREE_SIZE 7 SqBiTree bt;;(2) 一般二叉树;(3)右单枝树;2.链式存储结构 (1)二叉链表 typedef char TElemType;//由用户定义TElemType的实际类型 typedef struct BiTNode { TElemType data; //数据元素 struct BiTNode *rchild,*lchild;//右,左孩子指针 } BiTNode,*BiTree;//结点类型 BiTree root; //指向根结点的指针root;(2)三叉链表 除根结点外，在每个结点中增加一个指向双亲的指针域parent。;6.3 遍历二叉树和线索二叉树 6.3.1 遍历二叉树 按某种规则访问二叉树的每一个结点且每一结点仅被访问一次。 设: D----访问根结点,输出根结点； L----递归遍历左二叉树； R----递归遍历右二叉树。 遍历规则(方案): ● DLR----前序遍历(先根,preorder) ● LDR----中序遍历(中根,inorder) ● LRD----后序遍历(后根,postorder) ● DRL----逆前序遍历 ● RDL----逆中序遍历 ● RLD----逆后序遍历;1.前序遍历二叉树递归定义： 若二叉树为空，则遍历结束； 否则，执行下列步骤： (1) 访问根结点； (2) 遍历根的左子树； (3) 遍历根的右子树。 例1. 前序遍历;● 遍历T12： ● 访问F； ● 左子树为空,遍历结束； ● 右子树为空,遍历结束。 ● T12遍历结束。 ● T1遍历结束。;C;主程序;2.中序遍历二叉树递归定义： 若二叉树为空，则遍历结束； 否则，执行下列步骤