文档详情

数据结构 6树与二叉树A.ppt

发布:2017-07-24约小于1千字共26页下载文档
文本预览下载声明
数据结构课程的内容;第6章 树和二叉树( Tree Binary Tree );6.1 树的基本概念;1. 树的定义;2. 若干术语;2. 若干术语(续);3. 树的逻辑结构 ;讨论3:树的链式存储方案应该怎样制定?;解决思路:二叉树;6.2 二叉树;1. 二叉树的定义;2. 二叉树的性质 (3+2);证明: ∵ 二叉树中全部结点数 n=n0+n1+n2(叶子数+1度结点数+2度结点数) 又∵二叉树中全部结点数n=B+1 ( 总进入分支数+根结点 ) (除根结点外,每个结点必有一个直接前驱,即一个分支) 而 总分支数B= n1+2n2 (1度结点射出1个进入分支数,2度结点射出2个) 三式联立可得: n0+n1+n2= n1+2n2 +1, 即n0=n2+1 实际意义:叶子数=2度结点数+1;满二叉树:一棵深度为k 且有2k -1个结点的二叉树。 (特点:每层都“充满”了结点);对于两种特殊形式的二叉树(满二叉树和完全二叉树),还特别具备以下2??性质:;3. 深度为9的二叉树中至少有 个结点。 A)29 B)28 C)9 D)29-1;3. 二叉树的存储结构;讨论:不是完全二叉树怎么办?;二、链式存储结构 用二叉链表即可方便表示。;例: ;4.二叉树的运算;遍历规则———;例1:;先序遍历算法 DLR( TNode *root ) {if (root !=NULL) //非空二叉树 {printf(“%d”,root-data); //访问D DLR(root-lchild); //递归遍历左子树 DLR(root-rchild); //递归遍历右子树 } return(0); };对遍历的分析:;小结
显示全部
相似文档