02331数据结构
对于一棵具有n个结点，其高度为h的任何二叉树，进行任一种次序遍历的时间复杂度均为O(h)。
题目
对于一棵具有n个结点，其高度为h的任何二叉树，进行任一种次序遍历的时间复杂度均为O(h)。
相似问题和答案
第1题：
● 对于n 个元素的关键字序列{k1,k2,…,kn}， 若将其按次序对应到一棵具有 n 个结点的完全二叉树上， 使得任意结点都不大于其孩子结点(若存在孩子结点)， 则称其为小顶堆。根据以上定义， （43） 是小顶堆
第2题：
关于满二叉树、完全二叉树有以下说法：
①满二叉树不仅是一种特殊形态的二叉树，而且是一种特殊的完全二叉树。
②具有n个结点的满二叉树的高度为
+1。
③具有n个结点的完全二叉树的高度为+1。
④具有n个结点的满二叉树的高度为log2(n+1)。
⑤具有n个结点的满二叉树共有叶子结点
。
其中______最全面、最准确。
A．①②④
B．③④⑤
C．①③④⑤
D．全对
解析：若二叉树的每一层的结点数都是最大结点数，也就是说每一层都是满的，那么此时的二叉树便成为一棵满二叉树。若二叉树除最后一层外都是满的，而且最后一层的结点都连续紧挨靠左，那么称此时的二叉树为完全二叉树。所谓的“完全”，指的是在给其结点按层次自上而下、同一层自左至右编号时，n个结点(设完全二叉树结点总数为n)与同深度的满二叉树中编号从1到n的结点一一对应。因此，①正确。显然，③是正确的。注意到，满二叉树是特殊的二叉树，因此②也正确。值得指出的是，②和③中的n分别满足不同的条件，因此，②和③都正确。设具有n个结点的满二叉树的高度为h，那么根据二叉树的性质有n=2h-1，从而有h=log2(n+1)，叶子结点的个数为n-2h-1-1=2h-1=(n+1)/2，因此④和⑤都正确。值得指出的是②和④是等价的，只是表述不同而已。综上所述，由于题干要求选最全面、最准确的，因此选D。
第3题：
A.高度等于其结点数
B.任一结点无左孩子
C.任一结点无右孩子
D.空或只有一个结点
第4题：
设n/m为一棵二叉树上的两个结点，在中序遍历中，n在m的前面的条件是（）。
正确答案:n在m的上方
第5题：
B.(1)
C.(2)
D.(1)、(2)都错
第6题：
对于n个元素的关键字序列{k1，k2，…，kn}，若将其按次序对应到一棵具有n个结点的完全二叉树上，使得任意结点都不大于其孩子结点(若存在孩子结点)，则称其为小顶堆。根据以上定义，(43)是小顶堆。
A．
B．
C．
D．
解析：本题考查排序方法中堆排序的基础知识。，对于n个元素的关键字序列{k1，k2，…，kn}，当且仅当满足下列关系时称其为堆：①ki≤k2i且ki≤k2i+1或者②kik2i且kik2i+1其中，1≤i≤|n/2|，满足①式称为小顶堆，满足②式称为大顶堆。显然，题目中选、项A中25与23和51之间的关系不满足小顶堆的定义；选项B中51与63和25之间、 55与23之间的关系不满足小顶堆的定义；选项C的情况与B类似。选项D是小顶堆。
第7题：
某二叉树T有n个结点，设按某种顺序对T中的每个结点进行编号，编号值为1、2、…、n，且有如下性质：T中任一结点v，其编号等于左子树上的最小编号减1，而v的右子树的结点中，其最小编号等于 v左子树上的最大编号加1。此二叉树是按( )顺序编号的。
A．前序遍历
B．中序遍历
C．后序遍历
D．按层次遍历
解析：根据节点v的右子树的结点中，其最小编号等于v左子树上的结点的最大编号加1，可以断定是前序遍历。
第8题：
某二叉树T有n个结点，设按某种顺序对T中的每个结点进行编号，编号值为1,2…,n，且有如下性质：T中任一结点v，其编号等于左子树上的最小编号减1，而v的右子树的结点中，其最小编号等于v左子树上的结点的最大编号加1。此二叉树是按( )顺序编号的。
A．前序遍历
B．中序遍历
C．后序遍历
D．按层次遍历
解析：根据结点v的右子树的结点中，其最小编号等于v左子树上的结点的最大编号加 1，可以断定是前序遍历。
第9题：
第10题：
对于一棵具有n个结点的二叉树，其相应的链式存储结构中共有（）个指针域为空。
正确答案:n+1