chap6树和二叉树.ppt

第六章树和二叉树,6.1 树的类型定义,6.2 二叉树的类型定义,6.3 二叉树的存储结构,6.4 二叉树的遍历,6.5 线索二叉树,6.6 树和森林的表示方法,6.7 树和森林的遍历,6.8 哈夫曼树与哈夫曼编码,6.1 树的类型定义,数据对象 D：,D是具有相同特性的数据元素的集合若D为空集，则称为空树 否则: (1) 在D中存在唯一的称为根的数据元素root； (2) 当n>1时，其余结点可分为m (m>0)个互 不相交的有限集T1, T2, …, Tm，其中每一 棵子集本身又是一棵符合本定义的树， 称为根root的子树数据关系 R：,,基本操作：,查 找 类,插 入 类,删 除 类,,,,,Root(T) // 求树的根结点,查找类：,Value(T, cur_e) // 求当前结点的元素值,Parent(T, cur_e) // 求当前结点的双亲结点,LeftChild(T, cur_e) // 求当前结点的最左孩子,RightSibling(T, cur_e) // 求当前结点的右兄弟,TreeEmpty(T) // 判定树是否为空树,TreeDepth(T) // 求树的深度,TraverseTree( T, Visit() ) // 遍历,,InitTree(&T) // 初始化置空树,插入类：,CreateTree(&T, definition) // 按定义构造树,Assign(T, cur_e, value) // 给当前结点赋值,InsertChild(&T, &p, i, c) // 将以c为根的树插入为结点p的第i棵子树,,ClearTree(&T) // 将树清空,删除类：,DestroyTree(&T) // 销毁树的结构,DeleteChild(&T, &p, i) // 删除结点p的第i棵子树,,A,B,C,D,E,F,G,H,I,J,M,K,L,,,,,,,,,,,,,A( B(E, F(K, L)), C(G), D(H, I, J(M)) ),,,,T1,T3,T2,,树根,例如:,(１) 有确定的根；(２) 树根和子树根之间为有向关系。

有向树：,有序树：,子树之间存在确定的次序关系无序树：,子树之间不存在确定的次序关系对比树型结构和线性结构的结构特点,~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~,线性结构,树型结构,第一个数据元素 (无前驱),根结点 (无前驱),最后一个数据元素 (无后继),多个叶子结点 (无后继),其它数据元素(一个前驱、 一个后继),其它数据元素(一个前驱、 多个后继),,基 本 术 语,结点:,结点的度:,树的度:,叶子结点:,分支结点:,数据元素+若干指向子树的分支,分支的个数,树中所有结点的度的最大值,度为零的结点,度大于零的结点,D,H,I,J,M,,,,,(从根到结点的)路径：,孩子结点、双亲结点兄弟结点、堂兄弟祖先结点、子孙结点,结点的层次:,树的深度：,由从根到该结点所经分支和结点构成,A,B,C,D,E,F,G,H,I,J,M,K,L,,,,,,,,,,,,,假设根结点的层次为1，第l 层的结点的子树根结点的层次为l+1,树中叶子结点所在的最大层次,任何一棵非空树是一个二元组 Tree = （root，F）其中：root 被称为根结点 F 被称为子树森林,森林：,是m（m≥0）棵互不相交的树的集合,A,root,,B,C,D,E,F,G,H,I,J,M,K,L,,,,,,,,,,F,,,,,6.2 二叉树的类型定义,二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。

