国家级精品课程《数据结构与算法》.ppt

1、国家级精品课程数据结构与算法,张铭、赵海燕、王腾蛟、宋国杰、高军http:/ 二叉树,5.1 二叉树的概念5.2 二叉树的抽象数据类型5.3 二叉树的存储结构5.4 二叉搜索树5.5 堆与优先队列5.6 Huffman树及其应用5.7 二叉树知识点总结,主要内容,5.1.1 二叉树的定义及基本术语5.1.2 满二叉树、 完全二叉树、 扩充二叉树5.1.3 二叉树的主要性质,5.1 二叉树的概念,二叉树的定义,二叉树(binary tree)由结点的有限集合构成，这个有限集合或者为空集(empty)，或者为由一个根结点(root)及两棵互不相交、分别称作这个根的左子树(left subtree)

2、和右子树(right subtree)的二叉树组成的集合。,二叉树的五种基本形态,图5.1 二叉树的五种基本形态,二叉树相关术语（1）,二叉树是由唯一的起始结点引出的结点集合。这个起始结点称为根(root)二叉树中的任何非根结点都有且仅有一个前驱结点，称之为该结点的父结点(或称为双亲，parent)。根结点即为二叉树中唯一没有父结点的结点二叉树中的任何结点最多可能有两个后继结点，分别称为左子结点(或左孩子、左子女，left child)和右子结点(或右孩子，右子女，right child)，具有相同父结点的结点之间互称兄弟结点(sibling)二叉树中结点的子树数目称为结点的度(degree)

3、。没有子结点的结点称为叶结点 (leaf，也称“树叶”或“终端结点”)，叶结点的度为0。除叶结点以外的那些非终端结点称为内部结点(或分支结点，internal node)父结点k与子结点k之间存在一条有向连线，称作边(edge),二叉树相关术语（2）,若二叉树中存在结点序列k0，k1，ks，使得，都是二叉树中的边，则称从结点k0到结点ks存在一条路径(path)，该路径所经历的边的个数称为这条路径的路径长度(path length)。若有一条由 k到达ks的路径，则称k是ks的祖先(ancestor)，ks是k的子孙(descendant)断掉一个结点与其父结点的连接，则该结点与其子孙构成的树

4、就称为以该结点为根的子树(subtree)从根结点到某个结点的路径长度称为结点的层数(level)，根结点为第0层，非根结点的层数是其父结点的层数加1,满二叉树与完全二叉树,如果一棵二叉树的任何结点，或者是树叶，或者恰有两棵非空子树，则这棵二叉树称作满二叉树(full binary tree)。 如果一棵二叉树最多只有最下面的两层结点度数可以小于2，并且最下面一层的结点都集中在该层最左边的连续位置上，则此二叉树称作完全二叉树(complete binary tree)。,图5.2 满二叉树和完全二叉树示例,完全二叉树,完全二叉树的特点是：其叶结点只可能在层次最大的两层出现完全二叉树中由根结点到

5、各个结点的路径长度总和在具 有同样结点个数的二叉树中达到了最小，即任意一棵 二叉树中根结点到各结点的最长路径一定不短于结点 数目相同的完全二叉树中的路径长度,扩充二叉树,在二叉树里出现空子树的位置增加空树叶，所形成的二叉树称为扩充二叉树(extended binary tree)构造一棵扩充二叉树只需要在原二叉树里度数为1的分支结点下增加一个空树叶，在原二叉树的树叶下面增加两个新的空树叶。扩充二叉树是满二叉树，新增空树叶(以下称为外部结点)的个数等于原二叉树的结点(以下称为内部结点)个数加1,扩充二叉树,图5.3 扩充二叉树,扩充二叉树,从扩充的二叉树的根到每个外部结点的路径长度之和称为外部路

