二叉树 队列 数组 层次遍历

timehorse · · 906 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

bfs 和 队列

学过数据结构的都知道,二叉树的层次遍历。

层次遍历利用的数据结构是队列。

那么,

思考一下

为什么层次遍历,要用到队列,而不是其他的数据结构,比如栈呢?换句话说,队列在二叉树的层次遍历过程中起到了什么作用呢?

队列在二叉树层次遍历中的作用

我们知道,二叉树的结构如下:

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

从结构中大致可以知道,二叉树的根跟左右还是是采用链表的形式联系的,父节点,保存了左右孩子的指针,所以,我们知道了父节点,必然也就知道了左右孩子的信息。

但是,在一个二叉树中,同层之间的信息通过什么联系在一起的呢?
7
5 8
2 6 9 12

比如上图中的2,6,9,12,这时层次遍历的时候,我们如何保持同层之间的顺序呢?这个就应该是靠队列的作用了。

队列的一个特点是,元素是先进先出,我们可以把同层的兄弟元素依次入队,然后,在出队的过程中再遍历左右孩子,循环以上操作即可。

通过数组创建二叉树vs二叉树的层次遍历

今天,做leetcode上的一道二叉树层次遍历的题目,由于需要在本地调试,所以想在本地创建一个二叉树,于是想到了,通过数组去创建一个二叉树,也就是将一个数组转化为完全二叉树。

最后发现,原来,通过数组创建二叉树和二叉树的层次遍历其实存在着某种联系,他们是一个相反的过程。

也就是通过数组创建二叉树是将数组转化为二叉树,而二叉树的层次遍历其实是将二叉树转化为数组的形式。

确实很妙。

下面给出代码

python

#!/usr/bin/python 
#-*- coding: UTF-8 -*-
class node():
    def __init__(self,k=None,l=None,r=None):
        self.key=k;
        self.left=l;
        self.right=r;
 
def create_tree_by_array(input_list):
  """
  通过数组创建二叉树,
  其实是层次遍历
  需要利用节点队列 
  """  

  def _createNode(item):
    if item is '#':
      return None
    else:
      return node(k=item)

  queue = []

  root = _createNode(input_list.pop(0))
  queue.append(root)

  while len(input_list) > 0:
    curNode = queue.pop(0)
    curNode.left = _createNode(input_list.pop(0))
    curNode.right = _createNode(input_list.pop(0))
    if curNode.left: 
      queue.append(curNode.left)
    if curNode.right:
      queue.append(curNode.right)

  return root

def traverse_tree_by_level(root):
  """
  层次遍历
  需要利用节点队列
  """

  queue = []
  output_list = []
  queue.append(root)
  output_list.append(root.key)
  while len(queue) > 0:
    curNode = queue.pop(0)
    if curNode.left:
      output_list.append(curNode.left.key)
      queue.append(curNode.left)
    if curNode.right:
      output_list.append(curNode.right.key)
      queue.append(curNode.right)
    
  print(output_list)

def inorder(root):     #中序遍历
    if root is None:
        return ;
    else:
        inorder(root.left);
        print(root.key,)
        inorder(root.right);

tree_data_list = [3,9, 20, '#','#', 15,7]
root=None;     # 测试代码
root=create_tree_by_array(tree_data_list);
inorder(root);
traverse_tree_by_level(root)

golang

package main

import (
    "fmt"
)

type Node struct {
    Value int
    Left  *Node
    Right *Node
}

func CreateNode(item int) *Node {

    if item == -1 {
        return nil
    }

    return &Node{item, nil, nil}
}

func CreateByBreadthFirstSearch(inputList []int) *Node {

    queue := []*Node{}
    root := CreateNode(inputList[0])
    queue = append(queue, root)

    inputList = inputList[1:]

    for len(inputList) > 0 {
        curNode := queue[0]
        queue = queue[1:]

        curNode.Left = CreateNode(inputList[0])
        if curNode.Left != nil {
            queue = append(queue, curNode.Left)
        }
        inputList = inputList[1:]

        curNode.Right = CreateNode(inputList[0])
        if curNode.Right != nil {
            queue = append(queue, curNode.Right)
        }
        inputList = inputList[1:]

    }

    return root
}

func (node *Node) BreadthFirstSearch() {
    if node == nil {
        return
    }
    output_list := []int{}
    queue := []*Node{node}
    for len(queue) > 0 {
        curNode := queue[0]
        queue = queue[1:]
        output_list = append(output_list, curNode.Value)
        if curNode.Left != nil {
            queue = append(queue, curNode.Left)
        }
        if curNode.Right != nil {
            queue = append(queue, curNode.Right)
        }
    }
    for _, v := range output_list {
        fmt.Print(v, " ")
    }
}

func main() {

    input_list := []int{3, 7, 9, -1, -1, 20, 4}
    root := CreateByBreadthFirstSearch(input_list)
    root.BreadthFirstSearch()
}

有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:timehorse

查看原文:二叉树 队列 数组 层次遍历

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

906 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传