二叉树及其应用课件

7.1 二叉树的概念7.2 二叉树的存储7.3 二叉树的遍历7.4 线索二叉树7.5 二叉树的应用1基本算法7.6 二叉树的应用2哈夫曼树7.7 二叉树的应用3二叉排序树7.8 二叉树的应用3堆和堆排序,第7章 二叉树及其应用,7.1.1 什么是二叉树7.1.2 特殊的二叉树7.1.3 二叉树的性质,7.1 二叉树的概念,二叉树的定义二叉树是由n(n0)个结点组成的有限集合，其中： 当n0时为空树； 当n0时，有且仅有一个特定的结点，称为二叉树的根，其余结点可分为2个互不相交的子集，其中每一个子集本身又是一棵二叉树，分别称为左子树和右子树。,二叉树的形态,二叉树的基本术语： 父结点：若一个结点有子树，则该结点为父结点（也称 双亲结点）。 孩子结点：若某结点有左子树，则其左子树的根为该结点的左孩子；若其有右子树，则其右子树的根为该结点的右孩子。,结点A为结点B、C的父结点B为A的左孩子，C是A的右孩子；,兄弟结点：同一个结点的孩子。延伸父子关系可得到祖先结点和后代结点关系。 层次：根结点的层次为1，其余结点的层次是其父结点的层次加1。 高度（深度）：二叉树中结点的最大层次数。,该二叉树的深度为4；,度：一个结点的孩子数目是这个结点的度。 叶子结点：度为0的结点。 二叉树的度：二叉树中结点的最大的度。,A、B、C的度均为2； E、F、G的度均为1； D、H、I、J的度为0.,注意：对于结点数>1的二叉树，有且仅有一个结点为二叉树的根，其余结点均为孩子结点，且有左右之分左孩子、右孩子。,例：具有三个结点的二叉树,总结：二叉树的逻辑结构（1）二叉树中任一结点（除根结点外）只有一个父结点；（2）二叉树中任一结点（除叶子结点外）最多有2个孩子结点；（3）结点间为非线性关系。,7.1.1 什么是二叉树 7.1.2 两种特殊的二叉树7.1.3 二叉树的性质,7.1 二叉树的概念,满二叉树 定义：满二叉树是满足如下条件的二叉树： 任一非叶子结点均有两个孩子； 对于二叉树的任一层，若该层上有一个结点有孩子，则该层上所有结点均有孩子。 特点：满二叉树的每层都有最大结点数。,问题：可不可以说，所有非叶子结点均有两个孩子的二叉树为满二叉树？,完全二叉树定义：在满二叉树的最下层从右到左连续地删除若干个结点所得到的二叉树。特点： 叶子结点只可能在层次最大的两层上出现； 满二叉树必为完全二叉树， 而完全二叉树不一定是满二叉树。,例：满二叉树和完全二叉树,7.1.1 什么是二叉树7.1.2 两种特殊的二叉树 7.1.3 二叉树的性质,7.1 二叉树的概念,性质1：在二叉树的第i层上至多有2i-1个结点（i >0） 证明： 用数学归纳法。 归纳基础：当i=1时，整个二叉树只有一根结点，此时2i-1=20=1，结论成立。归纳假设：假设i=k时结论成立，即第k层上结点总数最多为2k-1个。 现证明当i=k+1时， 结论成立： 因为二叉树中每个结点的度最大为2，则第k+1层的结点总数最多为第k层上结点最大数的2倍，即2×2k-1=2(k+1)-1，故结论成立。,性质2：深度为k的二叉树至多有2k-1个结点（k >0） 证明：因为深度为k的二叉树，其结点总数的最大值是将二叉树每层上结点的最大值相加，所以深度为k的二叉树的结点总数至多为,故结论成立。,深度为k的满二叉树有2k-1个结点；或者说，深度为k且有2k-1个结点的二叉树为满二叉树。,性质3：对任一棵非空的二叉树T，如果其叶子数为n0，度为2的结点数为n2，则：n0 = n2 +1 证明：设 总结点数为n，度为1的结点数为n1.则 ： n = n1 + n2 + n0又 度为1的结点有1个孩子，度为2的结点有2个孩子.故 二叉树中孩子结点的总数为n1 + 2n2二叉树中只有根结点不是任何结点的孩子 总结点数 n = n1 + 2n2 + 1即：n1 +2n2 + 1 = n1 + n2 + n0 n0 = n2 +1,例：已知叶子数为20，10个结点有一个左孩子，15个结点有一个右孩子，求该二叉树的总结点数。 解：n0 = 20 n1 = 10 + 15 = 25由于 n0 = n2 + 1 则：n2 = n0 1= 19 n = n0 + n1 + n2 = 20 + 25 + 19 = 64,性质4： 有 n 个结点的完全二叉树( n > 0 )的高度为 +1 证明：假设一棵高度为h的二叉树有n个结点，根据性质2，有 n2h1从而 hlog2(n+1)所以 h +1,性质5：若对满二叉树或完全二叉树按照“从上到下，每层从左到右，根结点编号为1”的方式编号，则编号为 i 的结点，它的两个孩子结点的编号分别为 2i 和 2i +1，它的父结点的编号为 i /2 。,思考题：有100个结点的完全二叉树有多少个叶子结点？ 解：第100个结点的编号为100，其父结点的编号为50，且其父结点的右兄弟（编号为51）没有孩子，即为叶子；所以，叶子结点的编号从51至100，叶子结点有50个。,7.1 二叉树的概念 7.2 二叉树的存储7.3 二叉树的遍历7.4 线索二叉树7.5 二叉树的应用1基本算法7.6 二叉树的应用2哈夫曼树7.7 二叉树的应用3二叉排序树7.8 二叉树的应用3堆和堆排序,第7章 二叉树及其应用,7.2.1 二叉树的顺序存储7.2.2 二叉树的链接存储7.2.3 二叉树的建立,7.2 二叉树的存储,顺序存储将一棵二叉树中的结点，按它们在完全二叉树中的编号顺序，依次存储在一维数组btn+1中；即编号为 i 的结点存储在数组中下标为 i 的元素中。这样，根据性质5可知编号为 i 的结点，其左孩子下标为2i ，其右孩子下标为2i +1，其父结点的下标为i/2。,例：如下二叉树的顺序存储。,a,先对二叉树中结点进行编号;将二叉树存储在数组bt12中。,b,c,d,e,f,g,二叉树顺序存储的特点： 结点间关系蕴含在其存储位置中，无需附加任何信息就能在这种顺序存储结构里找到每个结点的双亲和孩子。 浪费空间，适于存储满二叉树和完全二叉树。,7.2.1 二叉树的顺序存储 7.2.2 二叉树的链接存储7.2.3 二叉树的建立,7.2 二叉树的存储,二叉链表对于任意的二叉树来说，每个结点只有两个孩子，一个双亲结点。我们可以设计每个结点至少包括三个域：数据域、 左孩子域和右孩子：,其中，lchild域指向该结点的左孩子，data域记录该结点的信息，rchild域指向该结点的右孩子。,结点类型描述为：typedef struct node datatype data ;struct node *lchild , *rchild ; bitree ;若定义一个 bitree 类型的指针变量 T，存放根结点的地址，则称 T 为根指针。bitree *T ;这时，一个二叉链表由根指针 T 唯一确定，称 二叉链表 T,例：右图二叉树的二叉链表,三叉链表二叉树的链式存储中，有时，为了便于找到父结点，可以增加一个parent域， parent域指向该结点的父结点。 该结点结构如下：,typedef struct node datatype data;struct node *lchild, *rchild, *parent; JD;,不同的存储结构实现二叉树的操作也不同。如要找某个结点的父结点，在三叉链表中很容易实现；在二叉链表中则需从根指针出发一一查找。可见，在具体应用中，需要根据二叉树的形态和需要进行的操作来决定二叉树的存储结构。,7.2.1 二叉树的顺序存储7.2.2 二叉树的链接存储 7.2.3 二叉树的建立,7.2 二叉树的存储,以建立一个二叉链表的方式生成一个二叉树按完全二叉树的层次顺序，依次输入结点信息建立二叉链表。 算法思想：依次输入结点信息，若其不是虚结点，则建立一个新结点。若新结点是第一个结点，则令其为根结点；否则将新结点作为孩子链接到它的父结点上。 重复 、 ，直至输入信息“”时为止。,具体实现： 为使新结点能正确地与其父结点链接，可设置一个队列，该队列是一个指针类型的数组，保存已输入的结点的地址。 且 front 指向当前与其孩子结点建立链接的父结点，rear 指向当前输入的结点。, 若rear 为偶数，则该结点为父结点的左孩子；若 rear 为奇数，则为父结点的右孩子。若父结点或孩子结点为虚结点，则无需链接。 若父结点与其两个孩子结点链接完毕，则做出队操作：front +1 .初始值：front = 1; rear = 0 ;,a,b,ch=getchar( ); s=NULL; if(ch!=) s=malloc( );s->data=ch; s->lchild=s->rchild=NULL; rear+; Qrear=s; if(rear=1) root=s,if(s,若输入的是虚结点则s为NULL,具体的算法如下： Bitree *Qmaxsize; /队列Q为指针类型 Bitree *creatree( ) /建立二叉树，返回根指针 char ch;int front, rear;bitree *root, *s;root =NULL; /置空二叉树front = 1; rear = 0; /置空队列ch = getchar ( ); /输入第一个字符While ( ch!=#) /不是结束符号时继续s=NULL; /如果输入的是虚结点，则无需为虚结点申请空间,if ( ch ! =) /表示虚结点，不是虚结点时建立新结点 s = malloc( sizeof ( bitree) );s->data=ch; s->lchild=s->rchild=NULL; rear+; Qrear=s; /将虚结点指针NULL或新结点地址入队if (rear = =1) root=s; /输入的第一个结点为根结点else if (s ,if ( rear %2= =1 ) front+; /结点* Qfront的两个孩子已处理完毕front+1ch = getchar( );return root;,7.1 二叉树的概念7.2 二叉树的存储 7.3 二叉树的遍历7.4 线索二叉树7.5 二叉树的应用1基本算法7.6 二叉树的应用2哈夫曼树7.7 二叉树的应用3二叉排序树7.8 二叉树的应用3堆和堆排序,第7章 二叉树及其应用,7.3 二叉树的遍历7.3.1 二叉树遍历的概念7.3.2 二叉树遍历的递归算法 7.3.3 二叉树遍历的非递归算法,二叉树的遍历 对一个二叉树，按某种次序访问其中每个结点一次且仅一次的过程称为二叉树的遍历。 二叉树的遍历算法是二叉树各种运算的基础。,遍历过程的实现分析 1、 若二叉树 T 为空，则遍历结束。 2、 否则，假设二叉树的形态如图所示，且左右子树能分别遍历，则整个二叉树可按如下6种次序分别遍历出来：,(1) 访问根，遍历左子树，遍历右子树（记做DLR）。 (2) 访问根，遍历右子树，遍历左子树（记做DRL）。 (3) 遍历左子树，访问根，遍历右子树（记做LDR）。 (4) 遍历左子树，遍历右子树，访问根（记做LRD）。 (5) 遍历右子树，访问根，遍历左子树（记做RDL）。 (6) 遍历右子树，遍历左子树，访问根（记做RLD）。,