6、径长度(E)。扩充的二叉树里从根到每个内部结点的路径长度之和称为内部路径长度(I)。外部路径长度E和内部路径长度I满足：E = I + 2n，其中n是内部结点个数。,扩充二叉树,例如，在图5.3这个有10个内部结点的扩充二叉树里 E = 3 + 4 + 4 + 3 + 4 + 4 + 3 + 4 + 4 + 3 + 3= 39 I = 0 + 1 + 2 + 3 + 2 + 3 + 1 + 2 + 3 + 2 = 19E和I两个量之间的关系为 E = I + 2n。,扩充二叉树,证明：对内部结点数目进行归纳。当n = 1时，I = 0且E = 2，故E = I + 2n成立。对于有n个内部结点

7、的扩充二叉树此等式已成立，即En = In十2n，现在考虑有n + 1个内部结点的扩充二叉树删去一个分支结点，该分支结点与根结点的路径长度是K，使之成为有n个内部结点的扩充二叉树。由于删去了一个路径长度为K的内部结点，内部路径长度变为In = In+1-K；由于减少了两个路径长度为K + 1的外部结点，增加了一个路径长度为 K的外部结点，外部路径长度变为En = En+1 - 2 ( K + 1) + K = En+1 K - 2。由前两个等式，有En+1 = In + 2n + K + 2 = In+1 + 2 ( n + 1 )。等式E = I+2n得证。,二叉树的主要性质,性质1. 在二

8、叉树中，第i层上最多有2i个结点（i0） 证明：利用数学归纳法 当i = 0时，20 = 1，只有一个根结点，正确。 现在假设对所有的j，1 j i，命题成立，即第j层上之多有2j个结点。下面证明当就j = i时结论也成立。由归纳假设，第i - 1层上最多有2i - 1个结点。由于二叉树每个结点的度数最大为2，所以第i层上的最大结点数为第i - 1层上的最大结点数的2倍，即2i个。,二叉树的主要性质,性质2. 深度为k的二叉树至多有 2k+1-1个结点（k0）。其中深度(depth)定义为二叉树中层数最大的叶结点的层数。证明：由性质1可知，第i层的最大结点数为2i，所以,二叉树的主要性质,性质

9、3. 任何一棵二叉树，若其终端结点数为n0 ，度为2的结点数为n2，则n0=n2+1 。 证明：设n1为二叉树中度为1 的结点数。该二叉树的结点总数n为度分别为0，1，2的结点数之和，即 n=n0+n1+n2 （公式5.1） 除根结点外，其余结点都有一条边进入，设边数为e，有n = e + 1。由于这些边是由度为1或2的的结点发出的，所以又有e=n1+2n2，于是得 n=e+1=n1+2n2+1 （公式5.2） 由公式5.1和5.2得 n0+n1+n2=n1+2n2+1， 即 n0=n2+1,二叉树的主要性质,性质4. 满二叉树定理：非空满二叉树树叶数目等于其分支结点数加1。 证明：满二叉树定

10、理由性质3可直接推出。 性质5. 满二叉树定理推论：一个非空二叉树的空子树数目等于其结点数加1。 证明：设二叉树为T，将其所有空子树换为树叶，记新扩充满二叉树为T。所有原来T的结点现在是T的分支结点。根据满二叉树定理，新添加的树叶数目等于T结点个数加1。而每个新添加的树叶对于T的一个空子树。因此T中空子树数目等于T中的结点个数加1,二叉树的主要性质,性质6. 有n个结点（n0）的完全二叉树的高度为log2 (n+1)（深度为log2 (n+1) - 1）。 其中二叉树的高度(height)定义为二叉树中层数最大的叶结点的层数加1。证明：假设高度为h，则根据性质2和完全二叉树的定义， 有 或 不

11、等式中各项取对数，于是得到 。因为h为整数，所以hlog2 (n+1)。,二叉树的主要性质,性质7. 对于具有n个结点的完全二叉树，结点按层次由左到右编号，则对任一结点i（0 i n - 1）有 （1）如果i = 0，则结点i是二叉树的根结点；若i0，则其父结点编号是(i - 1)/2。 （2）当2i + 1 n - 1时，结点i的左子结点是2i + 1，否则结点i没有左子结点。 当2i + 2 n - 1时，结点i的右子结点是2i + 2，否则结点i没有右子结点。 （3）当i为偶数且0 i n时，结点i的左兄弟是结点i - 1，否则结点i没有左兄弟。 当i为奇数且i+1 n-1，即不存在编号

