python 中具有不同类型节点的树的递归

Question

我正在构建一个由内部节点（由 class 内部表示）和叶节点（由 class 节点表示）组成的树 class。

class Node(object):
    def __init__(self,bits,data):
        self.bits = bits
        self.data = data


class Inner(object):
    def __init__(self):
        self.bits = ''
        self.c0  = None
        self.c1 = None


class Tree(object):
    def __init__(self):
        self.root = None

   def insert_Item(self,key,datastr):
   #code goes here

我可以使用插入方法插入叶节点和内部节点。

t = Tree()
t.insert('1111', 'A')
t.insert('1110', 'B')

插入方法的递归公式出现问题。假设 self.root.c0 和 self.root.c1 指向内部节点，我无法调用 self.root.c0.insert() 或 self.root.c1.insert()。这是因为内class没有插入功能

如何使插入方法以递归方式在所有三个 classes 上工作？同样，我无法进行树遍历，因为我收到内部对象没有属性 'data'

的错误

Answer 1

考虑改变你的实现，所以树只有节点，遍历方法是节点class的一个class方法，节点的身份是内部还是叶子被确定为节点是否有子节点的函数。

一般来说，就 OOP 而言，您希望实现尽可能少的 classes-- 尽可能少以完全消除程序功能的歧义，同时为其他程序员提供必要的增强实用程序。在实现一个新的 subclass 之前，想一想：另一个 class 可以在不使用多态性的情况下执行这个 class 的方法吗？

class Node(object):

      leftNode = None
      rightNode = None
      root = None

      def __init__(self,data,bit):
         self.bits = bit
         self.data = data
    /* I will make an assumption about the structure, left us assume the tree is simple, and preferentially populates the left subtree */
      def insert_Item(self,data,bit):
         if (leftNode == None):
              self.leftNode = Node(data,bit)
         elif (rightNode === None):
              self.rightNode = Node(data,bit)
         else:
              self.leftNode.insert_Item(data, bit)

class Tree(object):
    root = None
    def __init__(self, rootNode):
        self.root = rootNode

    def add_data(self,data,bit):
        self.root.insert_Item(data,bit)

稍作修改，这两个 classes 将满足您的所有需求。我建议将此文本作为入门读物：http://interactivepython.org/runestone/static/pythonds/index.html

python 中具有不同类型节点的树的递归

recursion on a tree with different type of nodes in python

python

recursion

binary-tree

data-structures