這次帶給大家怎樣使用PHP排序二元樹，使用PHP排序二元樹的注意事項有哪些，下面就是實戰案例，一起來看一下。
這裡示範了排序二叉樹節點的插入,中序遍歷,極值的查找和特定值的查找的功能.
基本上沒有提供什麼概念和定義.建議先簡單了解一下本文提供的幾個概念在來看本文.
其實,只是簡單的提供了程式碼,註解也很少,各位辛苦了.
二元樹:在電腦科學中，二元樹是每個節點最多有兩個子樹的樹結構。
排序二元樹: 左孩子節點的值小於父節點的值,右孩子節點的值大於父節點的值.
幾個概念:
根節點
葉子節點
左子樹
右子樹
中序遍歷
前序遍歷
後序遍歷
二元樹查找
中序遍歷:
先遍歷左子樹,在遍歷本節點,在遍歷右節點.遍歷之後的結果就是排序好之後的結果
// created by 曲朋维
// 排序二叉树
// 完成以下任务.
// 1. 将节点插入到对应位置
// 2. 使用中序遍历遍历这个二叉树
// 3. 找到这个二叉树的极值
// 4. 搜索一个特定的值
class Node{
public $key,$left,$right;
public function construct($key)
{
$this->key = $key;
}
}
class BinaryTree{
public $root;
public $sortArr = [];
// 插入节点
public function insertNode($node,$newNode){
if ($node->key < $newNode->key){
// 如果父节点小于子节点,插到右边
if (empty($node->right)){
$node->right = $newNode;
}else{
$this->insertNode($node->right,$newNode);
}
}elseif ($node->key > $newNode->key){
// 如果父节点大于子节点,插到左边
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(){
//不断的找它的左子树,直到这个左子树的节点为叶子节点.
if (!empty($this->root)){
$this->findMinNode($this->root);
}
}
public function findMinNode(Node $node){
if (!empty($node->left)){
$this->findMinNode($node->left);
}else{
echo '这个二叉树的最小值为:'.$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 '这个二叉树的最大值为:'.$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){
// 如果 父节点的值 大于要查找的值,那么查找它的左子树
if (!empty($node->left)){
$this->findNode($node->left,$val);
}else{
echo '没有这个东西!';
}
}else if ($node->key < $val){
if (!empty($node->right)){
$this->findNode($node->right,$val);
}else{
echo '没有这个东西!';
}
}
}
}
$tree = new BinaryTree();
// 节点插入
$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);運行結果：
##我相信看了本文案例你已經掌握了方法，更多精彩請關注php中文網其它相關文章！ 推薦閱讀：找到7了
沒有這個東西!
以上是怎樣使用PHP排序二元樹的詳細內容。更多資訊請關注PHP中文網其他相關文章！
