如何将二叉树存储为一维数组？

Question

如何将数据构造成二叉树排序输出一维数组？

既然已经把数据构造成二叉树了，那么如何将二叉树递归求解为一维数组呢，代码和数据如下：

数据

$nodes = array(8,3,10,1,6,14,4,7,13);

构造二叉树代码

function insertNode($node,$newNode){

    //var_dump($node);
    //var_dump($newNode);
    //exit;
    if ($node['key'] < $newNode['key']){

        if (empty($node['right'])){
            $node['right'] = $newNode;
        }else{
            $node['right'] = insertNode($node['right'],$newNode);
        }
    }elseif ($node['key'] > $newNode['key']){

        if (empty($node['left'])){
            $node['left'] = $newNode;
        }else{
            $node['left'] = insertNode($node['left'],$newNode);
        }
    }

    return $node;
}

function tree($nodes)
{
    $node = [
        'key' => '',
        'left' => '',
        'right' => ''
    ];
    $newNode = [
        'key' => '',
        'left' => '',
        'right'=> ''
    ];

    foreach ($nodes as $key => $value){
        //insert($value,$key);
        if($key == 0)
        {
            $node['key'] = $value;  
            continue;
        }

        $newNode['key'] = $value;
        //Constructing a binary tree
        $node = insertNode($node,$newNode);

    }

    //Recursive solution
    $node = midSortNode($node);

    return $node;
}


var_dump(tree($nodes));

下面是我构造的二叉树

array (size=3)
  'key' => int 8
  'left' => 
    array (size=3)
      'key' => int 3
      'left' => 
        array (size=3)
          'key' => int 1
          'left' => string '' (length=0)
          'right' => string '' (length=0)
      'right' => 
        array (size=3)
          'key' => int 6
          'left' => 
            array (size=3)
              ...
          'right' => 
            array (size=3)
              ...
  'right' => 
    array (size=3)
      'key' => int 10
      'left' => string '' (length=0)
      'right' => 
        array (size=3)
          'key' => int 14
          'left' => 
            array (size=3)
              ...
          'right' => string '' (length=0)

我需要递归地将二叉树分类成一个有序的一维数组

我的代码如下

function midSortNode($node){
    $sortArr = [];
    if (!empty($node)){
        $sortArr[] = midSortNode($node['left']);
        //$sortArr['left'] = midSortNode($node['left']);

        array_push($sortArr,$node['key']);

        $sortArr[] = midSortNode($node['right']);
        //$sortArr['right'] = midSortNode($node['right']);
    }

    return $sortArr;
}

var_dump(midSortNode($node));

这是结果，但不是我想要的

  0 => 
    array (size=3)
      0 => 
        array (size=3)
          0 => 
            array (size=0)
              ...
          1 => int 1
          2 => 
            array (size=0)
              ...
      1 => int 3
      2 => 
        array (size=3)
          0 => 
            array (size=3)
              ...
          1 => int 6
          2 => 
            array (size=3)
              ...
  1 => int 8
  2 => 
    array (size=3)
      0 => 
        array (size=0)
          empty
      1 => int 10
      2 => 
        array (size=3)
          0 => 
            array (size=3)
              ...
          1 => int 14
          2 => 
            array (size=0)
              ...

二叉树的解法如下

array (size=9)
  0 => int 1
  1 => int 3
  2 => int 4
  3 => int 6
  4 => int 7
  5 => int 8
  6 => int 10
  7 => int 13
  8 => int 14

Answer 1

我假设您对到目前为止的步骤感到满意，所以主要代码没有改变。我认为您需要做的就是将最终树中的数据提取到一维数组中。由于项目都是叶节点并且按顺序排列，您只需使用 array_walk_recursive() 遍历所有节点并将它们添加到新数组中...

$tree = tree($nodes);
array_walk_recursive( $tree, 
    function ($data) use (&$output) { $output[] = $data;} );
print_r($output);

给...

Array
(
    [0] => 1
    [1] => 3
    [2] => 4
    [3] => 6
    [4] => 7
    [5] => 8
    [6] => 10
    [7] => 13
    [8] => 14
)

编辑： 要更新现有代码以执行此操作，您可以更改 midSortNode() 以传递输出列表并仅添加当前节点...

function midSortNode($node, $sortArr = []){
    if (!empty($node)){
        $sortArr = midSortNode($node['left'], $sortArr);
        $sortArr[] = $node['key'];
        $sortArr = midSortNode($node['right'], $sortArr);
    }
    return $sortArr;
}

如何将二叉树存储为一维数组？

How to store a binary tree as one-dimensional array?

php

binary-tree