数据结构 6树与二叉树A.ppt
文本预览下载声明
数据结构课程的内容;第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); };对遍历的分析:;小结
显示全部