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

运行结果：

找到7了

没有这个东西!

Tags: PHP排序二叉树

分享到：