本文實(shí)例講述了PHP排序二叉樹基本功能實(shí)現(xiàn)方法。分享給大家供大家參考，具體如下：
這里演示了排序二叉樹節(jié)點(diǎn)的插入,中序遍歷,極值的查找和特定值的查找的功能.
基本沒有提供什么概念和定義.建議先簡(jiǎn)單了解一下本文提供的幾個(gè)概念在來看本文.
實(shí)際上,只是簡(jiǎn)單的提供了代碼,注釋也很少,各位辛苦了.
二叉樹:在計(jì)算機(jī)科學(xué)中，二叉樹是每個(gè)節(jié)點(diǎn)最多有兩個(gè)子樹的樹結(jié)構(gòu)。
排序二叉樹: 左孩子節(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相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《PHP數(shù)據(jù)結(jié)構(gòu)與算法教程》、《php程序設(shè)計(jì)算法總結(jié)》、《php字符串(string)用法總結(jié)》、《PHP數(shù)組(Array)操作技巧大全》、《PHP常用遍歷算法與技巧總結(jié)》及《PHP數(shù)學(xué)運(yùn)算技巧總結(jié)》
希望本文所述對(duì)大家PHP程序設(shè)計(jì)有所幫助。
您可能感興趣的文章:- PHP實(shí)現(xiàn)二叉樹深度優(yōu)先遍歷(前序、中序、后序)和廣度優(yōu)先遍歷(層次)實(shí)例詳解
- PHP實(shí)現(xiàn)從上往下打印二叉樹的方法
- PHP獲取二叉樹鏡像的方法
- PHP實(shí)現(xiàn)按之字形順序打印二叉樹的方法
- PHP基于非遞歸算法實(shí)現(xiàn)先序、中序及后序遍歷二叉樹操作示例
- PHP實(shí)現(xiàn)判斷二叉樹是否對(duì)稱的方法
- PHP實(shí)現(xiàn)繪制二叉樹圖形顯示功能詳解【包括二叉搜索樹、平衡樹及紅黑樹】
- PHP完全二叉樹定義與實(shí)現(xiàn)方法示例
- php實(shí)現(xiàn)二叉樹中和為某一值的路徑方法
