二叉搜索树BST广度优先搜索遍历BFS计算树高度，非递归，binarytree，python

骑猪看日落 2023-10-02 15:52 6阅读 0赞

基本原理：首先对二叉树搜索树进行BFS广度优先搜索遍历，搜索遍历后的节点访问依次顺序的存放在数组中，那么此时数组中**最后一个节点，即是树中距离根最远的节点**。然后用这个节点逆向的沿着父节点一层一层的往上爬，每爬一层就计数为1，直到根节点没有了父节点为止，算法结束。最终累计的计数即为树的高度。也就是说，广度遍历搜索是一种层次推进的搜索遍历，具体在BST二叉树搜索树中，一层代表数的高度1，对层高计数，即为该树的高度。

from binarytree import bst, get_parent
    
    
    def app():
        t = bst(height=0, is_perfect=False)
        print(t)
        print('标准API获得的树高', t.height)
    
        print('-----')
        h = get_tree_height(t)
        print('广度遍历思想求得树高', h)
    
    
    def get_tree_height(node):
        most_far_edge_node = node.levelorder.pop()
        print('most_far_edge_node', most_far_edge_node.value)
    
        tree_height = 0
        while True:
            print('-')
            p = get_parent(node, most_far_edge_node)
            if p is not None:
                print('parent', most_far_edge_node.value, '->', p.value)
                tree_height = tree_height + 1
                most_far_edge_node = p
            else:
                break
    
        return tree_height
    
    
    if __name__ == '__main__':
        app()

输出：

0________
             \
        ______5__________________
       /                         \
      1__                  _______57_________
         \                /                  \
          3          ____47               ____62
         / \        /      \             /
        2   4     _23       48         _60
                 /   \        \       /   \
                20    35       56    58    61
    
    标准API获得的树高 5
    -----
    most_far_edge_node 61
    -
    parent 61 -> 60
    -
    parent 60 -> 62
    -
    parent 62 -> 57
    -
    parent 57 -> 5
    -
    parent 5 -> 0
    -
    广度遍历思想求得树高 5