树和图.ppt

树和图 西安交通大学计教中心 ctec.xjtu.edu.cn 树的递归定义: 树是由n个具有相同特性的数据元素组成的集合。若n=0，则称其为空树。一棵非空树T必须满足：1）其中有一个特定的元素称为T的根root。 2）除根以外的集合可被划分为m个不相交的子集T1，T2，…，Tm，其中每个子集都是树。它们称为根root的子树。 与树相关的术语 ? 结点：在树结构中一般把数据元素及其若干指向子树的分支称为结点。 ? 结点的度：结点拥有的非空子树的个数。 ? 树的度：树中所有结点的度的最大值。 ? 叶子结点：没有非空子树的结点。 ? 分支结点：至少有一个非空子树的结点。 ? 孩子结点和父结点：某结点所有子树的根结点都称为该结点的孩子结点，同时该结点也称为其孩子结点的父结点。 ? 兄弟结点：具有相同父结点的结点互为兄弟结点。 ? 结点的层次：根结点的层次为1,其子结点的层次为2。依次类推，子结点的层次总比父结点多一层。 ? 树的深度：树中结点所在的最大层次。 ? 有序树和无序树：将树中各结点的子树看成自左向右有序的，则称该树为有序树。否则称为无序树。 ? 森林：由零棵或有限棵互不相交的树组成的集合。 二叉树的定义 二叉树可以是空树，当二叉树非空时，其中有一个根元素，余下的元素组成两个互不相交二叉树，分别称为根的左子树和右子树。二叉树是有序树，也就是说任意结点的左、右子树不可交换。而一般树的子树间是无序的。 特殊形式的二叉树 满二叉树：当二叉树每个分支结点的度都是2，且所有叶子结点都在同一层上，则称其为满二叉树。完全二叉树：从满二叉树叶子所在的层次中，自右向左连续删除若干叶子所得到的二叉树被称为完全二叉树。满二叉树可看作是完全二叉树的一个特例。 二叉树有下列重要性质： （1）在二叉树的第k层上至多有2k-1个结点(k≥1) 证明：当k=1时，命题显然成立。假定k=n-1时命题成立，则第n层（k=n）的结点数最多是第n-1层的2倍，所以第n层最多有2*2n-2=2n-1个结点。命题成立。 （2）深度为h的二叉树上至多含2h-1个结点(h≥1) 证明：根据性质1容易知道深度为h的二叉树最多有20+21+…+2h-1个结点，即最多有2h-1个结点。 （3）包含n(n0)个结点的二叉树总的分支数为n-1 证明：二叉树中除了根结点之外每个元素有且只有一个父结点。在所有子结点与父结点间有且只有一个分支，即除根外每个结点对应一个分支，因此二叉树总的分支数为n-1。 （4）任何一棵二叉树，若含有n0个叶子结点、n2个度为2的结点，则必存在关系式n0=n2+1 证明：设二叉树含有n1个度为1的结点，则二叉树结点总数显然为： n0 + n1 + n2 （2-2） 再看看树的分支数，n2个度为2的结点必然有2n2个分支，n1个度为1的结点必然有n1个分支。又因为除根结点外，其余每个结点都有一个分支进入。因此二叉树的分支数加1就是结点总数。即结点总数为： 1 + n1 + 2n2 （2-3） 由（2-2）（2-3）两式可知：n0=n2+1 （5）具有n个结点的完全二叉树的深度为[log2(n)]+1 证明：假设二叉树的深度为h，则必有2h-1-1n≤2h-1，于是有2h-1n+1≤2h，也就是 2h-1≤n2h，从而得到h-1≤log2(n)h，于是h=[log2(n)]+1。 （6） 若对含n个结点的完全二叉树从上到下、从左至右进行1至n的编号，则对二叉树中任意一个编号为i的结点： ① 若i=1，则该结点是二叉树的根，无父结点。否则，编号为[i/2]的结点为其父结点； ② 若2in，则该结点无左孩子。否则，编号为2i的结点为其左孩子结点； ③ 若2i+1n，则该结点无右孩子。否则，编号为2i+1的结点为其右孩子结点。 证明通过对i进行归纳即可得证。 二叉树的链式存储 结点定义： struct BinTreeNode { ElemType data; struct BinTreeNode *leftChild, *rightChild; }; 这里leftChild和rightChild分别为某一结点指向其左孩子和右孩子的指针。对于叶子结点或一个新生成的结点而言，其左孩子和右孩子指针都应为空值。 二叉树的常用算法包括：获取根结点指针、判断树是否为空、插入或删除结点、插入或删除子树、二叉树遍历等。 二叉树类可描述如下： class BinTree { public: BinTreeNode *root; //定义根结点指针 BinTree() { root=NULL; } //构造函数，定义空树 //判断树是否为空 bool Is