算法系列15天速成 第十二天 树操作【中】

#region 中序遍历构建线索二叉树
        /// <summary>
/// 中序遍历构建线索二叉树
/// </summary>
/// <typeparam></typeparam>
/// <param></param>
        public void BinTreeThreadingCreate_LDR<T>(ref ThreadTree<T> tree, ref ThreadTree<T> prevNode)
        {
            if (tree == null)
                return;

//先左子树遍历，寻找起始点
            BinTreeThreadingCreate_LDR(ref tree.left, ref prevNode);

//如果left为空，则说明该节点可以放“线索”
            tree.leftFlag = (tree.left == null) ? NodeFlag.Thread : NodeFlag.SubTree;

//如果right为空，则说明该节点可以放“线索”
            tree.rightFlag = (tree.right == null) ? NodeFlag.Thread : NodeFlag.SubTree;

if (prevNode != null)
            {
                if (tree.leftFlag == NodeFlag.Thread)
                    tree.left = prevNode;
                if (prevNode.rightFlag == NodeFlag.Thread)
                    prevNode.right = tree;
            }

//保存前驱节点
            prevNode = tree;

BinTreeThreadingCreate_LDR(ref tree.right, ref prevNode);
        }
        #endregion

#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

（编辑：焦作站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!