Как сохранить двоичное дерево в виде одномерного массива?

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;
}