如何构建二叉树排序

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
)