python数据结构之二叉树的统计与转换实例
发布时间:2020-12-16 20:15:53 所属栏目:Python 来源:网络整理
导读:一、获取二叉树的深度 就是二叉树最后的层次,如下图: 实现代码: 复制代码 代码如下: def getheight(self): ''' 获取二叉树深度 ''' return self.__get_tree_height(self.root) def __get_tree_height(self,root): if root is 0: return 0 if root.left is
一、获取二叉树的深度 实现代码: 复制代码 代码如下: def getheight(self): ''' 获取二叉树深度 ''' return self.__get_tree_height(self.root) def __get_tree_height(self,root): if root is 0: return 0 if root.left is 0 and root.right is 0: return 1 else: left = self.__get_tree_height(root.left) right = self.__get_tree_height(root.right) if left < right: return right + 1 else: return left + 1 二、叶子的统计 叶子就是二叉树的节点的 left 指针和 right 指针分别指向空的节点 复制代码 代码如下: def getleafcount(self): ''' 获取二叉树叶子数 ''' return self.__count_leaf_node(self.root) def __count_leaf_node(self,root): res = 0 if root is 0: return res if root.left is 0 and root.right is 0: res += 1 return res if root.left is not 0: res += self.__count_leaf_node(root.left) if root.right is not 0: res += self.__count_leaf_node(root.right) return res 三、统计叶子的分支节点 与叶子节点相对的其他节点 left 和 right 的指针指向其他节点 复制代码 代码如下: def getbranchcount(self): ''' 获取二叉树分支节点数 ''' return self.__get_branch_node(self.root) def __get_branch_node(self,root): if root is 0: return 0 if root.left is 0 and root.right is 0: return 0 else: return 1 + self.__get_branch_node(root.left) + self.__get_branch_node(root.right) 四、二叉树左右树互换 复制代码 代码如下: def replacelem(self): ''' 二叉树所有结点的左右子树相互交换 ''' self.__replace_element(self.root) def __replace_element(self,root): if root is 0: return root.left,root.right = root.right,root.left self.__replace_element(root.left) self.__replace_element(root.right) 这些方法和操作,都是运用递归。其实二叉树的定义也是一种递归。附上最后的完整代码: 复制代码 代码如下: # -*- coding: utf - 8 - *- class TreeNode(object): def __init__(self,left=0,right=0,data=0): self.left = left self.right = right self.data = data class BinaryTree(object): def __init__(self,root=0): self.root = root def is_empty(self): if self.root is 0: return True else: return False def create(self): temp = input('enter a value:') if temp is '#': return 0 treenode = TreeNode(data=temp) if self.root is 0: self.root = treenode treenode.left = self.create() treenode.right = self.create() def preorder(self,treenode): '前序(pre-order,NLR)遍历' if treenode is 0: return print treenode.data self.preorder(treenode.left) self.preorder(treenode.right) def inorder(self,treenode): '中序(in-order,LNR' if treenode is 0: return self.inorder(treenode.left) print treenode.data self.inorder(treenode.right) def postorder(self,treenode): '后序(post-order,LRN)遍历' if treenode is 0: return self.postorder(treenode.left) self.postorder(treenode.right) print treenode.data def preorders(self,treenode): '前序(pre-order,NLR)非递归遍历' stack = [] while treenode or stack: if treenode is not 0: print treenode.data stack.append(treenode) treenode = treenode.left else: treenode = stack.pop() treenode = treenode.right def inorders(self,treenode): '中序(in-order,LNR) 非递归遍历' stack = [] while treenode or stack: if treenode: stack.append(treenode) treenode = treenode.left else: treenode = stack.pop() print treenode.data treenode = treenode.right def postorders(self,treenode): '后序(post-order,LRN)非递归遍历' stack = [] pre = 0 while treenode or stack: if treenode: stack.append(treenode) treenode = treenode.left elif stack[-1].right != pre: treenode = stack[-1].right pre = 0 else: pre = stack.pop() print pre.data # def postorders(self,treenode): # '后序(post-order,LRN)非递归遍历' # stack = [] # queue = [] # queue.append(treenode) # while queue: # treenode = queue.pop() # if treenode.left: # queue.append(treenode.left) # if treenode.right: # queue.append(treenode.right) # stack.append(treenode) # while stack: # print stack.pop().data def levelorders(self,treenode): '层序(post-order,LRN)非递归遍历' from collections import deque if not treenode: return q = deque([treenode]) while q: treenode = q.popleft() print treenode.data if treenode.left: q.append(treenode.left) if treenode.right: q.append(treenode.right) def getheight(self): ''' 获取二叉树深度 ''' return self.__get_tree_height(self.root) def __get_tree_height(self,root): if root is 0: return 0 if root.left is 0 and root.right is 0: return 1 else: left = self.__get_tree_height(root.left) right = self.__get_tree_height(root.right) if left < right: return right + 1 else: return left + 1 def getleafcount(self): ''' 获取二叉树叶子数 ''' return self.__count_leaf_node(self.root) def __count_leaf_node(self,root): res = 0 if root is 0: return res if root.left is 0 and root.right is 0: res += 1 return res if root.left is not 0: res += self.__count_leaf_node(root.left) if root.right is not 0: res += self.__count_leaf_node(root.right) return res def getbranchcount(self): ''' 获取二叉树分支节点数 ''' return self.__get_branch_node(self.root) def __get_branch_node(self,root): if root is 0: return 0 if root.left is 0 and root.right is 0: return 0 else: return 1 + self.__get_branch_node(root.left) + self.__get_branch_node(root.right) def replacelem(self): ''' 二叉树所有结点的左右子树相互交换 ''' self.__replace_element(self.root) def __replace_element(self,root.left self.__replace_element(root.left) self.__replace_element(root.right) node1 = TreeNode(data=1) node2 = TreeNode(node1,2) node3 = TreeNode(data=3) node4 = TreeNode(data=4) node5 = TreeNode(node3,node4,5) node6 = TreeNode(node2,node5,6) node7 = TreeNode(node6,7) node8 = TreeNode(data=8) root = TreeNode(node7,node8,'root') bt = BinaryTree(root) print u''' 生成的二叉树 ------------------------ root 7 8 6 2 5 1 3 4 ------------------------- ''' (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |