數據結構之二叉查找樹的代碼實現

本節繼續對上一節BST的功能實現
在實現之前，先對要實現的功能進行一下簡單的介紹

BST的幾種常見遍歷方式

以一個簡化的樹為例，一棵樹包含根(父)結點和其左子樹及右子樹：

遍歷順序的先后是指根(父)結點被遍歷的相對順序

先序遍歷：指的是“先根后左再右”

中序遍歷：指的是“先左后根再右”

后序遍歷：指的是“先左后又再根”

如果子樹也存在子樹，則也需按此規則進行遍歷，一般是遞歸地進行遍歷

4. 層序遍歷：指按樹層次順序，從根結點往下，子結點從左到右地遍歷

5. 獲取樹的最大深度：

• 實現步驟（使用遞歸）:
  1.如果根結點為空,則最大深度為0 ;
  2.計算左子樹的最大深度;
  3.計算右子樹的最大深度;
  4.當前樹的最大深度=左子樹的最大深度和右子樹的最大深度中的較大者+1

接下來對BST的這些遍歷功能進行實現

實現功能

pre_ergodic()實現BST的先序遍歷，返回遍歷的元素組成的列表

mid_ergodic()實現BST的中序遍歷，返回遍歷的元素組成的列表

post_ergodic()實現BST的后序遍歷，返回遍歷的元素組成的列表

layer_ergodic()實現BST的層序遍歷，返回遍歷的元素組成的列表

max_depth()獲取樹的最大深度

Python代碼實現

注：注釋的測試代碼是前一節的實現，可以忽略

import operatorclass Node:def __init__(self, key=None, value=None):self.key = keyself.value = valueself.left = Noneself.right = Noneclass BinarySearchTree:def __init__(self):self.root = Noneself.len = 0def size(self):return self.lendef put(self, _key, _value):"""Put an element into this tree and generate a new BST"""def put_into(node, _key, _value):"""Adjust position of new inserted nodeby BST character:left > root > right"""if not node:self.len += 1return Node(_key, _value)if operator.lt(_key, node.key):node.left = put_into(node.left, _key, _value)elif operator.gt(_key, node.key):node.right = put_into(node.right, _key, _value)elif operator.eq(_key, node.key):node.value = _valuereturn nodeself.root = put_into(self.root, _key, _value)return self.rootdef get(self, _key):"""Get a value responding to the given _key from this tree"""def get_value_by_key(node, _key):if not node:returnif operator.lt(_key, node.key):return get_value_by_key(node.left, _key)elif operator.gt(_key, node.key):return get_value_by_key(node.right, _key)else:return node.valuereturn get_value_by_key(self.root, _key)## def delete(self, _key):# """Delete a node responding to the giving key(_key)"""# def delete_value_by_key(node, _key):# if not node:# return# if operator.lt(_key, node.key):# node.left = delete_value_by_key(node.left, _key)# elif operator.gt(_key, node.key):# node.right = delete_value_by_key(node.right, _key)# else:# self.len -= 1# to_delete_node = node# if node == self.root:# self.root = None# return# # node = None# if not to_delete_node.left:# return to_delete_node.right# elif not to_delete_node.right:# return to_delete_node.left# else:# min_right_tree = to_delete_node.right# pre = min_right_tree# while min_right_tree.left:# pre = min_right_tree# min_right_tree = min_right_tree.left# pre.left = None# min_right_tree.left = to_delete_node.left# min_right_tree.right = to_delete_node.right# return min_right_tree# return delete_value_by_key(self.root, _key)## def min_key(self):# """Find the minimum key"""# def min_node(node):# while node.left:# node = node.left# return node# return min_node(self.root).key## def max_key(self):# """Find the maximum key"""# def max_node(node):# while node.right:# node = node.right# return node# return max_node(self.root).keydef pre_ergodic(self):"""Get every key of this tree, pre_ergodic; Return a list of its keys"""def pre_ergodic(node, keys_list):"""Root --> Left --> Right"""if not node:returnkeys_list.append(node.key)if node.left:pre_ergodic(node.left, keys_list)if node.right:pre_ergodic(node.right, keys_list)keys_list = []pre_ergodic(self.root, keys_list)return keys_listdef mid_ergodic(self):def mid_ergodic(node, keys_list):"""Left --> Root --> Right"""if not node:returnif node.left:mid_ergodic(node.left, keys_list)keys_list.append(node.key)if node.right:mid_ergodic(node.right, keys_list)keys_list = []mid_ergodic(self.root, keys_list)return keys_listdef post_ergodic(self):def post_ergodic(node, keys_list):"""Left --> Right --> Root"""if not node:returnif node.left:post_ergodic(node.left, keys_list)if node.right:post_ergodic(node.right, keys_list)keys_list.append(node.key)keys_list = []post_ergodic(self.root, keys_list)return keys_listdef layer_ergodic(self):"""Root-->Left --> Right"""queue = [self.root]keys = []while queue:node = queue.pop(0)keys.append(node.key)if node.left:queue.append(node.left)if node.right: queue.append(node.right)return keysdef max_depth(self):"""Get the max depth of this tree"""def max_depth(node):max_left, max_right = 0, 0if not node:return 0if node.left:max_left = max_depth(node.left)if node.right:max_right = max_depth(node.right)return max(max_left, max_right) + 1return max_depth(self.root)

代碼測試

if __name__ == '__main__':BST = BinarySearchTree()BST.put('e', '5')BST.put('b', '2')BST.put('g', '7')BST.put('a', '1')BST.put('d', '4')BST.put('f', '6')BST.put('h', '8')BST.put('c', '3')print(f"The size of this binary tree now is {BST.size()}\n")print("pre_order:\n", [(key, BST.get(key)) for key in BST.pre_ergodic()])print("mid_order:\n", [(key, BST.get(key)) for key in BST.mid_ergodic()])print("post_order:\n", [(key, BST.get(key)) for key in BST.post_ergodic()])print("layer_order:\n", [(key, BST.get(key)) for key in BST.layer_ergodic()])print(f"Get the maximum depth of this tree: {BST.max_depth()}")

測試結果

The size of this binary tree now is 8pre_order:[('e', '5'), ('b', '2'), ('a', '1'), ('d', '4'), ('c', '3'), ('g', '7'), ('f', '6'), ('h', '8')] mid_order:[('a', '1'), ('b', '2'), ('c', '3'), ('d', '4'), ('e', '5'), ('f', '6'), ('g', '7'), ('h', '8')] post_order:[('a', '1'), ('c', '3'), ('d', '4'), ('b', '2'), ('f', '6'), ('h', '8'), ('g', '7'), ('e', '5')] layer_order:[('e', '5'), ('b', '2'), ('g', '7'), ('a', '1'), ('d', '4'), ('f', '6'), ('h', '8'), ('c', '3')] Get the maximum depth of this tree: 4Process finished with exit code 0

根據前/后序+中序確定這顆二叉查找樹：

最大深度顯然是4

總結

以上是生活随笔為你收集整理的数据结构之二叉树：二叉查找树的先序、中序、后序、层序遍历，Python代码实现——10(续)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。