使用PHP怎么对二叉树进行排序

这篇文章给大家介绍使用PHP怎么对二叉树进行排序，内容非常详细，感兴趣的小伙伴们可以参考借鉴，希望对大家能有所帮助。

排序二叉树: 左孩子节点的值小于父节点的值,右孩子节点的值大于父节点的值.

几个概念:

根节点叶子节点左子树右子树中序遍历前序遍历后序遍历二叉树查找

中序遍历:

先遍历左子树,在遍历本节点,在遍历右节点.遍历之后的结果就是排序好之后的结果

//createdby曲朋维
//排序二叉树
//完成以下任务.
//1.将节点插入到对应位置
//2.使用中序遍历遍历这个二叉树
//3.找到这个二叉树的极值
//4.搜索一个特定的值
classNode{
public$key,$left,$right;
publicfunction__construct($key)
{
$this->key=$key;
}
}
classBinaryTree{
public$root;
public$sortArr=[];
//插入节点
publicfunctioninsertNode($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);
}
}
}
publicfunctioninsert($key){
$newNode=newNode($key);
if(empty($this->root)){
$this->root=$newNode;
}else{
$this->insertNode($this->root,$newNode);
}
}
//中序遍历
publicfunctionmidSort(){
$this->midSortNode($this->root);
}
publicfunctionmidSortNode($node){
if(!empty($node)){
$this->midSortNode($node->left);
array_push($this->sortArr,$node->key);
$this->midSortNode($node->right);
}
}
//寻找极值
publicfunctionfindMin(){
//不断的找它的左子树,直到这个左子树的节点为叶子节点.
if(!empty($this->root)){
$this->findMinNode($this->root);
}
}
publicfunctionfindMinNode(Node$node){
if(!empty($node->left)){
$this->findMinNode($node->left);
}else{
echo'这个二叉树的最小值为:'.$node->key;
}
}
publicfunctionfindMax(){
if(!empty($this->root)){
$this->findMaxNode($this->root);
}
}
publicfunctionfindMaxNode(Node$node){
if(!empty($node->right)){
$this->findMaxNode($node->right);
}else{
echo'这个二叉树的最大值为:'.$node->key;
}
}
//查找特定的值
publicfunctionfind($val=''){
if(!empty($val)){
$this->findNode($this->root,$val);
}
}
publicfunctionfindNode(Node$node,$val){
if($node->key==$val){
echo'找到'.$val.'了';
}elseif($node->key>$val){
//如果父节点的值大于要查找的值,那么查找它的左子树
if(!empty($node->left)){
$this->findNode($node->left,$val);
}else{
echo'没有这个东西!';
}
}elseif($node->key<$val){
if(!empty($node->right)){
$this->findNode($node->right,$val);
}else{
echo'没有这个东西!';
}
}
}
}
$tree=newBinaryTree();
//节点插入
$nodes=array(8,3,10,1,6,14,4,7,13);
foreach($nodesas$value){
$tree->insert($value);
}
//中序遍历
//$tree->midSort();
//print_r($tree->sortArr);
//寻找极值
//$tree->findMin();
//$tree->findMax();
//查找特定的值
$tree->find(7);
echo"<br/>";
$tree->find(11);

运行结果：

找到7了没有这个东西!

关于使用PHP怎么对二叉树进行排序就分享到这里了，希望以上内容可以对大家有一定的帮助，可以学到更多知识。如果觉得文章不错，可以把它分享出去让更多的人看到。