本文實例講述了PHP排序二叉樹基本功能實現(xiàn)方法。分享給大家供大家參考,具體如下:
這里演示了排序二叉樹節(jié)點的插入,中序遍歷,極值的查找和特定值的查找的功能.
基本沒有提供什么概念和定義.建議先簡單了解一下本文提供的幾個概念在來看本文.
實際上,只是簡單的提供了代碼,注釋也很少,各位辛苦了.
二叉樹:在計算機科學中,二叉樹是每個節(jié)點最多有兩個子樹的樹結構。
排序二叉樹: 左孩子節(jié)點的值小于父節(jié)點的值,右孩子節(jié)點的值大于父節(jié)點的值.
幾個概念:
根節(jié)點
葉子節(jié)點
左子樹
右子樹
中序遍歷
前序遍歷
后序遍歷
二叉樹查找
中序遍歷:
先遍歷左子樹,在遍歷本節(jié)點,在遍歷右節(jié)點.遍歷之后的結果就是排序好之后的結果
// created by 曲朋維
// 排序二叉樹
// 完成以下任務.
// 1. 將節(jié)點插入到對應位置
// 2. 使用中序遍歷遍歷這個二叉樹
// 3. 找到這個二叉樹的極值
// 4. 搜索一個特定的值
class Node{
public $key,$left,$right;
public function __construct($key)
{
$this->key = $key;
}
}
class BinaryTree{
public $root;
public $sortArr = [];
// 插入節(jié)點
public function insertNode($node,$newNode){
if ($node->key $newNode->key){
// 如果父節(jié)點小于子節(jié)點,插到右邊
if (empty($node->right)){
$node->right = $newNode;
}else{
$this->insertNode($node->right,$newNode);
}
}elseif ($node->key > $newNode->key){
// 如果父節(jié)點大于子節(jié)點,插到左邊
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(){
//不斷的找它的左子樹,直到這個左子樹的節(jié)點為葉子節(jié)點.
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){
// 如果 父節(jié)點的值 大于要查找的值,那么查找它的左子樹
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();
// 節(jié)點插入
$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);
運行結果:
找到7了
沒有這個東西!
更多關于PHP相關內(nèi)容感興趣的讀者可查看本站專題:《PHP數(shù)據(jù)結構與算法教程》、《php程序設計算法總結》、《php字符串(string)用法總結》、《PHP數(shù)組(Array)操作技巧大全》、《PHP常用遍歷算法與技巧總結》及《PHP數(shù)學運算技巧總結》
希望本文所述對大家PHP程序設計有所幫助。
您可能感興趣的文章:- PHP實現(xiàn)二叉樹深度優(yōu)先遍歷(前序、中序、后序)和廣度優(yōu)先遍歷(層次)實例詳解
- PHP實現(xiàn)從上往下打印二叉樹的方法
- PHP獲取二叉樹鏡像的方法
- PHP實現(xiàn)按之字形順序打印二叉樹的方法
- PHP基于非遞歸算法實現(xiàn)先序、中序及后序遍歷二叉樹操作示例
- PHP實現(xiàn)判斷二叉樹是否對稱的方法
- PHP實現(xiàn)繪制二叉樹圖形顯示功能詳解【包括二叉搜索樹、平衡樹及紅黑樹】
- PHP完全二叉樹定義與實現(xiàn)方法示例
- php實現(xiàn)二叉樹中和為某一值的路徑方法