12、为1的结点，此时结点i没有左孩子。其右孩子的编号只能是2，如果2n-1，此时结点i没有右孩子。 对于i0分两种情况讨论： (1)设第j层的第一个结点编号为i(此时有i = 2j-1)，则其左孩子必为第j + 1层的第一个结点，其编号为2j+1 - 1 = 2i + 1，如果2i + 1 n - 1，那么i没有左孩子；其右孩子必为第j + 1层第二个结点，其编号为2i + 2。 (2)假设第j层的某个结点编号为i，若它有左孩子，那么它的左孩子必然是第j + 1层中的第2i - (2j - 1)个，那么其左孩子的编号就是（2j+1 1） + 2i - (2j - 1) = 2i + 1；如果结点i

13、有右孩子，那么其右孩子的编号必是2i + 2。,5.2 二叉树的抽象数据类型,5.2.1 抽象数据类型5.2.2 深度优先周游二叉树5.2.3 广度优先周游二叉树,5.2.1 抽象数据类型,一般情况下需要二叉树的各个结点存储所需要的信息，对二叉树的操作和运算也主要集中在访问二叉树的结点信息上。例如访问某个结点的左子结点、右子结点、父结点，或者访问结点存储的数据。从二叉树的应用角度来看，有时还需要遍历二叉树的每个结点。,5.2.1 抽象数据类型,在二叉树的抽象数据类型中，定义了二叉树基本操作的集合，在具体应用中可以以此为基础进行扩充为了强调抽象数据类型与存储无关，在此并没有具体规定该抽象数据类型

