证:设有n个结点的k叉树的深度为h,若该树h-1层都是满的,即每层有最大结点数 -1(1≤i≤h-1),且其余结点都落在第h层,则该树的深度达最小,如图6.11所示:
c错在有序树不一定是二叉树,有序只是子树的相对保持有序,并没有严格定义具体那颗子树就是第几颗子树
结点的出度(od):结点拥有的非空子树数目
树的度(td):树中结点出度的最大值
例题:在下列情况中,可称为二叉树的是( b )
结点的度:该结点的出度
例如 在下述结论中,正确的是( d )【南京理工大学 1999 一、4 (1分)】
①只有一个结点的二叉树的度为0; ②二叉树的度为2; ③二叉树的左右子树可任意交换;④深度为k的完全二叉树的结点个数小于或等于深度相同的满二叉树
森林(或树林):m(m≥0) 涉及哪些方面棵互不相交的有序树的有序集合
a.每个结点至多有两棵子树的树 b. 哈夫曼树 c.每个结点至多有两棵子树的有序树 d. 每个结点只有一棵右子树 e.以上答案都不对
有序树和无序树:若树中任一结点的各子树从左到右有序,则该树为有序树(强调子树的次序),否则为无序树(只强调各子树之间相对有序,而并不像二叉树那样,当只有一个子树是要么是左子树要么是右子树而在有序树中,只有一个子树的有序树就不唯一了)
a.二叉树的度为2 b.一棵二叉树的度可以小于2
有关二叉树下列说法正确的是( b )【南京理工大学 2000 一、11 (1.5分)】
深度=h(h≥1)的k(k>1)叉树至多有( -1)/(k-1)个结点
第六章
c.二叉树中至少有一个结点的度为2 d.二叉树中任何一个结点的数据结构主要是做什么度都为2
结点的入度(id):指向结点的分支(或有向弧、指针)的数目
包含n(n≥0)个结点的k(k>1)叉树的最小深度为:
a.①②③ b.②③④ c.②④ d.①④