资源描述：
《5_树与二叉树》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第5章树和二叉树一、树的基本概念树的定义任何一个非空树是这样一个包含n个结点的有限集合：⑴唯一存在一个结点R，它没有前驱，被称为根；⑵当n>1时，除了根之外，其他结点可分为m(m>0)个不相交的子集T1,T2,…,Tm，其中每一个子集都是一棵树，它们的根的前驱是R，这些子集被称为R的子树。基本术语根叶子分枝结点内部结点度层次深度(高度)双亲孩子祖先子孙兄弟堂兄弟有序树无序树森林2二、二叉树——定义和基本性质(1)定义：二叉树（BinaryTree）是一种特殊的树形结构。它的特点是每个结点最多有两个子树，而且子树分左右，不能
2、任意颠倒，我们通常称之为左子树和右子树。3二、二叉树——定义和基本性质(2)基本性质：⑴二叉树的第i层最多有2i-1（i≥1）个结点。⑵深度是k的二叉树，最多有2k-1个结点。⑶设任意一棵二叉树中，叶子结点数为n0，度是1的结点(即单枝结点)数为n1，度为2的结点(即双枝结点)数为n2，则有：n0=n2+1。⑷具有n个结点的完全二叉树的深度是满二叉树：当一个深度为K的二叉树具有2k-1个结点时，即结点数达到最大时，这个二叉树称为满二叉树。完全二叉树：将一颗满二叉树从底向上，从右到左删除有限个叶子结点并使二叉树的深度仍然为K
3、，这棵二叉树称为完全二叉树。4二、二叉树——定义和基本性质(3)⑸对于一个n个结点的完全二叉树，自上而下、自左向右给结点编号，根结点编号为1。如果已知某结点编号是i，那么①如果i=1，那么结点是根，如果i＞1，那么它的双亲是i/2,即②如果2i＞n，那么该结点没有左孩子，否则它的左孩子是2i；③如果2i+1＞n，那么该结点没有右孩子，否则它的右孩子是2i+1。5二、二叉树——存储结构(1)1．二叉树的顺序存储#defineN50/*最大结点数*/typedefelemtypeSQBTREE[N+1];/*数组0号单元空闲，
4、不存放结点*/6二、二叉树——存储结构(2)2．二叉树的链式存储二叉链表类型定义：typedefstructbtreenode{chardata;/*数据域可以是任意类型*/structbtreenode*lchild,*rchild;/*指向左右孩子的指针*/}BTREENODE,*BTREENODEPTR,*BTREE;三叉链表类型定义：typedefstructbtreenode{chardata;structbtreenode*lchild,*rchild;structbtreenode*parent;/*指向双亲
5、的指针*/}PBTREENODE,*PBTREENODEPTR,*PBTREE;7二、二叉树——建立与销毁(1)1．二叉树的建立二叉树是一个非线性数据结构，但它的建立却需要一个线性的输入序列。方法两种：1）广义表2）以层序遍历的顺序输入二叉树的数据一个二叉树的广义表如何表示：用结点名称为子表名，左右子树作为子表的内容，子树为空时忽略不写。表示二叉树的广义表中的字符排列是有规则的：字母、左括号和逗号都不能连续出现，左右括号是配对的。违反这个规则的广义表是非法的。。例子：A（B（D（,H（J,））,E（,I））,C（F,G））
6、二、二叉树——建立与销毁(2)1．二叉树的建立——以广义表字符串作为输入例子：A（B（D（,H（J,））,E（,I））,C（F,G））【算法思想】从左向右扫描广义表字符串，我们会遇到这样几种字符：①字母，字母代表结点，遇到字母时，当然要建立结点。需要设定一个栈，将所有左右孩子没有生成完毕的结点保存起来。当前结点的双亲必然是栈顶结点。②左括号，左括号前面一定是一个字母。因此遇到左括号时，意味着要生成前面字母结点的左右孩子，这时要将前面字母的结点入栈。③逗号，逗号的前面是某个结点的左孩子，后面是某个结点的右孩子。④右括号，右括
7、号意味着某个结点的左右孩子都生成完毕，这个结点一定位于栈顶。这时需要出栈操作。10课堂练习：1）已知广义表A(B(,D),C(E,))画出其对应的二叉树2）书115页，练一练5.2二、二叉树——建立与销毁(3)typedefBTREENODEPTRelemtype;BTREECreateBtree1(char*str){/*字符串str是广义表字符串，以它作为输入数据，返回建立的二叉树*/BTREEroot=NULL;/*二叉树根结点指针*/BTREENODEPTRp;inttag,i,len;intmark;/*记录扫描
8、到的字符类型，1代表字母,2代表(,3代表逗号,4代表)*/SQSTACKs;/*栈中存放左右孩子为生成完毕的结点*/if(str[0]==0)returnroot;/*广义表是空，返回NULL*/root=(BTREENODEPTR)malloc(sizeof(BTREENODE));/*生成根结点*