14、的存储方式,5.2.1 抽象数据类型,【代码5.1】 二叉树结点的抽象数据类型(ADT)template class BinaryTreeNode friend class BinaryTree; / 声明二叉树类为结点类的友元类，以便访问私有数据成员private:T info; / 二叉树结点数据域public:BinaryTreeNode(); / 缺省构造函数BinaryTreeNode(const T/ 子树构造结点,5.2.1 抽象数据类型,T value() const;/ 返回当前结点的数据BinaryTreeNode* leftchild() const;/ 返回当前结点左子

15、树BinaryTreeNode* rightchild() const;/ 返回当前结点右子树void setLeftchild(BinaryTreeNode*) ;/ 设置当前结点的左子树void setRightchild(BinaryTreeNode*) ;/ 设置当前结点的右子树void setValue(const T,5.2.1 抽象数据类型,【代码5.2】 二叉树的抽象数据类型template class BinaryTree private:BinaryTreeNode* root; / 二叉树根结点public: BinaryTree() root = NULL;/ 构造函数

16、 BinaryTree() DeleteBinaryTree(root);/ 析构函数 bool isEmpty() const;/ 判定二叉树是否为空树BinaryTreeNode* Root()return root;/ 返回二叉树根结点,5.2.1 抽象数据类型,BinaryTreeNode* Parent(BinaryTreeNode *current); / 返回当前结点的父结点BinaryTreeNode* LeftSibling(BinaryTreeNode *current); / 返回当前结点的左兄弟BinaryTreeNode* RightSibling(BinaryTre

17、eNode *current); / 返回当前结点的右兄弟void CreateTree(const T / 删除二叉树或其子树 ；,5.2.1 抽象数据类型,所谓二叉树的周游(或称遍历，traversal)是指按照一定顺序依次访问树中所有结点，并使得每一结点仅被访问一次。这里所说的“访问”是指操作，可以理解成对二叉树结点数据成员的处理，比如输出、修改结点的信息等。周游一棵二叉树的过程实际上就是把二叉树的结点放入一个线性序列的过程，也就是对二叉树进行线性化。,5.2.2 深度优先周游二叉树,基于二叉树的递归定义，这三种深度优先周游的递归定义是： (1) 前序法(tLR次序，preorder t

18、raversal)。其递归定义是 访问根结点； 按前序周游左子树； 按前序周游右子树。 (2) 中序法(LtR次序，inorder traversal)。其递归定义是 按中序周游左子树； 访问根结点； 按中序周游右子树。(3) 后序法(LRt次序，postorder traversal)。其递归定义是 按后序周游左子树； 按后序周游右子树； 访问根结点。,5.2.2 深度优先周游二叉树,深度周游如下二叉树前序序列是：A B D E G C F H I中序序列是：D B G E A C H F I后序序列是：D G E B H I F C A,图5.5 二叉树示例,5.2.2 深度优先周游二叉树

19、,二叉树的周游算法与表达式的“前缀”和“后缀”表示法之间有着密切的联系。例如图5.6是表达式A+B(C+D)的二叉树表示。按照前序方式周游，运算符出现在前面，参与运算的对象紧跟在其后，这样就形成了前缀表达式（波兰式）：+ A B + C D按照中序方式周游，得到的结果是去掉括号的中缀表达式：A + B C + D下面是后序方式周游的结果，得到的是后缀表达式（逆波兰式）：A B C D + +,图5.6 表达式树,5.2.2 深度优先周游二叉树,【算法5.3】 深度优先周游二叉树或其子树templatevoid BinaryTree:PreOrder (BinaryTreeNode *root)

20、 / 前序周游二叉树或其子树if (root != NULL) Visit(root-value();/ 访问当前结点PreOrder(root-leftchild();/ 前序周游左子树PreOrder(root-rightchild();/ 前序周游右子树templatevoid BinaryTree: InOrder (BinaryTreeNode *root) / 中序周游二叉树或其子树if (root != NULL) InOrder (root-leftchild();/ 中序周游左子树,5.2.2 深度优先周游二叉树,Visit(root-value();/ 访问当前结点InOr

21、der(root-rightchild();/ 中序周游右子树templatevoid BinaryTree: PostOrder (BinaryTreeNode *root) / 后序周游二叉树或其子树if (root != NULL) PostOrder(root-leftchild();/ 后序周游左子树PostOrder (root-rightchild();/ 后序周游右子树Visit(root-value();/ 访问当前结点,5.2.2 深度优先周游二叉树,深度优先周游二叉树的非递归算法递归算法虽然简洁，但是有时程序设计不允许用递归，这时就存在如何把递归程序转化成等价的非递归算法

22、的问题解决这个问题的关键是设置一个栈结构。仿照递归算法执行过程中编译栈的工作原理，可以写出非递归周游二叉树的算法,5.2.2 深度优先周游二叉树,非递归前序周游算法的主要思想：每遇到一个结点，先访问该结点，并把该结点的非空右子结点推入栈中，然后周游其左子树左子树周游不下去时，从栈顶托出待访问的结点，继续周游。算法执行过程中，只有非空结点入栈为了算法的简洁，最开始推入一个空指针作为监视哨；当这个空指针被弹出来时，周游就结束了,5.2.2 深度优先周游二叉树,【算法5.4】 非递归前序周游二叉树或其子树templatevoid BinaryTree:PreOrderWithoutRecursion

23、(BinaryTreeNode *root) using std:stack;/ 使用STL中的栈stack* aStack;BinaryTreeNode *pointer = root; aStack.push(NULL); / 栈底监视哨 while (pointer) / 或者!aStack.empty() Visit(pointer-value(); / 访问当前结点,5.2.2 深度优先周游二叉树,if (pointer-rightchild() != NULL) / 非空右孩子入栈 aStack.push(pointer-rightchild(); if (pointer-left

24、child() != NULL) pointer = pointer-leftchild(); / 左路下降 else / 左子树访问完毕，转向访问右子树 pointer=aStack.top(); / 获得栈顶元素 aStack.pop(); / 栈顶元素退栈 ,5.2.2 深度优先周游二叉树,非递归中序周游算法的主要思想是：每遇到一个结点就把它推入栈，然后去周游其左子树周游完左子树后，从栈顶托出这个结点并访问之然后按照其右链接指示的地址再去周游该结点的右子树,5.2.2 深度优先周游二叉树,【算法5.5】 非递归中序周游二叉树或其子树templatevoid BinaryTree:InOr

25、derWithoutRecursion(BinaryTreeNode *root) using std:stack;/ 使用STL中的栈stack* aStack; BinaryTreeNode *pointer = root;while (!aStack.empty() | pointer) if (pointer) ,5.2.2 深度优先周游二叉树,aStack.push(pointer);/ 当前指针入栈pointer = pointer-leftchild(); / 左路下降 else / 左子树访问完毕，转向访问右子树pointer = aStack.top();/ 获得栈顶元素aS

26、tack.pop(); / 栈顶元素退栈 Visit(pointer-value(); / 访问当前结点pointer = pointer-rightchild(); / 指针指向右孩子 ,5.2.2 深度优先周游二叉树,在非递归的后序周游算法的主要思想：每遇到一个结点，先把它推入栈中，去周游它的左子树周游完它的左子树后，应继续周游该结点的右子树游完右子树之后，才从栈顶托出该结点并访问它,5.2.2 深度优先周游二叉树,解决方案：由于访问某个结点前需要知道是否已经访问该结点的右子树，因此需要给栈中的每个元素加一个标志位tag标志位用枚举类型Tags表示，tag为Left表示已进入该结点的左子树

27、；tag为Right表示已进入该结点的右子树,5.2.2 深度优先周游二叉树,【算法5.6】 非递归后序周游二叉树或其子树enum TagsLeft,Right; / 定义枚举类型标志位template class StackElement / 栈元素的定义public:BinaryTreeNode* pointer; / 指向二叉树结点的指针Tags tag; / 标志位;templatevoid BinaryTree:PostOrderWithoutRecursion(BinaryTreeNode* root) using std:stack; / 使用STL的栈StackElement

28、element;,stack aStack;BinaryTreeNode* pointer;if (root = NULL)/ 如果是空树则返回return; else pointer = root;while (!aStack.empty() | pointer) while (pointer != NULL) / 如果当前指针非空则压栈并下降到最左子结点element.pointer = pointer;element.tag = Left; / 置标志位为Left, 表示进入左子树aStack.push(element);pointer = pointer-leftchild();ele

29、ment = aStack.top();/ 获得栈顶元素,5.2.2 深度优先周游二叉树,aStack.pop();/ 栈顶元素退栈pointer = element.pointer;if (element.tag = Left) / 如果从左子树回来element.tag = Right; / 置标志位为Right, 表示进入右子树aStack.push(element);pointer = pointer-rightchild();else / 如果从右子树回来Visit(pointer-value(); / 访问当前结点pointer = NULL; / 置point指针为空，以继续弹栈

30、,5.2.2 深度优先周游二叉树,5.2.2 深度优先周游二叉树,对于有n个结点的二叉树，周游完树的每一个元素都需要O(n)时间只要对每个结点的处理（函数Visit的执行）时间是一个常数，那么周游二叉树就可以在线性时间内完成所需要的辅助空间为周游过程中栈的最大容量，即树的高度最坏情况下具有n个结点的二叉树高度为n，则所需要的空间复杂度为O(n),5.2.3 广度优先周游二叉树,对二叉树进行广度优先(层次)周游的过程是：首先访问第0层，也就是根结点所在的层然后从左到右依次访问第一层两个结点以此类推，当第i层的所有结点访问完之后，再从左至右依次访问第i+1层的各个结点,对于右图中的二叉树进行广度优

31、先周游的结果为： A B C D E F G H I,5.2.3 广度优先周游二叉树,【算法5.7】 广度周游二叉树及其子树templatevoid BinaryTree:LevelOrder(BinaryTreeNode *root)using std:queue; / 使用STL的队列queue* aQueue;BinaryTreeNode *pointer = root;if (pointer)aQueue.push(pointer); / 根结点入队列while (!aQueue.empty() / 队列非空pointer = aQueue.front(); / 获得队列首结点aQue

32、ue.pop(); / 当前结点出队列 Visit(pointer-value(); / 访问当前结点if (pointer-leftchild() != NULL)aQueue.push(pointer-leftchild(); / 左子树进队列if (pointer-rightchild()!= NULL)aQueue.push(pointer-rightchild(); / 右子树进队列,5.3 二叉树的存储结构,5.3.1 二叉树的链式存储结构 5.3.2 完全二叉树的顺序存储结构,5.3.1 二叉树的链式存储结构,所谓链式存储方式，是指二叉树的各结点随机的存储在内存空间中，结点之间的

33、关系用指针表示。 二叉树的链表的结点包含三个域：数据域和左、右指针域。用info域存储结点的数据元素，另外再设置两个指针域left和right，分别指向结点的左子结点和右子结点当结点的某个子结点为空时，相应的指针为空指针。其结点结构如图5.7(a)所示。有时候为了便于查找二叉树中某个结点的父结点，还可以在结点结构中加入一个指向其父结点的指针域，如图5.7(b)所示,图5.7 二叉树结点的存储结构,5.3.1 二叉树的链式存储结构,利用这两种结点结构所得到的二叉树的存储结构分别称为二叉链表（也称“left-right存储法”）和三叉链表在使用二叉链表存储的二叉树中，如果找某个结点的父结点，那么需

34、要从根结点出发依次巡查在三叉链表表示的二叉树中只需要顺着parent指针就能直接找到该结点的父结点,5.3.1 二叉树的链式存储结构,图5.8 图5.5中二叉树的二叉链表存储结构,容易看出，在含有n个结点的二叉链表中有n+1个空链域。可以利用这些空链域存储其它的有用信息，形成其它的链式存储结构。,图5.5 二叉树示例,5.3.1 二叉树的链式存储结构,【算法5.8】 二叉树部分成员函数的实现/ 用二叉链表实现二叉树需要在代码5.1的BinaryTreeNode类中增加两个私有数据成员private:BinaryTreeNode *left; / 指向左子树的指针BinaryTreeNode *

35、right; / 指向右子树的指针templatebool BinaryTree: isEmpty() const / 判定二叉树是否为空树return ( root != NULL ? false : true);templateBinaryTreeNode* BinaryTree:Parent(BinaryTreeNode *current) ,5.3.1 二叉树的链式存储结构,using std:stack;/ 使用STL中的栈stack* aStack;BinaryTreeNode *pointer = root;if (root != NULL / 获得栈顶元素,5.3.1 二叉树的

36、链式存储结构,aStack.pop(); / 栈顶元素退栈 pointer = pointer-rightchild(); / 当前指针指向右孩子/ 创建一棵新树，参数info为根结点元素，leftTree和rightTree是不同的两棵树templatevoid BinaryTree: CreateTree (const T / 原来两棵子树根结点置为空，避免非法访问,5.3.1 二叉树的链式存储结构,templatevoid BinaryTree: DeleteBinaryTree(BinaryTreeNode *root) / 后序周游删除二叉树if (root != NULL) Del

37、eteBinaryTree(root-left); / 递归删除左子树DeleteBinaryTree(root-right);/ 递归删除右子树delete root;/ 删除根结点,5.3.2 完全二叉树的顺序存储结构,二叉树的顺序存储是指按照一定次序，用一组地址连续的存储单元存储二叉树上的各个结点元素。 完全二叉树的顺序表示法： 对于一棵具有n个结点的完全二叉树，可以从根结点起自上而下，从左至右地把所有的结点编号，得到一个足以反映整个二叉树结构的线性序列。线性序列里存储的结点就是按照层次周游二叉树得到的排列。,复习：二叉树的主要性质7,性质7. 对于具有n个结点的完全二叉树，结点按层次由

38、左到右编号，则对任一结点i（0 i n - 1）有 （1）如果i = 0，则结点i是二叉树的根结点；若i0，则其父结点编号是(i - 1)/2。 （2）当2i + 1 n - 1时，结点i的左子结点是2i + 1，否则结点i没有左子结点。 当2i + 2 n - 1时，结点i的右子结点是2i + 2，否则结点i没有右子结点。 （3）当i为偶数且0 i n时，结点i的左兄弟是结点i - 1，否则结点i没有左兄弟。 当i为奇数且i+1 value() = pointer-value() / 如果存在相等的元素则不用插入return ;else if (newpointer-value() value() / 如果待插入结点小于pointer的关键码值if (pointer-leftchild() = NULL) / 如果pointer没有左孩子,