PHP排序二叉树基本功能实现方法示例
发布:smiling 来源: PHP粉丝网 添加日期:2021-09-18 14:14:09 浏览: 评论:0
本文实例讲述了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 (emptyempty($node->right)){
- $node->right = $newNode;
- }else{
- $this->insertNode($node->right,$newNode);
- }
- }elseif ($node->key > $newNode->key){
- // 如果父节点大于子节点,插到左边
- if (emptyempty($node->left)){
- $node->left = $newNode;
- }else{
- $this->insertNode($node->left,$newNode);
- }
- }
- }
- public function insert($key){
- $newNode = new Node($key);
- if (emptyempty($this->root)){
- $this->root = $newNode;
- }else{
- $this->insertNode($this->root,$newNode);
- }
- }
- // 中序遍历
- public function midSort(){
- $this->midSortNode($this->root);
- }
- public function midSortNode($node){
- if (!emptyempty($node)){
- $this->midSortNode($node->left);
- array_push($this->sortArr,$node->key);
- $this->midSortNode($node->right);
- }
- }
- // 寻找极值
- public function findMin(){
- //不断的找它的左子树,直到这个左子树的节点为叶子节点.
- if (!emptyempty($this->root)){
- $this->findMinNode($this->root);
- }
- }
- public function findMinNode(Node $node){
- if (!emptyempty($node->left)){
- $this->findMinNode($node->left);
- }else{
- echo '这个二叉树的最小值为:'.$node->key;
- }
- }
- public function findMax(){
- if (!emptyempty($this->root)){
- $this->findMaxNode($this->root);
- }
- }
- public function findMaxNode(Node $node){
- if (!emptyempty($node->right)){
- $this->findMaxNode($node->right);
- }else{
- echo '这个二叉树的最大值为:'.$node->key;
- }
- }
- // 查找特定的值
- public function find($val = ''){
- if (!emptyempty($val)){
- $this->findNode($this->root,$val);
- }
- }
- public function findNode(Node $node,$val){
- if ($node->key == $val){
- echo '找到'.$val.'了';
- }else if ($node->key > $val){
- // 如果 父节点的值 大于要查找的值,那么查找它的左子树
- if (!emptyempty($node->left)){
- $this->findNode($node->left,$val);
- }else{
- echo '没有这个东西!';
- }
- }else if ($node->key < $val){
- if (!emptyempty($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 "<br/>";
- $tree->find(11);
运行结果:
找到7了
没有这个东西!
Tags: PHP排序二叉树
推荐文章
热门文章
最新评论文章
- 写给考虑创业的年轻程序员(10)
- PHP新手上路(一)(7)
- 惹恼程序员的十件事(5)
- PHP邮件发送例子,已测试成功(5)
- 致初学者:PHP比ASP优秀的七个理由(4)
- PHP会被淘汰吗?(4)
- PHP新手上路(四)(4)
- 如何去学习PHP?(2)
- 简单入门级php分页代码(2)
- php中邮箱email 电话等格式的验证(2)