Question

引入二叉线索树的目的是( )

数据结构题
1.引入线索二叉树的目的是（ ）？2.在有序表（12，24，36，48，60，72，84）中二分查找关键字72时所需进行的关键字比较次数为（ ）？3.树的度是指一棵树上所有结点度的最大值（判断对错）。4.二叉树中度为1的结点数等于度为2的结点数加1（判断对错）。
6阶B_树中的结点最少有（ ）个关键字？

Answer 1

引入线索二叉树的目的是找一个节点的前驱后继的时候,比非二叉线索树方便快捷。
当用二叉链表作为二叉树的存储结构时，因为每个结点中只有指向其左、右儿子结点的指针，所以从任一结点出发只能直接找到该结点的左、右儿子。在一般情况下靠它无法直接找到该结点在某种遍历序下的前驱和后继结点。
如果在每个结点中增加指向其前驱和后继结点的指针，将降低存储空间的效率。
我们可以证明：在n个结点的二叉链表中含有n+1个空指针。因为含n个结点的二叉链表中含有个指针，除了根结点，每个结点都有一个从父结点指向该结点的指针，因此一共使用了n-1个指针，所以在n个结点的二叉链表中含有n+1个空指针。

Answer 2

线索二叉树：二叉树的结点上加上线索的二叉树

Answer 3

1. 找一个节点的前驱后继的时候,比非二叉线索树方便快捷
   

2. 两次

3. 对

4. 对

5. 没有高度，没法算
   

Answer 4

建立线索二叉树，或者说对二叉树线索化，实质上就是遍历一颗二叉树。在遍历过程中，访问结点的草所是检查当前的左，右指针域是否为空，将它们改为指向前驱结点或后续结点的线索。为实现这一过程，设指针pre始终指向刚刚访问的结点，即若指针p指向当前结点，则pre指向它的前驱，以便设线索。
另外，在对一颗二叉树加线索时，必须首先申请一个头结点，建立头结点与二叉树的跟结点的指向关系，对二叉树线索化后，还需建立最后一个结点与头结点之间的线索。
下面是建立中序二叉树的递归算法，其中pre为全局变量。
bithrnodetype
*pre;
bithrtree
inorderthr(bithrtree
t)
{
/*中序遍历二叉树t，并将其中序线索化，pre为全局变量*/
bithrtree
head;
head=(bitthrnodetype
*)malloc（sizeof（bithrtype））;/*设申请头结点成功*/
head->ltag=0;head->rtag=1;/*建立头结点*/
head->rchild=head;/*右指针回指*/
if(！t)head->lchild=head;/*若二叉树为空，则左指针回指*/
else{head->lchild=t;pre=head;
inthreading(t);/*中序遍历进行中序线索化*/
pre->rchild=head;
pre->rtag=1;/*最后一个结点线索化*/
head->rchild=pre;
};
return
head;
}
void
inthreading(bithrtree
p)
{/*通过中序遍历进行中序线索化*/
if(p)
{inthreading(p->lchild);/*左子树线索化*/
if(p->lchild==null)/*前驱线索*/
{p->ltag=1;
p->lchild=pre;
}
if(p->lchild==null)/*后续线索*/
{p->rtag=1;
p->rchild=pre;
}
pre=p;
inthreading(p->rchild);/*右子树线索化*/
}
}