资源描述：
《杨开成-数据结构(C语言)-chapt05.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第5章树和二叉树北京师范大学教育技术学院杨开城一、树的基本概念树的定义任何一个非空树是这样一个包含n个结点的有限集合：⑴唯一存在一个结点R，它没有前驱，被称为根；⑵当n>1时，除了根之外，其他结点可分为m(m>0)个不相交的子集T1,T2,…,Tm，其中每一个子集都是一棵树，它们的根的前驱是R，这些子集被称为R的子树。基本术语根叶子分枝结点内部结点双亲孩子祖先子孙兄弟堂兄弟度层次深度(高度)有序树无序树森林二、二叉树——定义和基本性质(1)定义：二叉树（BinaryTree）是一种特殊的树形结构。它的特
2、点是每个结点最多有两个子树，而且子树分左右，不能任意颠倒，我们通常称之为左子树和右子树。二、二叉树——定义和基本性质(2)基本性质：⑴二叉树的第i层最多有2i-1（i≥1）个结点。⑵深度是k的二叉树，最多有2k－1个结点。⑶设任意一棵二叉树中，叶子结点数为n0，度是1的结点(即单枝结点)数为n1，度为2的结点(即双枝结点)数为n2，则有：n0=n2+1。⑷具有n个结点的完全二叉树的深度是⑸对于一个n个结点的完全二叉树，自上而下、自左向右给结点编号，根结点编号为1。如果已知某结点编号是i，那么①如果i=1
3、，那么结点是根，如果i＞1，那么它的双亲是i/2,即②如果2i＞n，那么该结点没有左孩子，否则它的左孩子是2i；③如果2i+1＞n，那么该结点没有右孩子，否则它的右孩子是2i+1。二、二叉树——存储结构(1)1．二叉树的顺序存储#defineN50/*最大结点数*/typedefelemtypeSQBTREE[N+1];/*数组0号单元空闲，不存放结点*/二、二叉树——存储结构(2)2．二叉树的链式存储二叉链表类型定义：typedefstructbtreenode{chardata;/*数据域可以是任意
4、类型*/structbtreenode*lchild,*rchild;/*指向左右孩子的指针*/}BTREENODE,*BTREENODEPTR,*BTREE;三叉链表类型定义：typedefstructbtreenode{chardata;structbtreenode*lchild,*rchild;structbtreenode*parent;/*指向双亲的指针*/}PBTREENODE,*PBTREENODEPTR,*PBTREE;二、二叉树——建立与销毁(1)1．二叉树的建立——以广义表字符串作
5、为输入例子：A（B（D（,H（J,））,E（,I））,C（F,G））【算法思想】从左向右扫描广义表字符串，我们会遇到这样几种字符：①字母，字母代表结点，遇到字母时，当然要建立结点。需要设定一个栈，将所有左右孩子没有生成完毕的结点保存起来。当前结点的双亲必然是栈顶结点。②左括号，左括号前面一定是一个字母。因此遇到左括号时，意味着要生成前面字母结点的左右孩子，这时要将前面字母的结点入栈。③逗号，逗号的前面是某个结点的左孩子，后面是某个结点的右孩子。④右括号，右括号意味着某个结点的左右孩子都生成完毕，这个结点
6、一定位于栈顶。这时需要出栈操作。二、二叉树——建立与销毁(2)typedefBTREENODEPTRelemtype;BTREECreateBtree1(char*str){/*字符串str是广义表字符串，以它作为输入数据，返回建立的二叉树*/BTREEroot=NULL;/*二叉树根结点指针*/BTREENODEPTRp;inttag,i,len;intmark;/*记录扫描到的字符类型，1代表字母,2代表(,3代表逗号,4代表)*/SQSTACKs;/*栈中存放左右孩子为生成完毕的结点*/if(st
7、r[0]==0)returnroot;/*广义表是空，返回NULL*/root=(BTREENODEPTR)malloc(sizeof(BTREENODE));/*生成根结点*/if(root==NULL)returnroot;/*假设str[0]是字母*/root->data=str[0];root->lchild=root->rchild=NULL;len=strlen(str);/*初始化栈，容量是字符串的长度*/InitSqstack(&s,len);二、二叉树——建立与销毁(3)p=root;
8、/*p指向当前生成的结点*/mark=1;/*标明扫描到字母*/for(i=1;str[i]!=0;i++)/*开始从左向右扫描字符串*/switch(str[i]){case'(':if(mark==2)returnNULL;/*连续出现（,非法*/mark=2;/*扫描到左括号*/Push(&s,p);/*将当前结点入栈*/tag=0;/*标明准备生成左孩子*/break;case')':mark=4;/*扫描到右括号*//*栈顶结点左
