PHP排序二叉树基本功能实现方法示例

php  /  管理员 发布于 7年前   173

本文实例讲述了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 "
";$tree->find(11);

运行结果：

找到7了
没有这个东西!

更多关于PHP相关内容感兴趣的读者可查看本站专题：《PHP数据结构与算法教程》、《php程序设计算法总结》、《php字符串(string)用法总结》、《PHP数组(Array)操作技巧大全》、《PHP常用遍历算法与技巧总结》及《PHP数学运算技巧总结》

希望本文所述对大家PHP程序设计有所帮助。

您可能感兴趣的文章:

• PHP实现二叉树深度优先遍历(前序、中序、后序)和广度优先遍历(层次)实例详解
• PHP实现从上往下打印二叉树的方法
• PHP获取二叉树镜像的方法
• PHP实现按之字形顺序打印二叉树的方法
• PHP基于非递归算法实现先序、中序及后序遍历二叉树操作示例
• PHP实现判断二叉树是否对称的方法
• PHP实现绘制二叉树图形显示功能详解【包括二叉搜索树、平衡树及红黑树】
• PHP完全二叉树定义与实现方法示例
• php实现二叉树中和为某一值的路径方法