爲什麼需要在樹中添加新創建的節點以排隊

Question

我正在創建一個讀取列表的二叉樹。當我遍歷我的列表時，2k + 1元素是我的左子元素，而我的數組中的2k + 2元素是我的正確的孩子（從數組中的第0個索引開始）。

假設我有數組10,20,30,40,50然後10是根20是左邊的孩子30是右邊的孩子爲root 10.similary爲root.left即20它將有兩個孩子40,50基於在我提到的公式上。 當我們遍歷數組時，爲一個根，左邊的孩子或右邊創建一個新的節點新創建的對象被追加到隊列中。

class createnode: 
    def __init__(self,data): 
     self.root=data 
     self.left=None 
     self.right=None 

class createbinarytree: 

    def array(self): 
     self.q=[] 
     self.num=int(raw_input("enter the number of element you want in the list")) 
     for i in range(0,self.num): 
      self.num1=int(raw_input("enter the " + `i+1` +"element")) 
      self.q.append(self.num1) 

    def createtree(self): 
     z=[] 
     arr_len=len(self.q) 
     k=0 
     root_data=self.q[0] 
     self.top=createnode(root_data) 
     z.append(self.top) #Why we appened to list? 

     while(k<arr_len): 

      self.parent=z.pop(0) #poped value will be used as to refer to left or right child 
      self.x=int(2) * int(k)+int(1) 
      if(self.x>=arr_len): 
      break; 
      left_data=self.q[self.x] 
      self.left_child=createnode(left_data) 
      z.append(self.left_child) 
      self.y=int(2) * int(k)+int(2) 
      if(self.y>=arr_len): 
      break; 
      right_data=self.q[self.y] 
      self.right_child=createnode(right_data) 
      z.append(self.left_child) 
      self.parent.left=self.left_child ##Here it is used why not self.top directly 
      self.parent.right=self.right_child   

      k=k+1 
    def inordertraversse(self,top): 
      if(top): 
      self.inordertraversse(top.left) 
      print(top.root) 
      self.inordertraversse(top.right) 

conv=createbinarytree(); 
conv.array() 
conv.createtree() 
print("the inorder traversal is ") 
conv.inordertraversse(conv.top) 

輸出：14,11,15,10,13

隨着我們添加新創建的列表變量中去。所以聲明z.append(self.top)爲什麼我們不能直接使用self.top程序的其他部分。就像我試着用下面的代碼一樣，它只打印出最新的根值，一個元素。

class createnode: 
    def __init__(self,data): 
     self.root=data 
     self.left=None 
     self.right=None 

class createbinarytree: 

    def createtree(self): 
     self.l=[1,2,3,4,5] 
     arr_len=len(self.l) 
     k=0 

     while(k<arr_len): 
      root_data=self.l[k] 
      self.top=createnode(root_data) 
      self.x=int(2) * int(k)+int(1) 
      if(self.x>=arr_len): 
      break; 
      left_data=self.l[self.x] 
      self.left_child=createnode(left_data) 

      self.y=int(2) * int(k)+int(2) 
      if(self.y>=arr_len): 
      break; 
      right_data=self.l[self.y] 
      self.right_child=createnode(right_data) 
      self.top.left=self.left_child 
      self.top.right=self.right_child 
      print(self.top.left.root) 
      print(self.top.right.root) 
      k=k+1 
    def inordertraversse(self,top): 
      if(top): 
      self.inordertraversse(top.left) 
      print(top.root) 
      self.inordertraversse(top.right) 

conv=createbinarytree(); 
conv.createtree() 
print("THe inorder traversal") 
conv.inordertraversse(conv.top) 

輸出：3

爲什麼我們看到這樣的行爲難道我們需要存儲在數據結構的新創建的對象，如在案件列表等，每次如果我們想進一步參照的對象？

Answer 1

在你的（第2）代碼塊，看執行的時候這條線經過一些迭代已經完成：

self.top=createnode(root_data) 

，然後問自己這個節點如何成爲另一個節點的孩子，你已經創建過。您使用self.top唯一做的其他事情是分配其子女。但self.top本身仍然是一個孤兒。而且，它永遠不會有孫輩，因爲孩子們在下一次迭代中都不會再被引用。

這就是爲什麼在代碼的第一個版本中有一個列表用作隊列（先入先出）：它允許將新節點連接到您保留在隊列中的父節點。由於樹的數組表示形式中定義明確的順序，因此當前節點的父節點始終是下一個從隊列中拉出的節點。如果你沒有那個隊列，你不會知道哪個是父母。

當樹未滿時，代碼仍存在問題。嘗試使用[1,2,3,4,5,6,7,8]，你會看到輸出只列出5個節點（因爲left_child而不是right_child錯誤）或7（當該錯誤被修復時）。

這是因爲當節點沒有子節點時，你跳出循環，但是在所有節點都添加到樹之前，不應該結束循環。

所以不這樣做：

if(self.x>=arr_len): 
    break; 

相反測試反狀態，如果真的執行相關的行動，但仍繼續循環。

請注意，除非您要公開該數據，否則不要使用self屬性。但在你的代碼中，我不會使用self.x,self.parent等等，因爲它們只是用於臨時存儲。相反，請刪除self.前綴，以便它們是本地專用名稱。

此外，您不需要在if或while條件下用圓括號包裝。

調用int()是不必要的：所有這些值都是整數。

所以你的while循環應該是這樣的：

while k<arr_len: 
    parent=z.pop(0) 
    x=2*k+1 
    if x<arr_len: 
     left_data=self.q[x] 
     left_child=createnode(left_data) 
     z.append(left_child) 
     parent.left=left_child 
    y=2*k+1 
    if y<arr_len: 
     right_data=self.q[y] 
     right_child=createnode(right_data) 
     z.append(right_child) 
     parent.right=right_child   
    k=k+1 

要知道，你有兩次z.append(self.left_child)：其中一人必須是z.append(self.right_child)。

我也建議你爲你的類提供構造函數，所以你可以在從它們創建對象時傳遞參數。