钛节点

数据结构之树的代码实现（二）

发表@2018-09-13 09:15:22

更新@2023-01-21 22:47:40

“窝跟泥杠，憋说似泥，就换是劳资，泥让劳资搞设计画个涂什么的，劳资能给泥搞出带翅膀的宾士！蛋似，劳资就是造不出来！劳资只管画和想，能不能造粗来，那是泥们的似！”

YY和做梦以及指手画脚向来都是轻松easy的，亲自下地干活那是不可能的，这辈子都不可能的，这向来也是这个社会上大部人的常态。放到ARM处理器，也就说传说中的“一核有难，八核围观”：

![](https://ti-node.com/static/upload/6404267478360260608)

所以说，“Talk is cheap，show me your code”。

现在我们首先考虑建立一棵二叉树：

```php
<?php
class Node{
  // 父节点
  private $parent = null;
  // 左子树
  private $left = null;
  // 右子树
  private $right = null;
  // 数据域
  private $data = null;
  public function __construct( $value ){
    $this->data = $value;
  }
  // 添加左子树
  public function setLeft( Node $node ){
	  // 将当前class实例化后的结点作为父结点
	  $node->parent = $this;
  	$this->left = $node;
  	return $node;
  }
  // 添加右子树
  public function setRight( Node $node ){
  	// 将当前class实例化后的结点作为父结点
  	$node->parent = $this;
  	$this->right = $node;
  	return $node;
  }
}
```
我们用这段代码来实现一个“从上至下，从左往后”依次为1 -》2 -》3 -》4 -》5 -》6的二叉树：

![](https://ti-node.com/static/upload/6404338087551303681)

```php
<?php
$tree = new Node( 1 );
$left = $tree->setLeft( new Node( 2 ) );
$right = $tree->setRight( new Node( 3 ) );
$left->setLeft( new Node( 4 ) );
$left->setRight( new Node( 5 ) );
$right->setLeft( new Node( 6 ) );
print_r( $tree );
```

二叉树是已经建立了，紧接着就是如何遍历这颗二叉树了。遍历二叉树是指从根节点出发到按照某种顺序将树中的每一个结点都访问一次且每个结点只被访问一次。

二叉树常用的遍历方式有四种，但是，今天这里只有前三种，第四种放到后面。这前三种分别是：
- 前序遍历
- 中序遍历
- 后序遍历

前序遍历简单说就是先走根节点，然后前序遍历左子树，最后再前序遍历右子树，拿上面代码中构建的那个二叉树为例，遍历顺序就是：1-》2-》4-》5-》3-》6。

中序遍历简单说就是从根节点开始（注意仅仅是开始，但不遍历根节点），先中序遍历左子树，然后遍历根节点，最后中序遍历右子树。拿上述二叉树为例，遍历顺序就是：4-》2-》5-》1-》6-》3。

后续遍历简单说就是先从左子树开始，然后右子树，最后根节点。按照上述二叉树为例，遍历顺序就是：4-》5-》2-》6-》3-》1。

“窝跟泥杠，泥邀是能看明白丧面杠的森么，窝就扶泥！”

![](https://ti-node.com/static/upload/6404534380059951104)

下面依然通过纸笔演练来搞定三种遍历方式，二叉树就采用程序中建立好的那个二叉树：

- 前序遍历：一定记着，前序遍历的顺序是先遍历根节点，然后再前序遍历根节点的右子树，最后再前序遍历根节点的右子树！前序遍历中继续前序遍历！

![](https://ti-node.com/static/upload/6404568204512854016)

- 中序遍历：一定记着，中序遍历是先中序遍历左子树，然后遍历根节点，最后遍历右子树。

![](https://ti-node.com/static/upload/6404568481718599681)

- 后续遍历：我感觉我废话太多，不说了。

![](https://ti-node.com/static/upload/6404568551272742912)

其实，如果泥好好演练一遍以上内容，应该能感受到一股浓重的递归风扑面而来，代码感受一下：

```php
	// 接着在上面的Node类中添加如下方法
	// 前序遍历
	public function preOrder( $tree ){
		if( $tree instanceof Node ){
		  // 先遍历根节点
	  	echo $tree->data.'  ';
	  	// 然后遍历左子树
	  	$this->preOrder( $tree->left );
	  	// 最后遍历右子树
	  	$this->preOrder( $tree->right );
    }
	}
  // 中序遍历
  public function midOrder( $tree ){
		if( $tree instanceof Node ){
	  	// 先遍历左子树
	  	$this->midOrder( $tree->left );
		  // 再遍历根节点
	  	echo $tree->data.'  ';
	  	// 后遍历右子树
	  	$this->midOrder( $tree->right );
    }
  }
  // 后续遍历
  public function sufOrder( $tree ){
		if( $tree instanceof Node ){
	  	// 先遍历左子树
	  	$this->sufOrder( $tree->left );
	  	// 再遍历右子树
	  	$this->sufOrder( $tree->right );
		  // 最后遍历根节点
	  	echo $tree->data.'  ';
    }
  }
  
  // 接着上面的运行代码，运行一下三种排序...
  echo $tree->preOrder( $tree ).PHP_EOL;
  echo $tree->midOrder( $tree ).PHP_EOL;
  echo $tree->sufOrder( $tree ).PHP_EOL;
```

保存代码并运行，如下图：

![](https://ti-node.com/static/upload/6404574548682866688)

二叉树的一些最最基础概念和操作就被我们用PHP用最粗暴的代码和方式实现了，不要骄傲，这才刚刚是个开始！

----