二叉树的深度优先遍历与广度优先遍历

birdskyws

发布于 2018-09-12 15:02:03

1.8K0

发布于 2018-09-12 15:02:03

先说说为什么要遍历，二叉树不是已经排好序了么？如果大于当前节点值，搜索右子树，小于当前值，继续搜索左子树。参考两个sql： select id,name,grade from student where id=1 select id,name,grade from student where name='李四'

按id查找，id是主键，已经创建索引，用二叉树存储，id就是二叉树节点的key，可以按照二分查找法搜索。
按name搜索，只能采用遍历的方法，必须保证检查到树上的每一个节点，不能有遗漏。

数据库创建索引，可以加快搜索速度，但要维护额外空间。

深度优先遍历

先遍历子节点，再遍历兄弟节点。从根节点开始递归，如果存在子节点，继续遍历子节点。

    def traverse_d(self):
        self._traverse_d(self.root)
        
    ##深度优先遍历
    def _traverse_d(self,node):
        if(node == None):
            return
        self._traverse_d(node.lnode)
        self._traverse_d(node.rnode)
        print("key:%d==>value:%d"% (node.key,node.value))

广度优先遍历

先遍历兄弟节点，在遍历子节点。采用队列实现，出队时添加子节点。

    def traverse_w(self):
        self._traverse_w(self.root)
    ## 广度优先遍历
    def _traverse_w(self,node):
        q = Queue()
        q.put(node)
        while(not q.empty()):
            node = q.get()
            if(node.lnode!=None):
                q.put(node.lnode)
            if(node.rnode!=None):
                q.put(node.rnode)
            print("key:%d==>value:%d"% (node.key,node.value))