PHPソートツリー基本機能実装方法例
4231 ワード
この例では、PHPソートツリーの基本機能の実装方法について説明します.皆さんの参考にしてください.具体的には以下の通りです.
ここでは、ソートツリーノードの挿入、中順遍歴、極値の検索、特定の値の検索の機能を示す.
概念や定義はほとんど提供されていません.まず、本文が提供したいくつかの概念を簡単に理解して、本文を見てみることを提案する.
実际には、コードを简単に提供しただけで、コメントも少なく、お疲れ様でした.
ツリー:コンピュータ科学では、ツリーはノードごとに最大2つのサブツリーを持つツリー構造です.
ツリーのソート:左の子ノードの値は親ノードの値より小さく、右の子ノードの値は親ノードの値より大きい.
いくつかの概念:
ルートノードリーフノード左サブツリー右サブツリー中シーケンス前シーケンス後シーケンス二叉木検索
中間パス:
まず左サブツリーを遍歴し、本ノードを遍歴し、右ノードを遍歴する.遍歴した結果がソートされた結果です
実行結果:
7が見つかりました.これはありません.
PHPについてもっと兴味のある読者は、「PHPデータ构造とアルゴリズム教程」、「phpプログラム设计アルゴリズム総括」、「php文字列(string)用法総括」、「PHP配列(Array)操作技巧大全」、「PHP常用遍歴アルゴリズムと技巧総括」、「PHP数学演算技巧総括」
ここで述べたことが皆さんのPHPプログラム設計に役立つことを願っています.
ここでは、ソートツリーノードの挿入、中順遍歴、極値の検索、特定の値の検索の機能を示す.
概念や定義はほとんど提供されていません.まず、本文が提供したいくつかの概念を簡単に理解して、本文を見てみることを提案する.
実际には、コードを简単に提供しただけで、コメントも少なく、お疲れ様でした.
ツリー:コンピュータ科学では、ツリーはノードごとに最大2つのサブツリーを持つツリー構造です.
ツリーのソート:左の子ノードの値は親ノードの値より小さく、右の子ノードの値は親ノードの値より大きい.
いくつかの概念:
ルートノードリーフノード左サブツリー右サブツリー中シーケンス前シーケンス後シーケンス二叉木検索
中間パス:
まず左サブツリーを遍歴し、本ノードを遍歴し、右ノードを遍歴する.遍歴した結果がソートされた結果です
// 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 "
";
$tree->find(11);
実行結果:
7が見つかりました.これはありません.
PHPについてもっと兴味のある読者は、「PHPデータ构造とアルゴリズム教程」、「phpプログラム设计アルゴリズム総括」、「php文字列(string)用法総括」、「PHP配列(Array)操作技巧大全」、「PHP常用遍歴アルゴリズムと技巧総括」、「PHP数学演算技巧総括」
ここで述べたことが皆さんのPHPプログラム設計に役立つことを願っています.