资源描述：
《《叉树续》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、1第六章树和二叉树26.1树的类型定义6.2二叉树的类型定义6.3二叉树的存储结构6.4二叉树的遍历6.5线索二叉树6.6树和森林的表示方法6.7树和森林的遍历6.8哈夫曼树与哈夫曼编码36.3二叉树的存储结构（续）6.3二叉树的表示法二叉树数组表示法二叉树结构数组表示法二叉树链表结构表示法46.3.1二叉树数组表示法一颗高度为h的二叉树，拥有最大的节点数为2h-15可以发现二叉树有很好的顺序性：左子树是父节点乘以2右子数是父节点乘以2加16.3.1二叉树数组表示法通过这样的规则，我们可以使用一位数组btree代表这颗树，其长度是2MAX-1，MAX是最大可能的层数。6创建二叉树
2、结点数据的策略有三个，如下所示：将第一个要创建的元素插入成为跟结点；将元素值与结点值进行比较，如果元素值大于结点值，将此元素值送往结点的右子结点，如果右子结点并不是空的，需要重复比较，否则创建结点将元素值插入。如果元素值小于结点值，将此元素送往结点的左子结点，如果左子结点不是空的，需要重复比较，否则创建结点将元素值插入。7实例（二叉查找树）：BinarySearchTree二叉树结点值输入的数据顺序是5,6,4,8,2,3,7,1,9.按照上述策略创建二叉树，如下所示89/*========================================*//*程式实例:7_3_
3、1.c*//*二叉树的数组表示法*//*========================================*//*----------------------------------------*//*建立二叉树*//*----------------------------------------*/voidcreatebtree(int*btree,int*data,intlen){intlevel;/*树的阶层*/inti;btree[1]=data[1];/*建立根节点*/for(i=2;i<=len;i++)/*用回路建立其它节点*/{level=1;/*
4、从阶层1开始*/while(btree[level]!=0)/*是否有子树*/{if(data[i]>btree[level])/*是左或右子树*/level=level*2+1;/*右子树*/elselevel=level*2;/*左子树*/}btree[level]=data[i];/*存入节点数据*/}}10/*----------------------------------------*//*主程式:建立数组的二叉树.*//*----------------------------------------*/voidmain(){intbtree[16];/*二叉树数
5、组*//*二叉树节点数据*/intdata[10]={0,5,6,4,8,2,3,7,1,9};inti;for(i=1;i<16;i++)/*清除二叉树数组*/btree[i]=0;createbtree(btree,data,9);/*建立二叉树*/for(i=1;i<16;i++)/*列出二叉树内容*/printf("%2d:[%d]",i,btree[i]);}结论的输出图形表示：二叉树的数组表示法可以使用在所有的二叉树。前面例子中的二叉树的空间使用率已经相当理想了，但是对于下面的二叉树，还是按照原来的方法就不理想了。11产生的问题与解决方法产生的问题如果使用二叉树数
6、组表示法，那么只使用不到三分之一的数组元素，存储空间浪费严重而且是顺序表示，二叉树结点的插入与删除必须移动相当多的元素才能完成。解决方法可以使用下面各节的二叉树表示法来解决。126.3.2二叉树结构数组表示法二叉树的特征是每一个结点至多拥有两个子结点，所以可以声明结构存储树的结点，这个结点至少拥有三个数据项，数据项存放结点数据，另外两项存储指向左子树和右子树的数据索引，如下图13二叉树使用的结构声明structtree{intdata;intleft;intright;};typedefstructtreetreenode;treenodebtree[15];14上述声明最有一行
7、的结构数组就是存储二叉树的各结点。结点的数据安排是将跟结点放在索引0，字段变量left和right分别指向跟结点左、右子树的索引值，如果没有子树变量left和right为-1.例如：一颗二叉树和其结构数组表示法，如图所示15接着我们从跟结点来看这颗二叉树。结构数据索引0表示这颗树的树根，先从左子树开始其字段left是1，数据索引1表示是其左子结点。再看右子树，字段right是2，数据索引2是其右子结点即数据索引2，字段left是-1表示没有左子结点字段right是3表示数据索引3
