百度定义：二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树。
class Node(object): def __init__(self, item): self.item = item self.left = None self.right = None class Tree(object): def __init__(self): self.root = Node('root')二叉树的构建，先左子树后右子树
class Tree(object): def __init__(self): self.root = Node('root') def add(self, item): node = Node(item) if self.root is None: self.root = node else: q = [self.root] while True: pop_node = q.pop(0) if pop_node.left is None: pop_node.left = node return elif pop_node.right is None: pop_node.right = node return else: q.append(pop_node.left) q.append(pop_node.right) def get_parent(self, item): if self.root.item == item: return None # 根节点没有父节点 tmp = [self.root] # 将tmp列表，添加二叉树的根节点 while tmp: pop_node = tmp.pop(0) if pop_node.left and pop_node.left.item == item: #某点的左子树为寻找的点 return pop_node #返回某点，即为寻找点的父节点 if pop_node.right and pop_node.right.item == item: #某点的右子树为寻找的点 return pop_node #返回某点，即为寻找点的父节点 if pop_node.left is not None: #添加tmp 元素 tmp.append(pop_node.left) if pop_node.right is not None: tmp.append(pop_node.right) return None tmp = [self.root] while tmp: pop_node = tmp.pop(0) if pop_node.left and pop_node.left.item == item: return pop_node elif pop_node.right and pop_node.right.item == item: return pop_node if pop_node.left is None: tmp.append(pop_node.left) if pop_node.right is None: tmp.append(pop_node.right) return None def delete(self, item): if self.root is None: return False ''' 删除二叉树中的节点有三种情况： 1.该节点是叶子节点，只需要置空 2.该节点有一个孩子节点，只需要将该节点和孩子节点交换，然后置空该节点 3.该节点有左右孩子节点，就找到右子树的最后一个叶子，并且替代，删除该节点。 ''' parent = self.get_parent(item) if parent: del_node = parent.left if parent.left.item == item else parent.right if del_node.left is None: if parent.left.item == item: parent.left = del_node.right else: parent.right = del_node.right elif del_node.right is None: if parent.left.item == item: parent.left = del_node.left else: parent.right = del_node.left else: tmp_pre = del_node tmp_next = del_node.right # 寻找待删除节点右子树中的最左叶子节点并替代 if tmp_next.left is None: tmp_pre.right = tmp_next.right tmp_next.left = del_node.left tmp_next.right = del_node.right else: while tmp_next.left: tmp_pre = tmp_next tmp_next = tmp_next.left tmp_pre.left = tmp_next.right tmp_next.left = del_node.left tmp_next.right = del_node.right if parent.left.item == item: parent.left = tmp_next else: parent.right = tmp_next del del_node return True else: return False #中序遍历 左->中->右 def inorder(self, node): if node is None: return [] result = [node.item] left_item = self.inorder(node.left) right_item = self.inorder(node.right) return left_item + result + right_item #后序遍历 左->右->中 def postorder(self, node): if node is None: return [] result = [node.item] left_item = self.postorder(node.left) right_item = self.postorder(node.right) return left_item + right_item + result #先序遍历 中->左->右 def preorder(self, node): if node is None: return [] result = [node.item] left_item = self.preorder(node.left) right_item = self.preorder(node.right) return result + left_item + right_item