使用PHP怎么對(duì)二叉樹進(jìn)行排序

這篇文章給大家介紹使用PHP怎么對(duì)二叉樹進(jìn)行排序，內(nèi)容非常詳細(xì)，感興趣的小伙伴們可以參考借鑒，希望對(duì)大家能有所幫助。

排序二叉樹: 左孩子節(jié)點(diǎn)的值小于父節(jié)點(diǎn)的值,右孩子節(jié)點(diǎn)的值大于父節(jié)點(diǎn)的值.

幾個(gè)概念:

根節(jié)點(diǎn)
葉子節(jié)點(diǎn)
左子樹
右子樹
中序遍歷
前序遍歷
后序遍歷
二叉樹查找

中序遍歷:

先遍歷左子樹,在遍歷本節(jié)點(diǎn),在遍歷右節(jié)點(diǎn).遍歷之后的結(jié)果就是排序好之后的結(jié)果

// created by 曲朋維
// 排序二叉樹
// 完成以下任務(wù).
// 1. 將節(jié)點(diǎn)插入到對(duì)應(yīng)位置
// 2. 使用中序遍歷遍歷這個(gè)二叉樹
// 3. 找到這個(gè)二叉樹的極值
// 4. 搜索一個(gè)特定的值
class Node{
  public $key,$left,$right;
  public function __construct($key)
  {
    $this->key = $key;
  }
}
class BinaryTree{
  public $root;
  public $sortArr = [];
  // 插入節(jié)點(diǎn)
  public function insertNode($node,$newNode){
    if ($node->key < $newNode->key){
      // 如果父節(jié)點(diǎn)小于子節(jié)點(diǎn),插到右邊
      if (empty($node->right)){
        $node->right = $newNode;
      }else{
        $this->insertNode($node->right,$newNode);
      }
    }elseif ($node->key > $newNode->key){
      // 如果父節(jié)點(diǎn)大于子節(jié)點(diǎn),插到左邊
      if (empty($node->left)){
        $node->left = $newNode;
      }else{
        $this->insertNode($node->left,$newNode);
      }
    }
  }
  public function insert($key){
    $newNode = new Node($key);
    if (empty($this->root)){
      $this->root = $newNode;
    }else{
      $this->insertNode($this->root,$newNode);
    }
  }
  // 中序遍歷
  public function midSort(){
    $this->midSortNode($this->root);
  }
  public function midSortNode($node){
    if (!empty($node)){
      $this->midSortNode($node->left);
      array_push($this->sortArr,$node->key);
      $this->midSortNode($node->right);
    }
  }
  // 尋找極值
  public function findMin(){
    //不斷的找它的左子樹,直到這個(gè)左子樹的節(jié)點(diǎn)為葉子節(jié)點(diǎn).
    if (!empty($this->root)){
      $this->findMinNode($this->root);
    }
  }
  public function findMinNode(Node $node){
    if (!empty($node->left)){
      $this->findMinNode($node->left);
    }else{
      echo '這個(gè)二叉樹的最小值為:'.$node->key;
    }
  }
  public function findMax(){
    if (!empty($this->root)){
      $this->findMaxNode($this->root);
    }
  }
  public function findMaxNode(Node $node){
    if (!empty($node->right)){
      $this->findMaxNode($node->right);
    }else{
      echo '這個(gè)二叉樹的最大值為:'.$node->key;
    }
  }
  // 查找特定的值
  public function find($val = ''){
    if (!empty($val)){
      $this->findNode($this->root,$val);
    }
  }
  public function findNode(Node $node,$val){
    if ($node->key == $val){
      echo '找到'.$val.'了';
    }else if ($node->key > $val){
      // 如果 父節(jié)點(diǎn)的值 大于要查找的值,那么查找它的左子樹
      if (!empty($node->left)){
        $this->findNode($node->left,$val);
      }else{
        echo '沒有這個(gè)東西!';
      }
    }else if ($node->key < $val){
      if (!empty($node->right)){
        $this->findNode($node->right,$val);
      }else{
        echo '沒有這個(gè)東西!';
      }
    }
  }
}
$tree = new BinaryTree();
// 節(jié)點(diǎn)插入
$nodes = array(8,3,10,1,6,14,4,7,13);
foreach ($nodes as $value){
  $tree->insert($value);
}
// 中序遍歷
//$tree->midSort();
//print_r($tree->sortArr);
// 尋找極值
//$tree->findMin();
//$tree->findMax();
// 查找特定的值
$tree->find(7);
echo "<br/>";
$tree->find(11);

運(yùn)行結(jié)果：

找到7了
沒有這個(gè)東西!

關(guān)于使用PHP怎么對(duì)二叉樹進(jìn)行排序就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，可以學(xué)到更多知識(shí)。如果覺得文章不錯(cuò)，可以把它分享出去讓更多的人看到。