|
#region 查找指定节点的后继
/// <summary>
/// 查找指定节点的后继
/// </summary>
/// <typeparam></typeparam>
/// <param></param>
public ThreadTree<T> BinTreeThreadNext_LDR<T>(ThreadTree<T> tree)
{
if (tree == null)
return null;
//如果查找节点的标志域中是Thread，则直接获取
if (tree.rightFlag == NodeFlag.Thread)
return tree.right;
else
{
//根据中序遍历的规则是寻找右子树中中序遍历的第一个节点
var rightNode = tree.right;
//如果该节点是subTree就需要循环遍历
while (rightNode.leftFlag == NodeFlag.SubTree)
{
rightNode = rightNode.left;
}
return rightNode;
}
}
#endregion
<4> 查找前驱节点
这个跟（3)的操作很类似，同样也具有两个情况。
《1》 拿“C结点”来说，他没有“左子树”，则说明“C节点”的左指针为Thread，此时，我们只要返回左指针域即可得到前驱结点。
《2》 拿"A节点“来说，他有”左子树“，则说明”A节点“的左指针为SubTree，那么怎么找的到”A节点“的前驱呢？同样啊，根据
”中序遍历“的性质，我们可以得知在”A节点“的左子树中往”右链“中找到第一个没有”右孩子“的节点。
复制代码 代码如下:
#region 查找指定节点的前驱
/// <summary>
/// 查找指定节点的前驱
/// </summary>
/// <typeparam></typeparam>
/// <param></param>
/// <returns></returns>
public ThreadTree<T> BinTreeThreadPrev_LDR<T>(ThreadTree<T> tree)
{
if (tree == null)
return null;
//如果标志域中存放的是线索，那么可以直接找出来
if (tree.leftFlag == NodeFlag.Thread)
return tree.left;
else
{
//根据”中序“的规则可知，如果不为Thread，则要找出左子树的最后节点
//也就是左子树中最后输出的元素
var leftNode = tree.left;
while (leftNode.rightFlag == NodeFlag.SubTree)
leftNode = leftNode.right;
（编辑：焦作站长网）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
