二叉树（BTree）
话说python的BTree插入节点，用队列bfs插入，效率贼低吧
class Node: """节点类""" def __init__(self, data = -1, left = None, right = None): self.data = data self.left = left self.right = right
class BTree: """树类""" def __init__(self, root = None): self.root = root def insert(self, data): node = Node(data) if self.root is None: self.root = node return queue = [self.root] while queue: cur = queue.pop(0) if cur.left is None: cur.left = node return elif cur.right is None: cur.right = node return else: queue.append(cur.left) queue.append(cur.right) # 先序遍历 def preorder(self, root): if root is None: return [] res = [root.data] left_res = self.preorder(root.left) right_res = self.preorder(root.right) return res + left_res + right_res # 中序遍历 def inorder(self, root): if root is None: return [] res = [root.data] left_res = self.inorder(root.left) right_res = self.inorder(root.right) return left_res + res + right_res # 后序遍历 def postorder(self, root): if root is None: return [] res = [root.data] left_res = self.postorder(root.left) right_res = self.postorder(root.right) return left_res + right_res + res # 层序遍历 def traverse(self): if self.root is None: return None queue = [self.root] res = [self.root.data] while queue != []: cur = queue.pop(0) if cur.left is not None: queue.append(cur.left) res.append(cur.left.data) if cur.right is not None: queue.append(cur.right) res.append(cur.right.data) return res # 获取树高 def height(self, root): if root is None: return 0 return 1 + max(self.height(root.left), self.height(root.right)) # 所有叶子节点 def leaves(self, root): if root is None: return [] if root.left is None and root.right is None: return [root.data] return self.leaves(root.left) + self.leaves(root.right)
二叉搜索树（BSTree）
主要是对节点的封装
class Node: """节点类""" def __init__(self, data = -1, left = None, right = None, father = None): self.data = data self.left = left self.right = right self.father = father def __str__(self): return str(self.data) @staticmethod def find(root, data): if root == None: return None if root.data == data: return root if root.data < data: return Node.find(root.right, data) return Node.find(root.left, data) @staticmethod def insert(root, data): if root == None: return Node(data) if root.data == data: return root if root.data < data: root.right = Node.insert(root.right, data) else: root.left = Node.insert(root.left, data) return root @staticmethod def next(root): if root.right != None: root = root.right while root.left != None: root = root.left return root while root.father != None and root != root.father.left: root = root.father return root.father @staticmethod def delete(root, data): if root == None: return None if root.data < data: root.right = Node.delete(root.right, data) elif root.data > data: root.left = Node.delete(root.left, data) else: if root.left == None or root.right == None: tmp = root.left if root.left != None else root.right del root return tmp tmp = Node.next(root) root.data = tmp.data return Node.delete(root.right, tmp.data) # 这里别忘记了，无语子！！！ return root
这里封装的效果就体现出来了，多简洁的BSTree（hhh
方法同上，外加一个find_k()（之后在补优化方法，如果没改，那我就是忘了
class BSTree: """二叉搜索树类""" def __init__(self, root = None): root = Node() self.root = root def insert(self, data): self.root.left = Node.insert(self.root.left, data) def delete(self, data): # 这里也要接住，万一删的是root self.root.left = Node.delete(self.root.left, data) def find(self, data): return Node.find(self.root.left, data) # 查找第k小（1-n） def find_k(self, k): # 好像不好维护 size， insert如果是存在的，size不++，以后在优化，hhh res = self.inorder(self.root.left) if k > len(res): return -1 return res[k - 1] def inorder(self, root): if root is None: return [] res = [root.data] left_res = self.inorder(root.left) right_res = self.inorder(root.right) return left_res + res + right_res
t = BSTree() print(t.root) for i in range(10, 0, -1): t.insert(i * 3 % 7 - 10) print(t.inorder(t.root.left)) print(t.find(15)) print(t.find_k(3))
吐槽一下：我花了不下5小时弄这个，大概就是模仿之前C++敲过的代码，写出的一个我自己理解的python版本。边角的细节还是很多的，尤其是对节点的删除操作。
代码应该是基本没问题，反正我能正常的跑出来，主要是为了复习一下二叉树的实现以及思想，我并没有去写一些概念性的东西，反正都在代码里了。
