基于Record Structure的二叉树程序仅能添加一个元素排查求助

我依据剑桥国际A&AS Level教材编写了一个使用Record Structure实现Binary Tree的程序（考试要求必须使用该结构），但程序运行时仅能添加一个元素，尽管数组支持最多8个元素。期望程序能添加最多8个元素并支持查找功能，自行排查未发现错误，恳请帮忙定位问题所在。

代码如下： #

NULLPOINTER = -1

class TreeNode:
    def __init__(self):
        self.Data= ""
        self.LeftPointer = NULLPOINTER
        self.RightPointer = NULLPOINTER

def InialiseTree():
    Tree = [TreeNode() for i in range(8)]
    RootPointer = NULLPOINTER
    FreePtr = 0
    for Index in range(7):
        Tree[Index].leftPointer = Index+1
    return (Tree, RootPointer, FreePtr)

def InsertNode(Tree, RootPointer, FreePtr, NewItem):
    if FreePtr !=NULLPOINTER:#there is space in the array, 
        NewNodePtr = FreePtr #take node from free list and store there
        Tree[NewNodePtr].Data = NewItem
        FreePtr=Tree[FreePtr].LeftPointer
        Tree[NewNodePtr].LeftPointer= NULLPOINTER
        if RootPointer ==NULLPOINTER:
            RootPointer = NewNodePtr
        else:
            ThisNodePtr = RootPointer
            while ThisNodePtr != NULLPOINTER:
                PreviousNodePtr=ThisNodePtr
                if Tree[ThisNodePtr].Data>NewItem:
                    TurnedLeft = True
                    ThisNodePtr=Tree[ThisNodePtr].LeftPointer
                else:
                    TurnedLeft = False
                    ThisNodePtr=Tree[ThisNodePtr].RightPointer
            if TurnedLeft:
                Tree[PreviousNodePtr].LeftPointer=NewNodePtr
            else:
                Tree[PreviousNodePtr].RightPointer=NewNodePtr
    else:
        print("No space for more data")
    return (Tree, RootPointer, FreePtr)
            
def TraverseTree(Tree, RootPointer):
  if RootPointer != NULLPOINTER:
    TraverseTree(Tree, Tree[RootPointer].LeftPointer)
    print(Tree[RootPointer].Data)
    TraverseTree(Tree, Tree[RootPointer].RightPointer)


def GetOption():
  print("1: add data")
  print("2: find data")
  print("3: traverse data")
  print("4: end program")
  option = input("Enter your choice: ")
  return (option)

def FindNode(Tree, RootPointer, SearchItem):
  ThisNodePtr= RootPointer
  while ThisNodePtr!= NULLPOINTER and Tree[ThisNodePtr].Data!=SearchItem:
    if Tree[ThisNodePtr].Data>SearchItem:
      ThisNodePtr = Tree[ThisNodePtr].LeftPointer
    else:
      ThisNodePtr = Tree[ThisNodePtr].RightPointer
  return (ThisNodePtr)
  
#main program
Tree, RootPointer, FreePtr = InialiseTree()
Option=GetOption()
while Option !=4:
  if Option == "1":
    Data = input("Enter the value: ")
    Tree, RootPointer, FreePtr = InsertNode(Tree, RootPointer, FreePtr, Data)
    TraverseTree(Tree, RootPointer)
  elif Option=="2":
    Data = input("Enter search value: ")
    ThisNodePtr= FindNode(Tree, RootPointer, Data)
    if ThisNodePtr==NULLPOINTER:
      print("Value not found")
    else:
      print("VAlue found at ", ThisNodePtr)
    print(RootPointer, FreePtr)
    for i in range (8):
      print(i, "  ", Tree[i].LeftPointer, "  ", Tree[i].Data, Tree[i].RightPointer, "  " )
  elif Option =="3":
    TraverseTree(Tree, RootPointer)  
  Option = GetOption()

错误定位与修复 #

问题出在InialiseTree函数中的属性大小写不匹配：

• TreeNode类定义的左指针属性是LeftPointer（首字母大写L）
• 但初始化循环中错误地使用了Tree[Index].leftPointer（首字母小写l），这会给每个节点新增一个名为leftPointer的属性，而非修改原本的LeftPointer

这导致首次插入元素后，FreePtr被设置为Tree[FreePtr].LeftPointer（即初始的NULLPOINTER），程序误以为数组已满，无法继续插入新元素。

修复方法：修改InialiseTree函数中的循环语句，将leftPointer改为LeftPointer：

def InialiseTree():
    Tree = [TreeNode() for i in range(8)]
    RootPointer = NULLPOINTER
    FreePtr = 0
    for Index in range(7):
        Tree[Index].LeftPointer = Index+1  # 修正大小写
    return (Tree, RootPointer, FreePtr)

另外，代码中还有一处拼写错误：InialiseTree应为InitializeTree（符合英文拼写规范），但如果是教材要求的写法，可保留原名称。

修复后，程序即可正常插入最多8个元素，同时查找功能也能正常工作。

内容的提问来源于stack exchange，提问作者Naushin Mirza