当前位置:首页 > PHP教程 > php应用 > 列表

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

发布:smiling 来源: PHP粉丝网  添加日期:2021-09-18 14:14:09 浏览: 评论:0 

本文实例讲述了PHP排序二叉树基本功能实现方法,分享给大家供大家参考,具体如下:

这里演示了排序二叉树节点的插入,中序遍历,极值的查找和特定值的查找的功能.

基本没有提供什么概念和定义.建议先简单了解一下本文提供的几个概念在来看本文.

实际上,只是简单的提供了代码,注释也很少,各位辛苦了.

二叉树:在计算机科学中,二叉树是每个节点最多有两个子树的树结构。

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

几个概念:

根节点

叶子节点

左子树

右子树

中序遍历

前序遍历

后序遍历

二叉树查找

中序遍历:

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

  1. // created by 曲朋维 
  2. // 排序二叉树 
  3. // 完成以下任务. 
  4. // 1. 将节点插入到对应位置 
  5. // 2. 使用中序遍历遍历这个二叉树 
  6. // 3. 找到这个二叉树的极值 
  7. // 4. 搜索一个特定的值 
  8. class Node{ 
  9.   public $key,$left,$right
  10.   public function __construct($key
  11.   { 
  12.     $this->key = $key
  13.   } 
  14. class BinaryTree{ 
  15.   public $root
  16.   public $sortArr = []; 
  17.   // 插入节点 
  18.   public function insertNode($node,$newNode){ 
  19.     if ($node->key < $newNode->key){ 
  20.       // 如果父节点小于子节点,插到右边 
  21.       if (emptyempty($node->right)){ 
  22.         $node->right = $newNode
  23.       }else
  24.         $this->insertNode($node->right,$newNode); 
  25.       } 
  26.     }elseif ($node->key > $newNode->key){ 
  27.       // 如果父节点大于子节点,插到左边 
  28.       if (emptyempty($node->left)){ 
  29.         $node->left = $newNode
  30.       }else
  31.         $this->insertNode($node->left,$newNode); 
  32.       } 
  33.     } 
  34.   } 
  35.   public function insert($key){ 
  36.     $newNode = new Node($key); 
  37.     if (emptyempty($this->root)){ 
  38.       $this->root = $newNode
  39.     }else
  40.       $this->insertNode($this->root,$newNode); 
  41.     } 
  42.   } 
  43.   // 中序遍历 
  44.   public function midSort(){ 
  45.     $this->midSortNode($this->root); 
  46.   } 
  47.   public function midSortNode($node){ 
  48.     if (!emptyempty($node)){ 
  49.       $this->midSortNode($node->left); 
  50.       array_push($this->sortArr,$node->key); 
  51.       $this->midSortNode($node->right); 
  52.     } 
  53.   } 
  54.   // 寻找极值 
  55.   public function findMin(){ 
  56.     //不断的找它的左子树,直到这个左子树的节点为叶子节点. 
  57.     if (!emptyempty($this->root)){ 
  58.       $this->findMinNode($this->root); 
  59.     } 
  60.   } 
  61.   public function findMinNode(Node $node){ 
  62.     if (!emptyempty($node->left)){ 
  63.       $this->findMinNode($node->left); 
  64.     }else
  65.       echo '这个二叉树的最小值为:'.$node->key; 
  66.     } 
  67.   } 
  68.   public function findMax(){ 
  69.     if (!emptyempty($this->root)){ 
  70.       $this->findMaxNode($this->root); 
  71.     } 
  72.   } 
  73.   public function findMaxNode(Node $node){ 
  74.     if (!emptyempty($node->right)){ 
  75.       $this->findMaxNode($node->right); 
  76.     }else
  77.       echo '这个二叉树的最大值为:'.$node->key; 
  78.     } 
  79.   } 
  80.   // 查找特定的值 
  81.   public function find($val = ''){ 
  82.     if (!emptyempty($val)){ 
  83.       $this->findNode($this->root,$val); 
  84.     } 
  85.   } 
  86.   public function findNode(Node $node,$val){ 
  87.     if ($node->key == $val){ 
  88.       echo '找到'.$val.'了'
  89.     }else if ($node->key > $val){ 
  90.       // 如果 父节点的值 大于要查找的值,那么查找它的左子树 
  91.       if (!emptyempty($node->left)){ 
  92.         $this->findNode($node->left,$val); 
  93.       }else
  94.         echo '没有这个东西!'
  95.       } 
  96.     }else if ($node->key < $val){ 
  97.       if (!emptyempty($node->right)){ 
  98.         $this->findNode($node->right,$val); 
  99.       }else
  100.         echo '没有这个东西!'
  101.       } 
  102.     } 
  103.   } 
  104. $tree = new BinaryTree(); 
  105. // 节点插入 
  106. $nodes = array(8,3,10,1,6,14,4,7,13); 
  107. foreach ($nodes as $value){ 
  108.   $tree->insert($value); 
  109. // 中序遍历 
  110. //$tree->midSort(); 
  111. //print_r($tree->sortArr); 
  112. // 寻找极值 
  113. //$tree->findMin(); 
  114. //$tree->findMax(); 
  115. // 查找特定的值 
  116. $tree->find(7); 
  117. echo "<br/>"
  118. $tree->find(11); 

运行结果:

找到7了

没有这个东西!

Tags: PHP排序二叉树

分享到: