自考——数据结构第四章02142.pptVIP

第四章 树和二叉树;第四章 树和二叉树; 树型结构是一类重要的非线性结构。树型结构是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。树结构在客观世界中是大量存在的，例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程等等。; 二、树的逻辑表示 ▲一般表示法(直观表示法)：?;三、树的基本术语;●结点的层次——从根算起，根为第一层，其孩子在第二层, ….， L层上任何结点的孩子都在L+1层上。;求根Root(T):求树T的根结点； 求双亲Parent(T,X):求结点X在树T上的双亲结点；若X是树T的根或X不在T上，则结果为一特殊标志； 求孩子Child(T,X,i):求树T上结点X的第i个孩子结点；若X不在T上或X没有第i个孩子，则结果为一特殊标志； 建树Create(X,T1,…,Tk),k1:建立一棵以X为根，以T1,…,Tk为第1,…,k棵子树的树； 剪枝Delete(T,X,i):删除树T上结点X的第i棵子树；若T无第i棵子树，则为空操作； 遍历Traverse Tree(T):遍历树，即访问树中每个结点，且每个结点仅被访问一次。; 二叉树在树结构的应用中起着非常重要的作用，因为二叉树有许多良好的性质和简单的物理表示，而任何树都可以与二叉树相互转换，这样就解决了树的存储结构及其运算中存在的复杂性。; 2、特点： ①二叉树可以是空的，称空二叉树； ②每个结点最多只能有两个孩子； ③子树有左、右之分且次序不能颠倒。; 二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。下图列出二叉树的5种基本形态，图(c) 和（d）是不同的两棵二叉树。;初始化Initiate(BT):建立一棵空二叉树，BT=?。 求双亲Parent(BT,X):求出二叉树BT上结点X的双亲结点，若X是BT的根或X根本不是BT上的结点，运算结果为NULL。 求左孩子Lchild(BT,X)和求右孩子Rchild(BT,X)：分别求出二叉树BT上结点X的左、右孩子；若X为BT的叶子或X不在BT上，运算结果为NULL。 建二叉树Create(BT):建立一棵二叉树BT。 先序遍历PreOrder(BT)(根、左、右):按先序对二叉树BT进行遍历，每个结点被访问一次且仅被访问一次，若BT为空，则运算为空操作。;中序遍历InOrder(BT)（左、根、右）:按中序对二叉树BT进行遍历，每个结点被访问一次且仅被访问一次，若BT为空，则运算为空操作。 后序遍历PostOrder(BT)（左、右、根）:按后序对二叉树BT进行遍历，每个结点被访问一次且仅被访问一次，若BT为空，则运算为空操作。 层次遍历LevelOrder(BT):按层从上往下，同一层中结点按从左往右的顺序，对二叉树进行遍历，每个结点被访问一次且仅被访问一次，若BT为空，则运算为空操作。 ;1、性质1： 在二叉树的第i(i=1)层上至多有2i-1个结点。; ;1; 符号[x]表示不大于x的最大整数。 假设此二叉树的深度为k，则根据性质2及完全二叉树的定义得到：2k-1－1n=2k-1 或 2k-1=n2k 取对数得到：k－1log2nk 因为k是整数。所以 ：k＝[log2n]＋1。; 5、性质5： 对有n个结点的完全二叉树的结点按层编号 （从第1层到第[log2n]+1层，每层从左到右), 则对任一结点i（1≤i≤n),有： （1）如果i＝1，则结点i无双亲，是二叉树的根； 如果i1，则i的双亲Parent(A)是结点[i/2]; （2）如果2*i≤n，则其左孩子是结点2*i, 否则，结点i无左孩子且为叶子结点； （3）如果2*i＋1≤n，则其右孩子是结点2*i＋1， 否则，结点i无右孩子。;思考题:;1. 树最适合用来表示( ? ?? ) ?? A.有序数据元素 ??B.无序数据元素 ?? C.元素之间具有分支层次关系的数据 ? ? D.元素之间无联系的数据 2. 根据定义，树的叶子结点其度数（　　　） A. 必大于0 B. 必等于0 C.必等于1 D.必等于2 3. 对一棵有100个结点的完全二叉树按层序编号，则编号为49的结 点，它的左孩子的编号为（ ）