用 Python 等语言写树结构的疑问

最近想做几道算法题，但是我并不熟悉用任何刷题用的主流语。我发现我用这些语言似乎表达不出我想要的语义。拿 Python 写二叉树结构为例，我用 Python 的类定义好了 Leaf 和 Node 的结构，假设现在我想定义一个结构或者类型，叫“Leaf 或者 Node”，起名为“Tree”，在 Python 里是怎么处理的呢？或者 Java、C、C++都行。（如下图，我写习惯了 Typed Scheme，所以在接触算法题之前用的都是 Union Type 来表示这些“递归数据类型”，其实就是想在 Python 等主流语言里找个对应的写法）

如果实在没有满足我需求的写法的话，大家用这些语言一般是怎么表示这些“递归数据类型”，以方便刷题需求的呢，不会是树里套表这种的吧？......



另外我还想知道，Python 有什么机制（比如 contract）防止 Node 的左右两边加进去奇怪的东西而不是 Node 或 Leaf ......

1. class Node(object):
   
2.         def __init__(self, l=None, r=None):
   
3.                 self.left  = l
   
4.                 self.right = r
   
5. 
   
6. class Leaf(object):
   
7.         def __init__(self, v=None):
   
8.                 self.val = v
   
9. 
   
10.         def get_val(self):
    
11.                 return self.val

复制代码

虽然感觉不用给node和leaf分开两个类（node也要有val的呀，leaf就是left和right都为none的node）

但如果非要有node有leaf还有一个类表示他俩任意之一，感觉用继承(inheritance)就好了
先定义一个general的类，然后node和leaf都是那个类的子类

enthusiastic 发表于 2020-1-22 04:19
python不是有private吗？在变量前面加__就可以了？

这只是一种convention，没有任何约束力的，在外面一样能访问（除非你用某些特殊trick）。这和你写一个private int x然后外面访问x，编译器直接报错完全不一样

Leaf 就是左右子树为空的node

加上assert
见例子
http://composingprograms.com/pag ... cts.html#tree-class

可以考虑用typing来限定传入的类型

在一个连 private 和 typed array 都没有的语言里寻求 type contract 感觉有点缘木求鱼啊。最接近的就是使用 type hints 了，但是也只是 hints 而已，解释器本身不会做检查的。。

onefly 发表于 2020-1-20 12:40
在一个连 private 和 typed array 都没有的语言里寻求 type contract 感觉有点缘木求鱼啊。最接近的就是使 ...

python不是有private吗？在变量前面加__就可以了？

Python  简洁的原因之一就是所有的variable 都是object。

Leaf 不就是一个Node么？没有assign的话，就是None，所以检查leaf就是 left is None and right is None

rwalle 发表于 2020-1-22 22:32
这只是一种convention，没有任何约束力的，在外面一样能访问（除非你用某些特殊trick）。这和你写一个pri ...

噢原来是这样啊，懂了！谢谢！