题目内容（请给出正确答案）

[主观题]

对于二叉查找树（Binary Search Tree)，若其左子树非空，则左子树上所有结点的值均小于根结点的值；

对于二叉查找树(Binary Search Tree)，若其左子树非空，则左子树上所有结点的值均小于根结点的值；若其右子树非空，则右子树上所有结点的值均大于根结点的值。左、右子树本身就是两棵二叉查找树。因此，对任意一棵二叉查找树进行(61)遍历可以得到一个结点元素的递增序列。在具有n个结点的二叉查找树上进行查找运算，最坏情况下的算法复杂度为(62)。

A．先序

B．中序

C．后序

D．层序

提问人：网友linux5151 发布时间：2022-01-06

参考答案

查看官方参考答案

如搜索结果不匹配，请联系老师获取答案

您可能会需要：

重置密码查看订单联系客服

安装简答题APP，拍照搜题省时又省心！

更多“对于二叉查找树（Binary Search Tree)，若其…”相关的问题

第1题

实现一个二分查找程序。提交的答案应该是完整的binary_search函数。 bool binary_search(int a[], int key, uint32_t lower, uint32_t upper) { // 请将代码写于此处，答案是完整的binary_search函数 }

点击查看答案

第2题

对于二叉搜索树（Binary Search Tree），以下说法正确的是：

A、二叉搜索树的查找时间效率是

B、二叉搜索树的前序遍历序列，是从小到大排列的

C、二叉搜索树的查找算法与二分法查找是等价的

D、同样一组数据，如果按照不同顺序插入到一棵初始状态为空的二叉搜索树当中，则产生的二叉搜索树形态有可能不同。

点击查看答案

第3题

阅读下列C++程序和程序说明, 将应填入(n)处的字句写在答题纸的对应栏内。

【说明】构造最优二叉查找树。

具有n个结点的有序序列a1, a2, …, an存在于数组元素a[1]、a[2], …, a[n]之中, a[0]未被使用。结点a1, a2, …, an-1, an的查找成功的概率p1, p2, …, pn-1, pn存在于数组元素 p[1]、p[2], …, p[n—1]、p[n]之中, p[0]未用。另外, 查找失败的概率q0, q1, …, qn-1, qn存在于数组元素q[0]、p[1], …, q[n-1]、q[n]之中。算法计算的序列ai+1, ai+2,…, aj-1, aj的最优二叉查找树Tij的代价Cij存在于数组元素c[i][j]之中, Tij的根结点的序号rij存在于r[i][j]之中, 它的权值存在于w[i][j]之中。为了便于内存的动态分配, 统统使用一维数组取代二维数组。

const float MAXNUM=99999. 0; //尽可能大的浮点数

template＜(1)＞

void OPtimal_Binary_Search_Tree(float p[], float q[], Type a[], int n) {

float *C, *W;

c=(2);

w=(3);

int *r;

r=new int[(n+1)*(n+1)];

for(i=0; i＜=n; i++)

{ c[i*(n+1)+i]=0. 0; // 即：c[i][i]=0.0, 用一维数组表示

w[i*(n+1)+i]=q[i]; // 即：w[i][i]=q[i], 用一维数组表示

}

int i, j, k, m, length; // m表示根结点的下标或序号, 范围为0～n

float minimum;

for(length=1; length＜=n; length++) //处理的序列长度由1到n

for(i=0; i＜=n-length; i++){ //i为二叉查找树Tij的起始序号

j=i + length; //j为二叉查找树Tij的终止序号。如：处理序列a1a2a3时,

//相应的二叉查找树为T03, i=0, 而j=3

w[i*(n+1)+j]=(4);

minimum =MAXMUM;

for(k=i+1; k＜=j; k++) //考察以ai+1、ai+2, …, ai为根的情况

if((5)＜minimum)

{ minimum=c[i*(n+1)+k-1]+c[k*(n+1)+j];m=k; }

c[i*(n+1)+j]=w[i*(n+1)+j]+c[i*(n+1)+m-1]+c[m*(n+1)+j];

r[i*(n+1)+j]=m; // r[i][j]=m

}

} //构造好的最优二叉查找树的根结点的序号在r[0][n]中

点击查看答案

第4题

假设以带双亲指针的二叉链表作为-二叉树的存储结构，其结点结构的类型说明如下所示：

typedef char DataType;

typedef struct node{

DataType data;

struct node*lchild,*rchild; //左右孩子指针

struct node*parent; //指向双亲的指针

}BinTNode;

typedef BinTNode*BinTree;

若px为指向非空二叉树中某个结点的指针，可借助该结构求得px所指结点在二叉树的中序序列中的后继。

1. 就后继的不同情况，简要叙述实现求后继操作的方法；

点击查看答案

第5题

假设二叉树采用链式方式存储，t为其根结点，请选择正确的选项将函数int Depth(bintree t) 补充完整，该函数功能为求树t的高度。二叉链表定义如下： typedef struct node{ datatype data; struct node *lchild,*rchild; }bintnode typedef bintnode *bintree; 函数定义如下： int depth(bintree t) { int height,leftTreeHeight,rightTreeHeight; if (t==NULL) ( 1 ) ; else { (2) ; rightTreeHeight =depth(t->rchild); if ( (3) ) height=leftTreeHeight+1; else height= rightTreeHeight +1; } return height; }

A、（1） return 0；

B、（1） return 1；

C、(3) leftTreeHeight >= rightTreeHeight

D、(3) leftTreeHeight <= righttreeheight> E、(2) leftTreeHeight =depth(t->lchild)

F、(2) depth(t->lchild)

点击查看答案

第6题

编写接口及实现类。定义抽象类树（Tree）有树根（Root）、树干（Bolo）、树枝（Branch）、叶子（Leaf）成员，以及树识别的抽象方法realize()。分别定义接口包含树成员的识别方法，如树根接口的方法rootRealize()，定义实现类柳树（Osier）也有树根、树干、树枝、叶子，但没有花（Flower）。并编写测试类进行测试。