本文实例讲述了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了

没有这个东西!