如何构建二叉树排序

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;
        //构造二叉树
        $node = insertNode($node,$newNode);
    
    }

    //解二叉树
    $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

已解决该问题，修改解析二叉树部分即可 function midSortNode($node, $sortArr = []){ if (!empty($node)){ $sortArr = midSortNode($node['left'], $sortArr); $sortArr[] = $node['key']; $sortArr = midSortNode($node['right'], $sortArr); } return $sortArr; } 结果展示 Array ( [0] => 1 [1] => 3 [2] => 4 [3] => 6 [4] => 7 [5] => 8 [6] => 10 [7] => 13 [8] => 14 )