A,B,C,D,E,F,G,H,K,,,,,,,,,,,根结点,左子树,右子树,二叉树的五种基本形态：,,,N,,,,,空树,只含根结点,N,N,N,L,R,R,右子树为空树,L,左子树为空树,左右子树均不为空树,二叉树的主要基本操作：,查 找 类,插 入 类,删 除 类,,Root(T); Value(T, e); Parent(T, e); LeftChild(T, e); RightChild(T, e); LeftSibling(T, e); RightSibling(T, e); BiTreeEmpty(T); BiTreeDepth(T); PreOrderTraverse(T, Visit()); InOrderTraverse(T, Visit()); PostOrderTraverse(T, Visit()); LevelOrderTraverse(T, Visit());,,InitBiTree(,,ClearBiTree(,,二叉树的重要特性,性质1： 在二叉树的第 i 层上至多有2i-1 个结点。

(i≥1),用归纳法证明： 归纳基： 归纳假设： 归纳证明：,i = 1 层时，只有一个根结点： 2i-1 = 20 = 1；,假设对所有的 j，1≤ j  i，命题成立；,二叉树上每个结点至多有两棵子树，则第 i 层的结点数 = 2i-2 2 = 2i-1 性质 2 ： 深度为 k 的二叉树上至多含 2k-1 个结点（k≥1）证明：,基于上一条性质，深度为 k 的二叉树上的结点数至多为 20+21+       +2k-1 = 2k-1 性质 3 ： 对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0 = n2+1证明：,设 二叉树上结点总数 n = n0 + n1 + n2又 二叉树上分支总数 b = n1+2n2 而 b = n-1 = n0 + n1 + n2 - 1由此， n0 = n2 + 1 两类特殊的二叉树：,满二叉树：指的是深度为k且含有2k-1个结点的二叉树。

完全二叉树：树中所含的 n 个结点和满二叉树中编号为 1 至 n 的结点一一对应1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,,,,,,,,,,,,,,,a,b,c,d,e,f,g,h,i,j,,,,,,,,,,,性质 4 ： 具有 n 个结点的完全二叉树的深度为  log2n +1 证明：,设完全二叉树的深度为 k 则根据第二条性质得 2k-1≤ n < 2k 即 k-1 ≤ log2 n < k 因为 k 只能是整数，因此， k =log2n + 1 性质 5 ：,若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点：(1) 若 i=1，则该结点是二叉树的根，无双亲，否则，编号为 i/2 的结点为其双亲结点；(2) 若 2i>n，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子结点；(3) 若 2i+1>n，则该结点无右孩子结点， 否则，编号为2i+1 的结点为其右孩子结点6.3 二叉树的存储结构,二、二叉树的链式 存储表示,一、 二叉树的顺序 存储表示,,#define MAX_TREE_SIZE 100 // 二叉树的最大结点数typedef TElemType SqBiTree[MAX_ TREE_SIZE]; // 0号单元存储根结点SqBiTree bt;,一、 二叉树的顺序存储表示,例如:,A,B,C,D,E,F,,,,A B D C E F,,,,,,,,,,,,,,,0 1 2 3 4 5 6 7 8 9 10 11 12 13,,,,,,1,4,0,13,2,6,,二、二叉树的链式存储表示,1. 二叉链表,2．三叉链表,3．双亲链表,4．线索链表,,A,,,D,,,E,,,B,,,C,,,F,,,,,,,,,,,,,,,,root,lchild data rchild,,,,结点结构:,1. 二叉链表,typedef struct BiTNode { // 结点结构 TElemType data; struct BiTNode *lchild, *rchild; // 左右孩子指针} BiTNode, *BiTree;,lchild data rchild,,,,结点结构:,C 语言的类型描述如下:,,A,,,D,,,E,,,B,,,C,,,F,,,,,,,,,,,,,,,root,,,,,,,,,,,,,,2．三叉链表,parent lchild data rchild,,,,,结点结构:,typedef struct TriTNode { // 结点结构 TElemType data; struct TriTNode *lchild, *rchild; // 左右孩子指针 struct TriTNode *parent; //双亲指针 } TriTNode, *TriTree;,parent lchild data rchild,,,,,结点结构:,C 语言的类型描述如下:,,0123456,data parent,结点结构:,3．双亲链表,LRTag,,LRRRL,typedef struct BPTNode { // 结点结构 TElemType data; int *parent; // 指向双亲的指针 char LRTag; // 左、右孩子标志域 } BPTNode typedef struct BPTree{ // 树结构 BPTNode nodes[MAX_TREE_SIZE]; int num_node; // 结点数目 int root; // 根结点的位置 } BPTree,,6.4二叉树的遍历,一、问题的提出,二、先左后右的遍历算法,三、算法的递归描述,四、中序遍历算法的非递归描述,五、遍历算法的应用举例,顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。

一、问题的提出,“访问”的含义可以很广，如：输出结点的信息等遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要另加讨论而二叉树是非线性结构，,每个结点有两个后继，则存在如何遍历即按什么样的搜索路径遍历的问题。