遍历二叉树，这个相对比较复杂。
二叉树的便利，主要有两种，一种是广度优先遍历，一种是深度优先遍历。
什么是广度优先遍历？就是根节点进入，水平一行一行的便利。
什么是深度优先遍历呢？就是根节点进入，然后按照一个固定的规律，一直向下走，一个方向的子树遍历之后再遍历另一个方向的子树。
深度优先遍历，主要有三种顺序遍历：先序（先输出根节点），中序（第二个输出根节点），后序（最后输出根节点）。
直接上代码吧。
1 class Node { 2 ????public $data = null; 3 ????public $left = null; 4 ????public $right = null; 5 } 6 ?7 $node1 = new Node(); 8 $node2 = new Node(); 9 $node3 = new Node();10 $node4 = new Node();11 $node5 = new Node();12 $node6 = new Node();13 $node7 = new Node();14 $node8 = new Node();15 $node9 = new Node();16 17 $node1->data = 1;18 $node2->data = 2;19 $node3->data = 3;20 $node4->data = 4;21 $node5->data = 5;22 $node6->data = 6;23 $node7->data = 7;24 $node8->data = 8;25 $node9->data = 9;26 27 $node1->left = $node2;28 $node1->right = $node3;29 $node2->left = $node4;30 $node2->right = $node5;31 $node3->left = $node6;32 $node3->right = $node7;33 $node4->left = $node8;34 $node4->right = $node9;以上代码，简单建立一个二叉树，如下图：
广度优先遍历
1 // 二叉树广度优先遍历 2 function binary_tree1($node) { 3 ????$result = [];//保存结果 4 ????$memc = []; 5 ????array_push($memc, $node);//根节点入队 6 ????while (!empty($memc)) {//持续输出节点，直到队列为空 7 ????????$cnode = array_shift($memc);//最前边的元素出队 8 ????????$result[] = $cnode->data;//记录当前节点的值 9 ????????//左节点先入队，然后右节点入队10 ????????if ($cnode->left != null) 11 ????????????array_push($memc, $cnode->left);12 ????????if ($cnode->right != null) 13 ????????????array_push($memc, $cnode->right);14 ????}15 ????return $result;16 }17 18 print_r(binary_tree2($node1));深度优先遍历（先序）
1 // 二叉树深度优先遍历（先序） 2 function binary_tree2($node) 3 { 4 ????$result = [];//结果数组 5 ????$memc ?= []; 6 ????array_push($memc, $node);//将根节点压栈 7 ????while (!empty($memc)) { 8 ????????$cnode = array_pop($memc);//弹出刚刚压栈的节点 9 ????????$result[] = $cnode->data;10 ????????//因为先进后出原则，想先显示左子树，所以先压入右子树11 ????????if ($cnode->right != null) {12 ????????????array_push($memc, $cnode->right);13 ????????}14 ????????if ($cnode->left != null) {15 ????????????array_push($memc, $cnode->left);16 ????????}17 ????}18 ????return $result;19 }20 21 print_r(binary_tree2($node1));PHP遍历二叉树
原文地址：https://www.cnblogs.com/leafinwind/p/10306553.html