在Python中创建一个空的二叉树

Question

我是编程的初学者，在其他问题中我找不到答案。 我想创建一个高度为h的空二叉树。

我的代码：

class node: 
    def __init__(self, a = None): 
     self.value = a 
     self.left = None 
     self.right = None 

def postorder(tree,abba): 
    if tree != None: 
     postorder(tree.left,abba) 
     postorder(tree.right,abba) 
     abba.append(tree.value) 

def inorder(tree,abba): 
    if tree != None: 
     inorder(tree.left,abba) 
     abba.append(tree.value) 
     inorder(tree.right,abba) 

我想定义一个函数

def getBinaryTree(h): 

这给了我与级别h的树。所以： empty tree of level

任何想法？

Answer 1

更新

为了使二叉树的高度h，你需要添加2^(h+1)-1节点。高度为0的树表示该树仅包含一个节点，并且该树是根。例如，要创建高度为3的树，您需要添加2^(3+1)-1 = 15节点。

如果你想创建一组节点，可以用你的给定的代码形成一个二叉树，你可以做这样的事情。

import math 

class node: 
    def __init__(self, a = None): 
     self.value = a 
     self.left = None 
     self.right = None 

def getBinaryTree(tree_height): 
    tree_nodes = [None] * int((math.pow(2, tree_height+1) - 1)) 
    for i in range(tree_height): 
     start_index = int(math.pow(2, i) - 1) 
     end_index = int(math.pow(2, i+1) - 1) 
     for j in range(start_index, end_index): 
      tree_nodes[j] = node(j) 
      if j == 0: continue 
      if j % 2 == 0: # a right child 
       parent_index = int((j - 2)/2) 
       tree_nodes[parent_index].right = tree_nodes[j] 
      else: # a left child 
       parent_index = int((j - 1)/2) 
       tree_nodes[parent_index].left = tree_nodes[j] 

    return tree_nodes[0] # returns the root node 

def printTree(tree_node, inorder_tree_walk): 
    if tree_node != None: 
     printTree(tree_node.left, print_tree) 
     inorder_tree_walk.append(tree_node.value) 
     printTree(tree_node.right, print_tree) 

root = getBinaryTree(4) 
inorder_tree_walk = [] 
printTree(root, inorder_tree_walk) 
print(inorder_tree_walk) 

那么，是什么程序呢？

该程序创建2^(h+1)-1节点，形成高度为h的树。节点存储在列表tree_nodes中。如下所示将节点之间的父子关系存储在tree_nodes中。

元件 i的
• 左子：第（2i + 1）个元素
• 元件i的右子节点：当创建一个孩子节点第（2i + 2）个元件

，它是设置为其父项的左/右子项。