数据结构,第六章 二叉树,课件函试题.ppt

第六章 二叉树 6.1 二叉树的定义与性质 6.2 二叉树的基本操作与存储实现 6.3 二叉树的遍历 6.4 线索二叉树 6.5 树和森林 6.6 哈夫曼树（赫夫曼树） 例1：二叉树的第k层的结点数最多为( ). A．2k-1 B.2K+1 C.2K-1 　D. 2k-1 例2：一棵高度为5的二叉树中最少含有__ 个结点，最多含有__个结点； 例3：在一棵非空二叉树中,度为2的结点个数为5,度为0的结点个数 ( ) A．4 B．5 C．6 D．7 例4：9．根据二叉树的定义可知二叉树共有（ ）种不同的形态。 (A) 4 (B) 5 (C) 6 (D) 7 6.2 二叉树的基本操作与存储实现 6.2.1二叉树的存储 1、顺序存储结构 它是用一组连续的存储单元存储二叉树的数据元素。一般 是按照二叉树结点从上至下，从左到右的顺序存储。 对于一般的二叉树，如果仍按从上到下和从左到右的顺 序将树中的结点顺序存储在一维数组中，需添加一些不存在的 空节点，使它变成一个完全二叉树。 结论：显然这种需增加许多空结点才能将一棵二叉树改造成一棵完全二叉树的存储，会造成空间的大量浪费，不宜采用顺序存储结构，满二叉树和完全二叉树比较适合顺序存储。 2、链式存储结构 所谓二叉链表存储结构，是指用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常有下面两种形式： （1）二叉链表存储 链中每个结点由3个域组成，除了数据域外，还有两个指针域，分别用来给出结点的左孩子和右孩子。结点存储结构： 存储二叉树经常用二叉链表法，如下图： 二叉链表也可以带头结点的方式存放，如下图： 二叉链表存储表示为： typedef struct BiTNode { // 结点结构 TElemType data; struct BiTNode *lchild, *rchild; // 左右孩子指针 } BiTNode, *BiTree 结点结构： （2）三叉链表存储 链中每个结点由4个域组成，结点存储结构： 其中，data、lchild以及rchild这三个域和二叉链表结构相同；parent域向该结点双亲结点的指针。这种结构既便于查找孩子结点，又便于查找双亲结点；但是相对于二叉链表，三叉链表增加了空间开销。 三叉链表存储 6.2.2二叉树的基本操作及实现 1、二叉树的基本操作 InitBiTree(bt); //建立一棵空二叉树 Create(x,lbt,rbt); //生成一棵以x为根结点的数据域信息，以二叉树lbt和rbt为左子树和右子树的二叉树。 InsertLChild(bt, x, parent); //将数据信息为x的结点插入到二叉树bt中作为结点parent的左孩子结点。如果原来结点parent原来有左孩子结点，则将结点parent原来的左孩子结点作为结点x的左孩子结点。 DeleteLChild(bt, parent); //在结点bt中删除结点parent的左子树。 Search(bt，x); //在二叉树bt中查找数据元素x。 Traverse(bt); //按某种方式遍历二叉树bt的全部结点。 2、算法实现 int InitBiTree(BiTNode bt); //建立一棵空二叉树 { bt = new BiNode; if(!bt) return 0; //没有存储空间返回0 bt-lchild=NULL; bt-rchild=NULL; return 1; //返回成功代码1 } main(){ BiTree t; Initiate(t); } 二叉树的遍历是按照某种顺序访问二叉树的每个 结点，是每个结点被访问一次且仅被访问一次。 二叉树的三个基本组成单元是：根结点、左子树 和右子树。 假如以L、D、R分别表示遍历左子树、遍历根结 点和遍历右子树，遍历整个二叉树则有DLR、LDR、 LRD、DRL、RDL、RLD六种遍历方案。若规定先左 后右，则只有前三种情况，分别规定为： DLR——先（根）序遍历