☰

pstree：如何强制树节点偏向一侧？

tag-icon • tag-icon pstricks trees pst-tree
pstree：如何强制树节点偏向一侧？

我正在使用 pstricks 和 pstree 绘制一些二叉搜索树，但我在文档中没有看到任何将节点推到一侧的内容。在二叉搜索树中，每个子节点都必须在右或左，但如果只有一个子节点，则 pstree 会将其垂直悬挂。

   *
  / \
 *   *
/ \  |

应该

   *
  / \
 *   *
/ \   \

答案1

放置一个 nil 节点并不难，但需要很好的数学知识。手动添加一些空间会很丑陋。

在 pstree 中，您操作的是（有序的）n 元树，因此没有左子节点或右子节点的概念。您只能给出子节点的列表（有序的）。

考虑一下如何用有序 n 元树 (t := 树列表) 实现二叉树 (t := () | (t, t))。以下两个二叉树是不同的。

  *          *
 /     !=     \
*              *

虽然它们与 n 叉树相同。您需要显式编码左子节点的跳过，以在 n 叉树中模拟这一点。

为了这个目的，pstree 的创建者向您提出了一个杰出的\Tn节点（零节点）。

\pstree{\TR{a}}{
  \Tn
  \TR{b}
}

就像缺失的信息也是一种信息一样。

答案2

用于\Tn“空节点”......

\documentclass{article}
\usepackage{pst-tree}
\begin{document}

\pstree[levelsep=25pt]{\Tcircle{10}}{
    \pstree{\Tcircle{1}}{
        \Tn
        \pstree{\Tcircle{5}}{\Tcircle{4}{\Tn}}
    }
    \pstree{\Tcircle{16}}{
        \Tn
        \pstree{\Tcircle{17}}{
            \Tn
            \Tcircle{21}
        }
    }
}

\end{document}

在此处输入图片描述

答案3

我求助于{\psset{linestyle=none}\TR{}}在树中插入不可见节点 ( )，这会将另一个节点推向一侧。它满足了我的需要，但有点不合时宜，并且表现得像一个不可见节点，而不是一个明确定义的向一侧的偏移。（例如，在渲染的图像中，将 4 进一步移到它应该在的位置会很麻烦。）

\pstree[levelsep=25pt]{\Tcircle{10}}
{
    \pstree{\Tcircle{1}}
    {
        {\psset{linestyle=none}\TR{}}
        \pstree{\Tcircle{5}}
        {
            \Tcircle{4}
            {\psset{linestyle=none}\TR{}}
        }
    }
    \pstree{\Tcircle{16}}
    {
        {\psset{linestyle=none}\TR{}}
        \pstree{\Tcircle{17}}
        {
            {\psset{linestyle=none}\TR{}}
            \Tcircle{21}
        }
    }
}

给予

  10
 /      1    16
 \            5     17
 /            4          21

使用 pstricks 和 pstree 的 BST

相关内容