用Python實(shí)現(xiàn)二叉樹(shù)、二叉樹(shù)非遞歸遍歷及繪制的例子

更新時(shí)間：2019年08月09日 17:07:49 作者：huang_shiyang

今天小編就為大家分享一篇用Python實(shí)現(xiàn)二叉樹(shù)、二叉樹(shù)非遞歸遍歷及繪制的例子，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧

前言

關(guān)于二叉樹(shù)的實(shí)現(xiàn)與遍歷，網(wǎng)上已經(jīng)有很多文章了，包括C， C++以及JAVA等。鑒于python做為腳本語(yǔ)言的簡(jiǎn)潔性，這里寫(xiě)一篇小文章用python實(shí)現(xiàn)二叉樹(shù)，幫助一些對(duì)數(shù)據(jù)結(jié)構(gòu)不太熟悉的人快速了解下二叉樹(shù)。本文主要通過(guò)python以非遞歸形式實(shí)現(xiàn)二叉樹(shù)構(gòu)造、前序遍歷，中序遍歷，后序遍歷，層次遍歷以及求二叉樹(shù)的深度及葉子結(jié)點(diǎn)數(shù)。其他非遞歸形式的遍歷，想必大多人應(yīng)該都很清楚，就不再聲明。如果你用C或者C++或者其他高級(jí)語(yǔ)言寫(xiě)過(guò)二叉樹(shù)或者閱讀過(guò)相關(guān)方面代碼，應(yīng)該知道二叉樹(shù)的非遞歸遍歷避不開(kāi)通過(guò)?；蛘哧?duì)列實(shí)現(xiàn)。是的，python也一樣。但是python自帶的list功能很強(qiáng)大，即可以當(dāng)stack 又可以當(dāng)成queue。這樣用python實(shí)現(xiàn)二叉樹(shù)就可以減少了對(duì)?；蛘哧?duì)列的聲明及定義。

實(shí)現(xiàn)

二叉樹(shù)的結(jié)點(diǎn)的實(shí)現(xiàn)

如上圖1的的二叉樹(shù)，要想實(shí)現(xiàn)二叉樹(shù)。首先應(yīng)該先聲明一個(gè)二叉樹(shù)結(jié)點(diǎn)，包括它的元素及左右子結(jié)點(diǎn)，這個(gè)在C/C++也是一樣的。在python里，可以通過(guò)類(lèi)聲明一個(gè)結(jié)點(diǎn)，如下:

class BiNode(object):
 """class BiNode provide interface to set up a BiTree Node and to interact"""
 def __init__(self, element=None, left=None, right=None):
  """set up a node """
  self.element = element
  self.left = left
  self.right = right

 def get_element(self):
  """return node.element"""
  return self.element

 def dict_form(self):
  """return node as dict form"""
  dict_set = {
   "element": self.element,
   "left": self.left,
   "right": self.right,
  }
  return dict_set

 def __str__(self):
  """when print a node , print it's element"""
  return str(self.element)

上述的dict_form interface是將結(jié)點(diǎn)以python字典的形式呈現(xiàn)出來(lái)，方便后面將樹(shù)打包成字典。另外說(shuō)明下由于python字典的特性，將字典當(dāng)成一個(gè)樹(shù)結(jié)構(gòu)來(lái)處理也是可以的。事實(shí)上，很多人是這樣做的。下圖測(cè)試展現(xiàn)了樹(shù)結(jié)點(diǎn)的實(shí)現(xiàn)：

二叉樹(shù)初始化

實(shí)現(xiàn)了二叉樹(shù)結(jié)點(diǎn)，接下來(lái)實(shí)現(xiàn)二叉樹(shù).首先對(duì)二叉樹(shù)進(jìn)行初始化，代碼如下：

