数据结构与程序设计(王丽苹)24二叉树.ppt
5/27/2023,数据结构与程序设计,1,数据结构与程序设计(24)Chapter Binary Tree 二叉树,王丽苹,5/27/2023,数据结构与程序设计,2,Tree,树tree的定义(1)无结点的树 空树(2)非空树 仅有一个根结点 其余结点分为若干 互不相交的子树在树形结构中每个结点最多只有一个前驱，但可有多个后继的结构。它表示了一种具有层次的分支关系。,5/27/2023,数据结构与程序设计,3,subtree,Tree,Root（根）:node without parent(A)Siblings（兄弟）:nodes share the same parentInternal node:node with at least one child(A,B,C,F)External node(leaf):node without children(E,I,J,K,G,H,D)Ancestors of a node:parent,grandparent,grand-grandparent,etc.Descendant of a node:child,grandchild,grand-grandchild,etc.Depth of a node:number of ancestorsHeight of a tree:maximum depth of any node(3)Degree of a node:the number of its childrenDegree of a tree:the maximum number of its node.,Subtree:tree consisting of a node and its descendants,5/27/2023,数据结构与程序设计,4,Tree Properties,PropertyValueNumber of nodes 9Height 4 Root Node ALeaves Interior nodesAncestors of H（G，E，B，A）Descendants of BSiblings of ERight subtree of ADegree of this tree,5/27/2023,数据结构与程序设计,5,Chapter 10 Binary Tree,DEFINITION A binary tree is either empty,or it consists of a node called the root（根）together with two binary trees called the left subtree(左子树)and the right subtree（右子树）of the root.,5/27/2023,数据结构与程序设计,6,二叉树(Binary Tree),二叉树的定义,二叉树的五种不同形态,一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。,5/27/2023,数据结构与程序设计,7,深度(Height)为k，结点至多2k+1-1个，深度为最大层数,第i层结点至多2i个 在本书，层数从0开始计算。,设有n2个2度点则有n2+1个叶片,A,B,C,D,E,F,G,H,I,J,5/27/2023,数据结构与程序设计,8,Binary Tree,满二叉树：如果一棵二叉树的深度为k,结点数2k+1-1,每层结点数都最大，则此二叉树称作满二叉树。完全二叉树：如果一棵二叉树至多只有最下面的两层结点度数可以小于2，其余各层结点度数都必须为2，并且最下面一层的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。即为，满二叉树去掉最下层最右边若干结点,5/27/2023,数据结构与程序设计,9,Binary Tree,5/27/2023,数据结构与程序设计,10,A,B,C,D,E,F,G,H,I,J,完全二叉树,K,L,M,n个结点,深度 k=log2(n)下取整,n个结点,深度为k:2k-1n2k+1-12k n 2k+1k log2n k+1k=log2(n)下取整,1个结点深度为0,2-3个结点深度为1,4-7个结点深度为2,8-15个结点深度为3,5/27/2023,数据结构与程序设计,11,0,1,2,3,4,5,6,7,8,9,完全二叉树,10,11,12,结点i的左子结点是2i+1 右子结点是2i+2,结点i的父结点是(i-1)/2堆排序利用了这种特点。,5/27/2023,数据结构与程序设计,12,10.1.2 Traversal of Binary Trees,With preorder traversal（前序）we first visit a node,then traverse its left subtree,and then traverse its right subtree.With inorder traversal（中序）we first traverse the left subtree,then visit the node,and then traverse its right subtree.With postorder traversal（后序）we first traverse the left subtree,then traverse the right subtree,and finally visit the node.,5/27/2023,数据结构与程序设计,13,写出这棵树的前序，后序，中序访问的结果,5/27/2023,数据结构与程序设计,14,前序遍历(Preorder Traversal),前序遍历二叉树算法的框架是若二叉树为空，则空操作；否则访问根结点(V)；前序遍历左子树(L)；前序遍历右子树(R)。遍历结果-+a*b-c d/e f,5/27/2023,数据结构与程序设计,15,中序遍历二叉树算法的框架是：若二叉树为空，则空操作；否则中序遍历左子树(L)；访问根结点(V)；中序遍历右子树(R)。遍历结果 a+b*c-d-e/f,中序遍历(Inorder Traversal),表达式语法树,5/27/2023,数据结构与程序设计,16,后序遍历(Postorder Traversal),后序遍历二叉树算法的框架是若二叉树为空，则空操作；否则后序遍历左子树(L)；后序遍历右子树(R)；访问根结点(V)。遍历结果a b c d-*+e f/-,5/27/2023,数据结构与程序设计,17,完全二叉树的数组表示 一般二叉树的数组表示,二叉树的表示 1.数组表示,5/27/2023,数据结构与程序设计,18,二叉树的表示2.链表表示,5/27/2023,数据结构与程序设计,19,10.1.3 二叉树的链式实现,5/27/2023,数据结构与程序设计,20,Implement of Binary Tree链式实现方式-节点的数据结构,template struct Binary_node/data members:Entry data;Binary_node*left;/指向左孩子的指针Binary_node*right;/指向右孩子的指针/constructors:Binary_node();/默认的不带参数的构造函数Binary_node(const Entry,5/27/2023,数据结构与程序设计,21,Implement of Binary Tree链式实现方式-节点的实现,#include Binary_node.htemplate Binary_node:Binary_node()left=NULL;right=NULL;template Binary_node:Binary_node(const Entry,5/27/2023,数据结构与程序设计,22,二叉树的基本方法,1.遍历void preorder(void(*visit)(Entry/求高度,5/27/2023,数据结构与程序设计,23,二叉树的基本方法,3.更新操作void insert(Entry/构造函数。,5/27/2023,数据结构与程序设计,24,Implement of Binary Tree链式实现的头文件,#include Binary_node.cpptemplate class Binary_tree public:Binary_tree();bool empty()const;void preorder(void(*visit)(Entry,5/27/2023,数据结构与程序设计,25,Implement of Binary Tree二叉树定义的头文件,protected:/Add auxiliary function prototypes here.void recursive_preorder(Binary_node*sub_root,void(*visit)(Entry,5/27/2023,数据结构与程序设计,26,Implement of Binary Tree构造函数的实现,template Binary_tree:Binary_tree()/*Post:An empty binary tree has been created.*/root=NULL;count=0;template bool Binary_tree:empty()const/*Post:A result oftrue is returned if the binary tree is empty.Otherwise,false isreturned.*/return root=NULL;,5/27/2023,数据结构与程序设计,27,Implement of Binary Tree二叉树的前序遍历,template void Binary_tree:preorder(void(*visit)(Entry,5/27/2023,数据结构与程序设计,28,Implement of Binary Tree二叉树的中序遍历,template void Binary_tree:inorder(void(*visit)(Entry,5/27/2023,数据结构与程序设计,29,Implement of Binary Tree二叉树的后序遍历,template void Binary_tree:postorder(void(*visit)(Entry,5/27/2023,数据结构与程序设计,30,Implement of Binary Tree求二叉树的高度,假设当前二叉树为一棵完全二叉树，则如何求其高度？启发，根据前面的讨论，设二叉树的节点数为n,，完全二叉树的高度为：log2n的值下取整。则有2K=n;k为满足条件的最大整数实现方法：K=0；tmp=20当tmp=n时，K=K+1，tmp=tmp*2；/2K退出循环时K的值，即为完全二叉树的高度。,5/27/2023,数据结构与程序设计,31,Implement of Binary Tree求二叉树的高度,template int Binary_tree:size()constreturn count;template/该方法适用于完全二叉树，当前的对象必须为完全二叉树。int Binary_tree:height()const int count=size();if(count=0)return 0;int tmp=1;for(int k=0;tmp=count;k+)tmp*=2;return k;,5/27/2023,数据结构与程序设计,32,插入：新插入的节点在最后一个叶子结点之后,0,1,2,3,4,5,6,7,8,结点i的左子结点是2i+1 右子结点是2i+2,结点i的父结点是(i-1)/2,5/27/2023,数据结构与程序设计,33,插入：新插入的节点在最后一个叶子结点之后,如何在完全二叉树的末尾插入一个新的节点：只需要知道插入位置的父节点的信息即可，即父节点的指针。如何获取父节点的信息：必须从根节点一层一层访问，获取父节点的信息。实现:(1)当前插入点的编号tmpcount=size();(2)计算tmpcount是左孩子还是右孩子。将信息入栈保存;(3)计算tmpcount的父节点，tmpcount=(tmpcount-1)/2;(4)当tmpcount不是根节点，继续步骤(2);经过上述计算之后，栈内保存了从根到插入点的路径。(5)依次将信息出栈，逐一访问路径上的节点，获取父节点的指针。(6)将当前信息插入到树中。,5/27/2023,数据结构与程序设计,34,插入：新插入的节点在最后一个叶子结点之后,template void Binary_tree:insert(Entry,5/27/2023,数据结构与程序设计,35,Implement of Binary Tree,MyStack numbers;int item=0;int tmpcount=size();while(tmpcount0)if(tmpcount%2=0)/the node is right child numbers.push(2);/2 stand for right child else/the node is left child numbers.push(1);/1 stand for left child tmpcount=(tmpcount-1)/2;/get to the parent,5/27/2023,数据结构与程序设计,36,Implement of Binary Tree,Binary_node*current=root;while(numbers.size()1)/出栈，直到栈内剩余一个节点numbers.top(item);if(item=1)current=current-left;if(item=2)current=current-right;numbers.pop();numbers.top(item);/链接新节点if(item=1)current-left=new Binary_node(x);if(item=2)current-right=new Binary_node(x);count+;,5/27/2023,数据结构与程序设计,37,Implement of Binary Tree,template void print(Entry,5/27/2023,数据结构与程序设计,38,Implement of Binary Tree,目录Binary_Tree下例程Tree size is:10Tree height is:4Preorder:0 1 3 7 8 4 9 2 5 6inorder:7 3 8 1 9 4 0 5 2 6Postorder:7 8 3 9 4 1 5 6 2 0,0,1,2,3,4,5,6,7,8,9,5/27/2023,数据结构与程序设计,39,课后作业 P441,（1）E5 用递归的方法计算二叉树的叶子节点数。（2）E6 用递归的方法计算二叉树的高度。,
