Number of valid parenthesis 加泰罗尼亚数字解释
Number of valid parenthesis catalan number explanation
在研究 catalan numbers 时,我遇到的一些应用程序是:
- 没有使用 n 个节点的可能二叉搜索树。
- 没有使用圆上的 2*n 个点绘制不相交弦的方法。
- 没有办法排列 n 对括号。
虽然我理解前两个问题,即加泰罗尼亚数字如何适合他们的解决方案,但我无法理解它们如何适合第三个问题。
在 Internet 上找不到任何其他有用的资源来解释 HOW 部分。每个人都说这是解决方案。
谁能解释一下。
由于其他人似乎不同意我这个问题off-topic,所以我现在决定它是主题并提供和回答。
维基百科确实混淆了 "number of ways to arrange n pairs of parentheses"(this link 中的第二个要点)。部分混淆是括号字符串的顺序与括号字符串的顺序不匹配二叉树,你确实理解,或者还有很多其他的例子。
这是一种将正确匹配的 n
对括号的字符串转换为具有 n
个内部节点的二叉树的方法。考虑 left-most 括号,它将是一个 left-parenthesis,连同它的匹配 right-parenthesis。将字符串变成二叉树的一个节点。 里面的currently-considered括号里面的sub-string就变成了这个节点左边的child,[=71的sub-string =]after(右边)的currently-considered right-parenthesis变成右边的child。 sub-string 中的一个或两个都可以为空,并且 currently-considered 括号被简单地删除。如果 sub-string 不为空,则递归地继续此过程,直到删除所有括号。
这里有两个例子。让我们从字符串 ((()))
开始。我们从
开始
considered-parentheses是最外面的。这变成
(我没有费心画外部叶节点)然后
然后
这是维基百科的 left-most 具有 3 个内部节点的二叉树。
现在让我们做另一个字符串,(())()
。我们从
开始
同样,considered-parentheses 是最外面的。这转换为
现在 considered-parentheses 是前两个,而不是最外面的。这变成
最后变成
这是维基百科列表中的第二个二叉树。
希望你现在明白了。这是正确配对的 3 对括号的所有五个可能字符串的列表,后面是维基百科的二叉树列表。这些列表现在相互对应。
((())) (()()) (())() ()(()) ()()()
在研究 catalan numbers 时,我遇到的一些应用程序是:
- 没有使用 n 个节点的可能二叉搜索树。
- 没有使用圆上的 2*n 个点绘制不相交弦的方法。
- 没有办法排列 n 对括号。
虽然我理解前两个问题,即加泰罗尼亚数字如何适合他们的解决方案,但我无法理解它们如何适合第三个问题。
在 Internet 上找不到任何其他有用的资源来解释 HOW 部分。每个人都说这是解决方案。
谁能解释一下。
由于其他人似乎不同意我这个问题off-topic,所以我现在决定它是主题并提供和回答。
维基百科确实混淆了 "number of ways to arrange n pairs of parentheses"(this link 中的第二个要点)。部分混淆是括号字符串的顺序与括号字符串的顺序不匹配二叉树,你确实理解,或者还有很多其他的例子。
这是一种将正确匹配的 n
对括号的字符串转换为具有 n
个内部节点的二叉树的方法。考虑 left-most 括号,它将是一个 left-parenthesis,连同它的匹配 right-parenthesis。将字符串变成二叉树的一个节点。 里面的currently-considered括号里面的sub-string就变成了这个节点左边的child,[=71的sub-string =]after(右边)的currently-considered right-parenthesis变成右边的child。 sub-string 中的一个或两个都可以为空,并且 currently-considered 括号被简单地删除。如果 sub-string 不为空,则递归地继续此过程,直到删除所有括号。
这里有两个例子。让我们从字符串 ((()))
开始。我们从
considered-parentheses是最外面的。这变成
(我没有费心画外部叶节点)然后
然后
这是维基百科的 left-most 具有 3 个内部节点的二叉树。
现在让我们做另一个字符串,(())()
。我们从
同样,considered-parentheses 是最外面的。这转换为
现在 considered-parentheses 是前两个,而不是最外面的。这变成
最后变成
这是维基百科列表中的第二个二叉树。
希望你现在明白了。这是正确配对的 3 对括号的所有五个可能字符串的列表,后面是维基百科的二叉树列表。这些列表现在相互对应。
((())) (()()) (())() ()(()) ()()()