class BiTree:
 """class BiTree provide interface to set up a BiTree and to interact"""
 def __init__(self, tree_node=None):
  """set up BiTree from BiNode and empty BiTree when nothing is passed"""
  self.root = tree_node`

上面代碼很簡(jiǎn)單，就是對(duì)樹(shù)通過(guò)一個(gè)傳進(jìn)來(lái)的結(jié)點(diǎn)進(jìn)行初始化，如果參數(shù)為空則初始化為一個(gè)空樹(shù)。

順序構(gòu)造二叉樹(shù)

那么我如果想通過(guò)一個(gè)列表元素按順序?qū)崿F(xiàn)樹(shù)的構(gòu)造或者通過(guò)字典進(jìn)行構(gòu)造呢？

先說(shuō)下用一個(gè)列表元素按順序構(gòu)造。

假設(shè)現(xiàn)在已經(jīng)存在一顆二叉樹(shù)，如下圖2

新添加的結(jié)點(diǎn)按順序做為結(jié)點(diǎn)2的左子結(jié)點(diǎn)（這里不考慮像二叉查找樹(shù)等的插入要求）?；静迦敕椒ㄈ缦拢?/p>

判斷根結(jié)點(diǎn)是否存在，如果不存在則插入根結(jié)點(diǎn)。否則從根結(jié)點(diǎn)開(kāi)始，判斷左子結(jié)點(diǎn)是否存在，如果不存在插入, 如果左子結(jié)點(diǎn)存在判斷右結(jié)點(diǎn)，不存在插入。如果左右結(jié)點(diǎn)存在，再依次遍歷左右子結(jié)點(diǎn)的子結(jié)點(diǎn)，直到插入成功。

上述的方法類(lèi)似于層次遍歷，體現(xiàn)了廣度搜索優(yōu)先的思想。因此從代碼實(shí)現(xiàn)上，很顯然需要一個(gè)隊(duì)列對(duì)子結(jié)點(diǎn)進(jìn)行入隊(duì)與出隊(duì)。在python上這很簡(jiǎn)單，一個(gè)list 就實(shí)現(xiàn)了，代碼如下：

 def add_node_in_order(self, element):
  """add a node to existent BiTree in order"""
  node = BiNode(element)

  if self.root is None:
   self.root = node
  else:
   node_queue = list()
   node_queue.append(self.root)
   while len(node_queue):
    q_node = node_queue.pop(0)
    if q_node.left is None:
     q_node.left = node
     break
    elif q_node.right is None:
     q_node.right = node
     break
    else:
     node_queue.append(q_node.left)
     node_queue.append(q_node.right)

 def set_up_in_order(self, elements_list):
  """set up BiTree from lists of elements in order """
  for elements in elements_list:
   self.add_node_in_order(elements)

set_up_in_order（）實(shí)現(xiàn)了通過(guò)列表對(duì)樹(shù)進(jìn)行順序構(gòu)造。

從字典初始化構(gòu)造二叉樹(shù)

當(dāng)然你會(huì)發(fā)現(xiàn)，用上述方法構(gòu)造的二叉樹(shù)永遠(yuǎn)都是完全二叉樹(shù)。實(shí)際情況下，我們需要初始化像圖3這樣的一棵不規(guī)則的二叉樹(shù)，怎么辦？

此時(shí)，可以借住python的字典對(duì)樹(shù)進(jìn)行構(gòu)造，參考的node的dict_form,約定”element”的key_value是結(jié)點(diǎn)值，“l(fā)eft”，“right”的key_value也是一個(gè)字典代表左右子樹(shù)，如果為空則為None 。為方便書(shū)寫(xiě)，對(duì)于一個(gè)結(jié)點(diǎn)除了element不能缺外, 左右子樹(shù)不存在時(shí)相應(yīng)key可以缺失。同時(shí)對(duì)于葉結(jié)點(diǎn)，可以省略寫(xiě)成相應(yīng)的元素值而不用繼續(xù)構(gòu)造一個(gè)字典。此時(shí)可以通過(guò)類(lèi)似如下字典初始一棵二叉樹(shù)表示，如下：

dict_tree = {
 "element": 0,
 "left": {
  "element": 1,
  "left": {
   "element": 3,
   "left": 6,
   "right": 7,
  }
 },
 "right": {
  "element": 2,
  "left": 4,
  "right": {
   "element": 5,
   "left": 8,
   "right": 9,
  },
 },
}

上述字典表示的二叉樹(shù)即為圖3所示

通過(guò)字典進(jìn)行初始樹(shù)，可以借用層次遍歷的思想實(shí)現(xiàn)樹(shù)的構(gòu)造，本質(zhì)上其實(shí)就是對(duì)樹(shù)進(jìn)行一個(gè)非遞歸實(shí)現(xiàn)的拷貝，代碼實(shí)現(xiàn)如下：

def set_up_from_dict(self, dict_instance):
  """set up BiTree from a dict_form tree using level traverse, or call it copy """
  if not isinstance(dict_instance, dict):
   return None
  else:
   dict_queue = list()
   node_queue = list()
   node = BiNode(dict_instance["element"])
   self.root = node
   node_queue.append(node)
   dict_queue.append(dict_instance)
   while len(dict_queue):
    dict_in = dict_queue.pop(0)
    node = node_queue.pop(0)
    # in dict form, the leaf node might be irregular, like compressed to element type
    # Thus , all this case should be solved out respectively
    if isinstance(dict_in.get("left", None), (dict, int, float, str)):
     if isinstance(dict_in.get("left", None), dict):
      dict_queue.append(dict_in.get("left", None))
      left_node = BiNode(dict_in.get("left", None)["element"])
      node_queue.append(left_node)
     else:
      left_node = BiNode(dict_in.get("left", None))
     node.left = left_node

    if isinstance(dict_in.get("right", None), (dict, int, float, str)):
     if isinstance(dict_in.get("right", None), dict):
      dict_queue.append(dict_in.get("right", None))
      right_node = BiNode(dict_in.get("right", None)["element"])
      node_queue.append(right_node)
     else:
      right_node = BiNode(dict_in.get("right", None))
     node.right = right_node

將二叉樹(shù)打包成字典

往往我們也需要將一顆二叉樹(shù)用字典的形式表示出來(lái)，其方法與從字典初始化一棵二叉樹(shù)一樣，代碼實(shí)現(xiàn)如下：

def pack_to_dict(self):
  """pack up BiTree to dict form using level traversal"""
  if self.root is None:
   return None
  else:
   node_queue = list()
   dict_queue = list()
   node_queue.append(self.root)
   dict_pack = self.root.dict_form()
   dict_queue.append(dict_pack)
   while len(node_queue):
    q_node = node_queue.pop(0)
    dict_get = dict_queue.pop(0)
    if q_node.left is not None:
     node_queue.append(q_node.left)
     dict_get["left"] = q_node.left.dict_form()
     dict_queue.append(dict_get["left"])
    if q_node.right is not None:
     node_queue.append(q_node.right)
     dict_get["right"] = q_node.right.dict_form()
     dict_queue.append(dict_get["right"])
  return dict_pack

求二叉樹(shù)的深度

求二叉樹(shù)的深度或者高度的非遞歸實(shí)現(xiàn)，本質(zhì)上可以通過(guò)層次遍歷實(shí)現(xiàn)，方法如下：

1. 如果樹(shù)為空，返回0 。

2. 從根結(jié)點(diǎn)開(kāi)始，將根結(jié)點(diǎn)拉入列。

3. 當(dāng)列非空，記當(dāng)前隊(duì)列元素?cái)?shù)（上一層節(jié)點(diǎn)數(shù)）。將上層節(jié)點(diǎn)依次出隊(duì)，如果左右結(jié)點(diǎn)存在，依次入隊(duì)。直至上層節(jié)點(diǎn)出隊(duì)完成，深度加一。繼續(xù)第三步，直至隊(duì)列完全為空。

代碼實(shí)現(xiàn)如下：


 def get_depth(self):
  """method of getting depth of BiTree"""
  if self.root is None:
   return 0
  else:
   node_queue = list()
   node_queue.append(self.root)
   depth = 0
   while len(node_queue):
    q_len = len(node_queue)
    while q_len:
     q_node = node_queue.pop(0)
     q_len = q_len - 1
     if q_node.left is not None:
      node_queue.append(q_node.left)
     if q_node.right is not None:
      node_queue.append(q_node.right)
    depth = depth + 1
   return depth

前序遍歷

二叉樹(shù)的前序，中序，后序稱(chēng)體現(xiàn)的是深度優(yōu)先搜索的思想。

本質(zhì)上它們的方法其實(shí)是一樣的。

先說(shuō)前序遍歷，方法如下：

1. 如果樹(shù)為空，返回None 。

2. 從根結(jié)點(diǎn)開(kāi)始，如果當(dāng)前結(jié)點(diǎn)左子樹(shù)存在，則打印結(jié)點(diǎn)，并將該結(jié)點(diǎn)入棧。讓當(dāng)前結(jié)點(diǎn)指向左子樹(shù)，繼續(xù)步驟2直至當(dāng)前結(jié)點(diǎn)左子樹(shù)不存在。

3. 將當(dāng)結(jié)點(diǎn)打印出來(lái)，如果當(dāng)前結(jié)點(diǎn)的右子樹(shù)存在，當(dāng)前結(jié)點(diǎn)指向右子樹(shù)，繼續(xù)步驟2。否則進(jìn)行步驟4.

4. 如果棧為空則遍歷結(jié)束。若非空，從棧里面pop一個(gè)節(jié)點(diǎn)，從當(dāng)前結(jié)點(diǎn)指向該結(jié)點(diǎn)的右子樹(shù)。如果右子樹(shù)存在繼續(xù)步驟2，不存在繼續(xù)步驟4直至結(jié)束。

以圖2為例，用N代表結(jié)點(diǎn)。

1.N0 ，N1依次打印，并且入棧。

2. 打印N3,

3. N3右子樹(shù)不存在，N1出棧，遍歷N1右子樹(shù)N4

4. N4的左子樹(shù)不存在，打印N4。N4右子樹(shù)不存在，N0出棧，指向其右子樹(shù)N2

5. N2的左子樹(shù)不存在，打印N2，判斷右子樹(shù)及?？战Y(jié)束

代碼實(shí)現(xiàn)如下：

def pre_traversal(self):
  """method of traversing BiTree in pre-order"""
  if self.root is None:
   return None
  else:
   node_stack = list()
   output_list = list()
   node = self.root
   while node is not None or len(node_stack):
    # if node is None which means it comes from a leaf-node' right,
    # pop the stack and get it's right node.
    # continue the circulating like this
    if node is None:
     node = node_stack.pop().right
     continue
    # save the front node and go next when left node exists
    while node.left is not None:
     node_stack.append(node)
     output_list.append(node.get_element())
     node = node.left
    output_list.append(node.get_element())
    node = node.right
  return output_list

中序遍歷

中序遍歷的思想基本與前序遍歷一樣，只是最開(kāi)始結(jié)點(diǎn)入棧時(shí)先不打印。只打印不存在左子樹(shù)的當(dāng)前結(jié)點(diǎn)，然后再出棧遍歷右子樹(shù)前再打印出來(lái)，代碼實(shí)現(xiàn)如下：


 def in_traversal(self):
  """method of traversing BiTree in in-order"""
  if self.root is None:
   return None
  else:
   node_stack = list()
   output_list = list()
   node = self.root
   while node is not None or len(node_stack):
    # if node is None which means it comes from a leaf-node' right,
    # pop the stack and get it's right node.
    # continue the circulating like this
    if node is None:
     node = node_stack.pop()
     # in in-order traversal, when pop up a node from stack , save it
     output_list.append(node.get_element())
     node = node.right
     continue
    # go-next when left node exists
    while node.left is not None:
     node_stack.append(node)
     node = node.left
    # save the the last left node
    output_list.append(node.get_element())
    node = node.right
  return output_list

后序遍歷

后序遍歷的實(shí)現(xiàn)思想與前序、中序一樣。有兩種實(shí)現(xiàn)方式。

先說(shuō)第一種，同中序遍歷，只是中序時(shí)從棧中pop出一個(gè)結(jié)點(diǎn)打印，并訪問(wèn)當(dāng)前結(jié)點(diǎn)的右子樹(shù)。后序必須在訪問(wèn)完右子樹(shù)完在，在打印該結(jié)點(diǎn)。因此可先

看棧頂點(diǎn)是否被訪問(wèn)過(guò)，如果訪問(wèn)過(guò)，即已經(jīng)之前已經(jīng)做了其右子樹(shù)的訪問(wèn)因此可出棧，并打印，繼續(xù)訪問(wèn)棧頂點(diǎn)。如果未訪問(wèn)過(guò)，則對(duì)該點(diǎn)的訪問(wèn)標(biāo)記置為訪問(wèn)，訪問(wèn)該點(diǎn)右子樹(shù)?？梢园l(fā)現(xiàn)，相對(duì)于前序與中序，后序的思想是一致的，只是需要多一個(gè)存儲(chǔ)空間來(lái)表示結(jié)點(diǎn)狀態(tài)。python代碼實(shí)現(xiàn)如下：

 def post_traversal1(self):
  """method of traversing BiTree in in-order"""
  if self.root is None:
   return None
  else:
   node_stack = list()
   output_list = list()
   node = self.root
   while node is not None or len(node_stack):
    # if node is None which means it comes from a leaf-node' right,
    # pop the stack and get it's right node.
    # continue the circulating like this
    if node is None:
     visited = node_stack[-1]["visited"]
     # in in-order traversal, when pop up a node from stack , save it
     if visited:
      output_list.append(node_stack[-1]["node"].get_element())
      node_stack.pop(-1)
     else:
      node_stack[-1]["visited"] = True
      node = node_stack[-1]["node"]
      node = node.right
     continue
    # go-next when left node exists
    while node.left is not None:
     node_stack.append({"node": node, "visited": False})
     node = node.left
    # save the the last left node
    output_list.append(node.get_element())
    node = node.right
  return output_list

另外，后續(xù)遍歷還有一種訪問(wèn)方式?？紤]到后續(xù)遍歷是先左子樹(shù)，再右子樹(shù)再到父結(jié)點(diǎn)，倒過(guò)來(lái)看就是先父結(jié)點(diǎn)，再右子樹(shù)再左子樹(shù)。是不是很熟悉，是的這種遍歷方式就是前序遍歷的鏡像試，除了改變左右子樹(shù)訪問(wèn)順序連方式都沒(méi)變。再將輸出的結(jié)果倒序輸出一遍就是后序遍歷。同樣該方法也需要額外的空間存取輸出結(jié)果。python代碼如下：

def post_traversal2(self):
  """method of traversing BiTree in post-order"""
  if self.root is None:
   return None
  else:
   node_stack = list()
   output_list = list()
   node = self.root
   while node is not None or len(node_stack):
    # if node is None which means it comes from a leaf-node' left,
    # pop the stack and get it's left node.
    # continue the circulating like this
    if node is None:
     node = node_stack.pop().left
     continue
    while node.right is not None:
     node_stack.append(node)
     output_list.append(node.get_element())
     node = node.right
    output_list.append(node.get_element())
    node = node.left
  return output_list[::-1]

求葉子節(jié)點(diǎn)

求葉子節(jié)點(diǎn)有兩種方法，一種是廣度搜索優(yōu)先，即如果當(dāng)前節(jié)點(diǎn)存在左右子樹(shù)將左右子樹(shù)入隊(duì)。如果當(dāng)前節(jié)點(diǎn)不存在子樹(shù)，則該節(jié)點(diǎn)為葉節(jié)點(diǎn)。繼續(xù)出隊(duì)訪問(wèn)下一個(gè)節(jié)點(diǎn)。直至隊(duì)列為空，這個(gè)方法留給讀者去實(shí)現(xiàn)。

另外一種方法是，用深度搜索優(yōu)先。采用前序遍歷，當(dāng)判斷到一個(gè)結(jié)點(diǎn)不存在左右子樹(shù)時(shí)葉子結(jié)點(diǎn)數(shù)加一。代碼實(shí)現(xiàn)如下：


 def get_leaf_num(self):
  """method of getting leaf numbers of BiTree"""
  if self.root is None:
   return 0
  else:
   node_stack = list()
   node = self.root
   leaf_numbers = 0
   # only node exists and stack is not empty that will do this circulation
   while node is not None or len(node_stack):
    if node is None:
     """node is None then pop the stack and get the node.right"""
     node = node_stack.pop().right
     continue
    while node.left is not None:
     node_stack.append(node)
     node = node.left
    # if there is not node.right, leaf_number add 1
    node = node.right
    if node is None:
     leaf_numbers += 1
   return leaf_numbers

二叉樹(shù)的可視化

到此，除了樹(shù)的結(jié)點(diǎn)刪除（這個(gè)可以留給讀者去嘗試），這里已經(jīng)基本完成二叉樹(shù)的構(gòu)造及遍歷接口。但你可能真正在意的是如何繪制一顆二叉樹(shù)。接下來(lái)，本節(jié)將會(huì)通過(guò)python matplotlib.annotate繪制一顆二叉樹(shù)。

要繪制一棵二叉樹(shù)，首先需要對(duì)樹(shù)中的任意結(jié)點(diǎn)給出相應(yīng)相對(duì)坐標(biāo)(axis_max: 1)。對(duì)于一棵已知樹(shù)，已知深度 dd ，那么可以設(shè)初始根結(jié)點(diǎn)坐標(biāo)為(1/2,1−12d)(1/2,1−12d). (這個(gè)設(shè)置只是為了讓根結(jié)點(diǎn)盡量中間往上且不觸及axis)

假設(shè)已經(jīng)知道父結(jié)點(diǎn)的坐標(biāo)(xp,yp)(xp,yp)，當(dāng)前層數(shù)ll（記根節(jié)點(diǎn)為第0層），則從上往下畫(huà)其左右子樹(shù)的坐標(biāo)表達(dá)如下：

左子樹(shù)：

右子樹(shù)：

對(duì)應(yīng)代碼實(shí)現(xiàn)如下：

def get_coord(coord_prt, depth_le, depth, child_type="left"): if child_type == "left": x_child = coord_prt[0] - 1 / (2 ** (depth_le + 1)) elif child_type == "right": x_child = coord_prt[0] + 1 / (2 ** (depth_le + 1)) else: raise Exception("No other child type") y_child = coord_prt[1] - 1 / depth return x_child, y_child

如果知道當(dāng)前結(jié)點(diǎn)與父結(jié)點(diǎn)坐標(biāo)，即可以通過(guò)plt.annotate進(jìn)行結(jié)點(diǎn)與箭標(biāo)繪制，代碼實(shí)現(xiàn)如下：

def plot_node(ax, node_text, center_point, parent_point):
 ax.annotate(node_text, xy=parent_point, xycoords='axes fraction', xytext=center_point, textcoords='axes fraction',
    va="bottom", ha="center", bbox=NODE_STYLE, arrowprops=ARROW_ARGS)

已知樹(shù)深度，當(dāng)前結(jié)點(diǎn)及當(dāng)前結(jié)點(diǎn)所在層數(shù)，則可以通過(guò)上述計(jì)算方式計(jì)算左右子樹(shù)的結(jié)點(diǎn)坐標(biāo)。使用層次遍歷，即可遍歷繪制整棵樹(shù)。代碼實(shí)現(xiàn)如下：

 def view_in_graph(self):
  """use matplotlib.pypplot to help view the BiTree """
  if self.root is None:
   print("An Empty Tree, Nothing to plot")
  else:
   depth = self.get_depth()
   ax = node_plot.draw_init()
   coord0 = (1/2, 1 - 1/(2*depth))
   node_queue = list()
   coord_queue = list()
   node_plot.plot_node(ax, str(self.root.get_element()), coord0, coord0)
   node_queue.append(self.root)
   coord_queue.append(coord0)
   cur_level = 0
   while len(node_queue):
    q_len = len(node_queue)
    while q_len:
     q_node = node_queue.pop(0)
     coord_prt = coord_queue.pop(0)
     q_len = q_len - 1
     if q_node.left is not None:
      xc, yc = node_plot.get_coord(coord_prt, cur_level + 1, depth, "left")
      element = str(q_node.left.get_element())
      node_plot.plot_node(ax, element, (xc, yc), coord_prt)
      node_queue.append(q_node.left)
      coord_queue.append((xc, yc))
     if q_node.right is not None:
      xc, yc = node_plot.get_coord(coord_prt, cur_level + 1, depth, "right")
      element = str(q_node.right.get_element())
      node_plot.plot_node(ax, element, (xc, yc), coord_prt)
      node_queue.append(q_node.right)
      coord_queue.append((xc, yc))
    cur_level += 1
   node_plot.show()

最后，可以對(duì)如下的一顆二叉樹(shù)進(jìn)行測(cè)試：

dict_tree2 = {
 "element": 0,
 "left": {
  "element": 1,
  "left": 3,
  "right": {
   "element": 4,
   "left": 5,
   "right": 6,
  },
 },
 "right": {
  "element": 2,
  "left": 7,
  "right": {
   "element": 8,
   "left": {
    "element": 9,
    "left": 10,
    "right": 11,
   },
  },
 },
}

其繪制結(jié)果如下圖4：