一、获取二叉树的深度就是二叉树最后的层次，如下图：
实现代码：
代码如下:
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): if root is 0: return root.left, root.right = root.right, root.left self.__replace_element(root.left) self.__replace_element(root.right)node1 = treenode(data=1)node2 = treenode(node1, 0, 2)node3 = treenode(data=3)node4 = treenode(data=4)node5 = treenode(node3, node4, 5)node6 = treenode(node2, node5, 6)node7 = treenode(node6, 0, 7)node8 = treenode(data=8)root = treenode(node7, node8, 'root') bt = binarytree(root)print u'''生成的二叉树------------------------ root 7 8 6 2 51 3 4-------------------------'''