首页 > 代码库 > 数据结构-- 二叉树

数据结构-- 二叉树

2024-07-28 21:50:36   230人阅读

#!/use/bin/env python

#encoding=gbk
 
import Queue
 
class Stack():
    def __init__(self, volume = 0):
        self.list = [0 for i in range(0, 1000)] if volume == 0 else [0 for i inrange(0,volume)]
        self.top = 0
 
    def push(self, element):
        if self.list != None:
            self.top += 1
            self.list[self.top] = element
 
    def pop(self):
        if self.list != None and self.top >= 0:
            ele = self.list[self.top]
            self.list[self.top] = None
            self.top -= 1
            return ele
        return None
    def empty(self):
        return self.top == 0
     
‘‘‘
二叉树的二叉链表表示
       A
      / \
     B   C
    /   / \
   D   E   F
    \     /
     G   H
先根遍历：访问根节点，遍历左子树，遍历右子树
中根遍历：遍历左子树，访问根节点，遍历右子树
后根遍历：遍历左子树，遍历右子树，访问根节点
preOrder  A B D G C E F H
inOrder   D G B A E C H F
postOrder G D B E H F C A
 
深度优先遍历（先根遍历），广度优先遍历（层次遍历）
depthFrist A  B  D  G  C  E  F  H
breadthFir A  B  C  D  E  F  G  H
‘‘‘
 
class BinaryNode():
    def __init__(self, data, left = None, right = None):
        self.data = data
        self.left = left
        self.right = right
 
    def isLeaf(self):
        return self.left == None and self.right == None
 
    def toString(self):
        return self.data
 
 
class BinaryTree():
    def __init__(self, root = None):
        self.root = root
     
    def isEmpty(self):
        return self.root == None
 
    def getRoot(self):
        return self.root
     
    def preOrder(self, node):
        if node != None:
            cstr = node.data
            lstr = self.preOrder(node.left)
            rstr = self.preOrder(node.right)
            return cstr + lstr + rstr
        return ""
    def inOrder(self, node):
        if node != None:
            lstr = self.inOrder(node.left)
            cstr = node.data
            rstr = self.inOrder(node.right)
            return lstr + cstr + rstr
        return ""
    def postOrder(self, node):
        if node != None:
            lstr = self.postOrder(node.left)
            rstr = self.postOrder(node.right)
            cstr = node.data
            return lstr + rstr + cstr
        return ""
 
    """get tree‘s height"""
    def height(self, node):
        if node != None:
            lh = self.height(node.left)
            rh = self.height(node.right)
            return lh + 1 if lh > rh else rh + 1
        return 0
 
    """get tree‘s node number"""
    def count(self, node):
        if node != None:
            lc = self.count(node.left)
            rc = self.count(node.right)
            return lc + rc + 1
        return 0
 
    """find node, and it‘s data is X """
    def search(self, value, node):
        tnode = None
        if node != None and value != None and value != "":
            if node.data == value:
                tnode = node
            else:
                tnode = self.search(value, node.left)
                if tnode == None:
                    tnode = self.search(value, node.right)
        return tnode
    """get parent node"""
    def getParent(self, node, rnode):
        tnode = None
        if rnode != None and node != None:
            if rnode.left == node or rnode.right == node:
                tnode = rnode
            else:
                tnode = self.getParent(node, rnode.left)
                if tnode == None:
                    tnode = self.getParent(node, rnode.right)
        return tnode
    """depth first search base on stack, like preOrder(non-recursive)"""
    def depth_first_search(self, node):
        list = []
        if node != None:
            stack = Stack()
            stack.push(node)
            while not stack.empty():
                tmp = stack.pop()
                list.append(tmp)
                if tmp.right != None: stack.push(tmp.right)
                if tmp.left != None: stack.push(tmp.left)
        return list
     
    """depth first search base on queue, like levelOrder(non-recursive)"""
    def breadth_first_search(self, node):
        list = []
        if node != None:
            queue = Queue.Queue()
            queue.put(node)
            while not queue.empty():
                tmp = queue.get()
                list.append(tmp)
                if tmp.left != None: queue.put(tmp.left)
                if tmp.right != None: queue.put(tmp.right)
        return list
 
if __name__ == ‘__main__‘:
    print "binary tree training."
    LNode = BinaryNode("B", BinaryNode("D", None, BinaryNode("G",None,None)), None)
    RNode = BinaryNode("C", BinaryNode("E", None, None), BinaryNode("F", BinaryNode("H", None, None), None))
    root = BinaryNode("A", LNode, RNode)
    tree = BinaryTree(root)
    print "pre order : %s"%(" ".join(tree.preOrder(tree.getRoot())))
    print "in order  : %s"%(" ".join(tree.inOrder(tree.getRoot())))
    print "post order: %s"%(" ".join(tree.postOrder(tree.getRoot())))
 
    list = tree.depth_first_search(tree.getRoot())
    if list != None:
        print "depth  first  search: ",
        for xn in list:
            print xn.data + " ",
        print ""
     
    list = tree.breadth_first_search(tree.getRoot())
    if list != None:
        print "breadth first search: ",
        for xn in list:
            print xn.data + " ",
        print ""

数据结构-- 二叉树


联系
我们