Question

n个结点的线索二叉树中线索的数目为多少？为什么?

Answer 1

在一个具有n个结点的线索二叉树中有n+1个指针是用来作为线索处理的。

因为n个结点的二叉树中有2n个指针，而这些个结点（除根结点）都有一个指针指向它，这有就n-1个结点被实用，空的指针有n+1个，可用作线索。

一棵深度为k，且有2^（k-1）个节点的二叉树，称为满二叉树。这种树的特点是每一层上的节点数都是最大节点数。而在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干节点，则此二叉树为完全二叉树。

具有n个节点的完全二叉树的深度为floor(log2n)+1。深度为k的完全二叉树，至多有2^（k-1）个叶子节点，至多有2k-1个节点。

扩展资料：

二叉树不是树的一种特殊情形，尽管其与树有许多相似之处，但树和二叉树有两个主要差别：

1、树中结点的最大度数没有限制，而二叉树结点的最大度数为2；

2、树的结点无左、右之分，而二叉树的结点有左、右之分。

有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：

若I为结点编号则 如果I>1，则其父结点的编号为I/2；

如果2*I<=N，则其左孩子（即左子树的根结点）的编号为2*I；若2*I>N，则无左孩子；

如果2*I+1<=N，则其右孩子的结点编号为2*I+1；若2*I+1>N，则无右孩子。

若结点是二叉树的根，则其后继为空；若结点是其双亲的右孩子，或是其双亲的左孩子且其双亲没有右子树，则其后继即为双亲结点；若结点是其双亲的左孩子，且其双亲有右子树，则其后继为双亲右子树上按后序遍历列出的第一个结点。

参考资料来源：百度百科——二叉树

Answer 2

在一个具有n个结点的线索二叉树中有n+1个指针是用来作为线索处理的
因为n个结点的二叉树中有2n个指针,而这些个结点（除根结点）都有一个指针指向它,这有就n-1个结点被实用,空的指针有n+1个,可用作线索

Answer 3

n个结点有2n个指针，这些指针本来用来指向左、右孩子，有些结点无左or右or左右孩子，这些空指针被利用起来指向某种顺序遍历的前驱、后继，就形成了线索二叉树。从结点作为孩子被指的角度出发，除根结点外的每个结点都有一个指针指向自己，所以有n-1个用来指向左右孩子的指针，剩余的2n-(n-1)=n+1个指针就当做线索。

Answer 4

n-1 首尾不用

Answer 5

这个教材上都有的，不要问这么傻乎乎的问题啦