6、树与二叉树

《6、树与二叉树》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、§7、树与二叉树1．树和二叉树的基本概念（1）树：树是n个结点的有限集，有且仅有一个根，其余结点为互不相交的子集。（2）度：一个结点拥有的子树数。一棵树中最大的接点度数为这棵树的度。（3）叶子：度为0的结点，又称端结点。（4）孩子：除根结点外，每个结点都是其前驱结点的孩子。（5）双亲：对应孩子结点的上层结点称为这些结点的双亲。（6）兄弟：同一孩子的孩子。（7）结点的层次：从根结点开始算起，根为第一层，根的直接后继结点为第二层，其余各层依次类推。（8）深度：树中结点的最大层次数。（9）森林：是m（m≥0）棵互不相交的树的集合。（10）路径：树中存在结点系列，使得Ki是Ki+1的双亲（1≤i≤n-

2、1）。（11）路径长度：从树根到树中每一结点的路径长度之和。1．树和二叉树的基本概念（12）二叉树：或是空集或是由互不相交的子集构成。二叉树的性质如下：第i层上结点数目最多为2i-1(i≥1)。深度为h的二叉树至多有2h-1(h≥1)个结点。在任意二叉树中，若叶子结点（终端结点）数为n0，则度为2的结点数n2为n0-1。（13）满二叉树：深度为K，且存在2K-1个结点的二叉树。（14）完全二叉树：至多只有最下面两层上的结点度数可以小于2，并且最下层结点都集中在该层最左边的位置。（15）平衡二叉树：或是一棵空树，或是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之

3、差的绝对值不超过1。2．二叉树的存储结构（1）顺序存储结构对于完全二叉树，从上层到下层，每层从左到右存储。对于非完全二叉树，也按完全二叉树的形式来存储，增加空结点。（2）链式存储结构链式存储结构每个结点的链结构为：类型定义如下：typedefstructBtreeNode{elemtypeData;structBTreeNode*LChild;structBTreeNode*RChild;}nodetype;LChildDataRChild3．二叉树的基本操作二叉树的基本操作有：（1）Initiate(bt)：建立一棵空二叉树。（2）Create(x,lbt,rbt)：生成一棵以x为根结点的数

4、据域信息，以lbt和rbt为左、右子树的二叉树。（3）InsertL(x,Parent)：将数据域信息为x的结点插入到二叉树中，插入位置是结点Parent的左孩子结点，如结点Parent原来有左孩子结点，则结点Parent原来的左孩子结点作为结点x的左孩子结点。（4）InsertR(x,Parent)：插入右孩子结点。（5）DeleteL(bt,Parent)：在二叉树bt中删除结点Parent的左子树。（6）DeleteR(bt,Parent)：在二叉树bt中删除结点Parent的右子树。（7）Search(bt,x)：在二叉树bt中查找查找数据元素为x的结点。（8）Traverse(bt)

5、：按某种方式遍历二叉树bt。4．二叉树的遍历二叉树的遍历根据访问根结点的次序可分为先序、中序和后序。（1）先序遍历（根—左—右）先访问根结点，然后遍历左子树，最后遍历右子树。（2）中序遍历（左—根—右）先遍历左子树，然后访问根结点，最后遍历右子树。（3）后序遍历（左—右—根）先遍历左子树，然后遍历右子树，最后访问根结点。5．树、森林与二叉树的转换树、森林与二叉树之间存在一一对应关系。（1）树转换为二叉树先将所有兄弟结点之间加一连线。对于每一个结点，除保留与其长子连线外，去掉所有其它连线。（2）森林换为二叉树先将森林中每一棵树变成二叉树。将二叉树的根结点视为兄弟，从左到右连接。6．树的存储结构（

6、1）双亲链表表示法为每一个结点附设一个指向双亲的指针Parent，置根结点的Parent为-1。（2）孩子链表表示法为树中每一个结点设置一个孩子链表，将些结点及相应的孩子链表的头指针存放在一个向量中。（3）孩子兄弟链表表示法每个结点附加两个分别指向该结点最左孩子和右邻兄弟的指针。7、二叉树算法的C程序实现——定义、函数声明#defineelemtypeint#defineMAXNODE100typedefstructBTreeNode{elemtypeData;structBTreeNode*LChild;structBTreeNode*RChild;}nodetype;intInitiate

7、(nodetype**bt);//1、初始化建立二叉树bt的头结点nodetype*Create(elemtypex,nodetype*lbt,nodetype*rbt);//2、生成一棵以x为根结点的数据域值，以lbt和rbt为左右子树的二叉树nodetype*InsertL(elemtypex,nodetype*Parent);//3、在二叉树的结点Parent的左子树插入结点数据元素xnod