本文共 4571 字，大约阅读时间需要 15 分钟。

一.二叉树三种常见用法：

1.堆

• 最大堆：根节点大于等于其子节点
• 最小堆：根节点小于等于其子节点

2.二叉搜索树（BST：Binary Search Tree）

• 左小右大：给定节点的左子树要小于它，右子树要大于它

3.表达式树

• 把表达式的每个量用二叉树表示

4.遍历

• 前序遍历：先遍历根节点
• 中序遍历：第二遍历根节点
• 后序遍历：最后遍历根节点
• 层序遍历：从上到下，从左到右，一层一层遍历
• 深度优先遍历(DFS: Depth First Search):类似于先序，中序，后序
• 广度优先遍历(BFS: Breadth First Search):类似于层序

5.结构

二.二叉树的遍历实现

class Node(object):    """节点类"""    def __init__(self, elem=-1, lchild=None, rchild=None):        self.elem = elem        self.lchild = lchild        self.rchild = rchildclass Tree(object):    """树类"""    def __init__(self):        self.root = Node()        self.myQueue = []    def add(self, elem):        """为树添加节点"""        node = Node(elem)        if self.root.elem == -1:  # 如果树是空的，则对根节点赋值            self.root = node            self.myQueue.append(self.root)        else:            # 末尾总是队列的头去掉, 所以总是把第0个节点赋值把此节点赋值给treeNOde,以便操作            treeNode = self.myQueue[0]            # 判断此节点的左右子树            if treeNode.lchild == None:                treeNode.lchild = node                self.myQueue.append(treeNode.lchild)            else:                # 赋值右子树                treeNode.rchild = node                self.myQueue.append(treeNode.rchild)                # 此节点赋值完成, 将此节点丢弃                self.myQueue.pop(0)

2.递归实现先序，中序，后续遍历

def front_digui(self, root):            """利用递归实现树的先序遍历"""            if root == None:                return            print(root.elem)            self.front_digui(root.lchild)            self.front_digui(root.rchild)        def middle_digui(self, root):            """利用递归实现树的中序遍历"""            if root == None:                return            self.middle_digui(root.lchild)            print(root.elem)            self.middle_digui(root.rchild)        def later_digui(self, root):            """利用递归实现树的后序遍历"""            if root == None:                return            self.later_digui(root.lchild)            self.later_digui(root.rchild)            print(root.elem)

3.堆栈实现先序，中序，后续遍历

def front_stack(self, root):        """利用堆栈实现树的先序遍历，先打印节点的值，再向左子树遍历"""        if root == None:            return        myStack = []        node = root        while node or myStack:            while node:  # 从根节点开始，一直找它的左子树                print(node.elem) # 先输出当前节点的值                myStack.append(node) # 把左边的节点加入到堆栈                node = node.lchild            node = myStack.pop() # 把节点提取出来，以免重复，以便对节点进行操作            node = node.rchild     def middle_stack(self, root):        """利用堆栈实现树的中序遍历，先打印左子树的值，这个子树的右节点为空，下一个循环就可以打印本节点的值，堆栈实现对节点的控制"""        if root == None:            return        myStack = []        node = root        while node or myStack:            while node:  # 从根节点开始，一直找它的左子树                myStack.append(node)                node = node.lchild            node = myStack.pop()  # 把节点提取出来，以免重复，以便对节点进行操作            print(node.elem) #             node = node.rchild        def later_stack(self, root):            """利用堆栈实现树的后序遍历"""            if root == None:                return            myStack1 = []            myStack2 = []            node = root            myStack1.append(node)            while myStack1:  # 这个while循环的功能是找出后序遍历的逆序，存在myStack2里面                node = myStack1.pop()                if node.lchild:                    myStack1.append(node.lchild)                if node.rchild:                    myStack1.append(node.rchild)                myStack2.append(node)            while myStack2:  # 将myStack2中的元素出栈，即为后序遍历次序                print(myStack2.pop().elem)

4.实现层序遍历

def level_queue(self, root):                """利用队列实现树的层次遍历"""                if root == None:                    return                myQueue = []                node = root                myQueue.append(node)                while myQueue:                    node = myQueue.pop(0)                    print(node.elem)                    if node.lchild != None:                        myQueue.append(node.lchild)                    if node.rchild != None:                        myQueue.append(node.rchild)            def level_queue(self, root):                """利用堆栈实现树的层次遍历"""                if root == None:                    return                myQueue = []                node = root                myQueue.append(node)                while myQueue:                    node = myQueue.pop()                    print(node.elem)                    if node.rchild != None:                        myQueue.append(node.rchild)                    if node.lchild != None:                        myQueue.append(node.lchild)

转载地址：http://zzjmf.baihongyu.com/