二叉树遍历php
‘壹’ php版本二叉树按层 从上到下左到右完全二叉树
<?php
/***二叉树的定义*/
classBinaryTree{
protected$key=NULL;//当前节点的值
protected$left=NULL;//左子树
protected$right=NULL;//右子树
/***以指定的值构造二叉树，并指定左右子树*
*@parammixed$key节点的值.
*@parammixed$left左子树节点.
*@parammixed$right右子树节点.
*/
publicfunction__construct($key=NULL,$left=NULL,$right=NULL){
$this->key=$key;
if($key===NULL){
$this->left=NULL;
$this->right=NULL;
}
elseif($left===NULL){
$this->left=newBinaryTree();
$this->right=newBinaryTree();
}
else{
$this->left=$left;
$this->right=$right;
}
}
/**
*析构方法.
*/
publicfunction__destruct(){
$this->key=NULL;
$this->left=NULL;
$this->right=NULL;
}
/**
*清空二叉树.
**/
publicfunctionpurge(){
$this->key=NULL;
$this->left=NULL;
$this->right=NULL;
}
/**
*测试当前节点是否是叶节点.
*
*@returnboolean如果节点非空并且有两个空的子树时为真，否则为假.
*/
publicfunctionisLeaf(){
return!$this->isEmpty()&&
$this->left->isEmpty()&&
$this->right->isEmpty();
}
/**
*测试节点是否为空
*
*@returnboolean如果节点为空返回真，否则为假.
*/
publicfunctionisEmpty(){
return$this->key===NULL;
}
/**
*Keygetter.
*
*@returnmixed节点的值.
*/
publicfunctiongetKey(){
if($this->isEmpty()){
returnfalse;
}
return$this->key;
}
/**
*给节点指定Key值,节点必须为空
*
*@parammixed$object添加的Key值.
*/
publicfunctionattachKey($obj){
if(!$this->isEmpty())
returnfalse;
$this->key=$obj;
$this->left=newBinaryTree();
$this->right=newBinaryTree();
}
/**
*删除key值，使得节点为空.
*/
publicfunctiondetachKey(){
if(!$this->isLeaf())
returnfalse;
$result=$this->key;
$this->key=NULL;
$this->left=NULL;
$this->right=NULL;
return$result;
}
/**
*返回左子树
*
*@returnobjectBinaryTree当前节点的左子树.
*/
publicfunctiongetLeft(){
if($this->isEmpty())
returnfalse;
return$this->left;
}
/**
*给当前结点添加左子树
*
*@paramobjectBinaryTree$t给当前节点添加的子树.
*/
publicfunctionattachLeft(BinaryTree$t){
if($this->isEmpty()||!$this->left->isEmpty())
returnfalse;
$this->left=$t;
}
/**
*删除左子树
*
*@returnobjectBinaryTree返回删除的左子树.
*/
publicfunctiondetachLeft(){
if($this->isEmpty())
returnfalse;
$result=$this->left;
$this->left=newBinaryTree();
return$result;
}
/**
*返回当前节点的右子树
*
*@returnobjectBinaryTree当前节点的右子树.
*/
publicfunctiongetRight(){
if($this->isEmpty())
returnfalse;
return$this->right;
}
/**
*给当前节点添加右子树
*
*@paramobjectBinaryTree$t需要添加的右子树.
*/
publicfunctionattachRight(BinaryTree$t){
if($this->isEmpty()||!$this->right->isEmpty())
returnfalse;
$this->right=$t;
}
/**
*删除右子树，并返回此右子树
*@returnobjectBinaryTree删除的右子树.
*/
publicfunctiondetachRight(){
if($this->isEmpty())
returnfalse;
$result=$this->right;
$this->right=newBinaryTree();
return$result;
}
/**
*先序遍历
*/
(){
if($this->isEmpty()){
return;
}
echo'',$this->getKey();
$this->getLeft()->preorderTraversal();
$this->getRight()->preorderTraversal();
}
/**
*中序遍历
*/
(){
if($this->isEmpty()){
return;
}
$this->getLeft()->preorderTraversal();
echo'',$this->getKey();
$this->getRight()->preorderTraversal();
}
/**
*后序遍历
*/
(){
if($this->isEmpty()){
return;
}
$this->getLeft()->preorderTraversal();
$this->getRight()->preorderTraversal();
echo'',$this->getKey();
}
}
/**
*二叉排序树的PHP实现
*/
classBSTextendsBinaryTree{
/**
*构造空的二叉排序树
*/
publicfunction__construct(){
parent::__construct(NULL,NULL,NULL);
}
/**
*析构
*/
publicfunction__destruct(){
parent::__destruct();
}
/**
*测试二叉排序树中是否包含参数所指定的值
*
*@parammixed$obj查找的值.
*@returnbooleanTrue如果存在于二叉排序树中则返回真，否则为假期
*/
publicfunctioncontains($obj){
if($this->isEmpty())
returnfalse;
$diff=$this->compare($obj);
if($diff==0){
returntrue;
}elseif($diff<0)return$this->getLeft()->contains($obj);
else
return$this->getRight()->contains($obj);
}
/**
*查找二叉排序树中参数所指定的值的位置
*
*@parammixed$obj查找的值.
*@returnbooleanTrue如果存在则返回包含此值的对象，否则为NULL
*/
publicfunctionfind($obj){
if($this->isEmpty())
returnNULL;
$diff=$this->compare($obj);
if($diff==0)
return$this->getKey();
elseif($diff<0)return$this->getLeft()->find($obj);
else
return$this->getRight()->find($obj);
}
/**
*返回二叉排序树中的最小值
*@returnmixed如果存在则返回最小值，否则返回NULL
*/
publicfunctionfindMin(){
if($this->isEmpty())
returnNULL;
elseif($this->getLeft()->isEmpty())
return$this->getKey();
else
return$this->getLeft()->findMin();
}
/**
*返回二叉排序树中的最大值
*@returnmixed如果存在则返回最大值，否则返回NULL
*/
publicfunctionfindMax(){
if($this->isEmpty())
returnNULL;
elseif($this->getRight()->isEmpty())
return$this->getKey();
else
return$this->getRight()->findMax();
}
/**
*给二叉排序树插入指定值
*
*@parammixed$obj需要插入的值.
*如果指定的值在树中存在，则返回错误
*/
publicfunctioninsert($obj){
if($this->isEmpty()){
$this->attachKey($obj);
}else{
$diff=$this->compare($obj);
if($diff==0)
die('arguerror');
if($diff<0)$this->getLeft()->insert($obj);
else
$this->getRight()->insert($obj);
}
$this->balance();
}
/**
*从二叉排序树中删除指定的值
*
*@parammixed$obj需要删除的值.
*/
publicfunctiondelete($obj){
if($this->isEmpty())
die();
$diff=$this->compare($obj);
if($diff==0){
if(!$this->getLeft()->isEmpty()){
$max=$this->getLeft()->findMax();
$this->key=$max;
$this->getLeft()->delete($max);
}
elseif(!$this->getRight()->isEmpty()){
$min=$this->getRight()->findMin();
$this->key=$min;
$this->getRight()->delete($min);
}else
$this->detachKey();
}elseif($diff<0)$this->getLeft()->delete($obj);
else
$this->getRight()->delete($obj);
$this->balance();
}
publicfunctioncompare($obj){
return$obj-$this->getKey();
}
/**
*.
*Thenodemustbeinitiallyempty.
*
*@paramobjectIObject$objThekeytoattach.
*@.
*/
publicfunctionattachKey($obj){
if(!$this->isEmpty())
returnfalse;
$this->key=$obj;
$this->left=newBST();
$this->right=newBST();
}
/**
*Balancesthisnode.
*Doesnothinginthisclass.
*/
protectedfunctionbalance(){}
/**
*Mainprogram.
*
*@paramarray$argsCommand-linearguments.
*@returnintegerZeroonsuccess;non-zeroonfailure.
*/
publicstaticfunctionmain($args){
printf("BinarySearchTreemainprogram. ");
$root=newBST();
foreach($argsas$row){
$root->insert($row);
}
return$root;
}
}
$root=BST::main(array(50,3,10,5,100,56,78));
echo$root->findMax();
$root->delete(100);
echo$root->findMax();
‘贰’ 二叉树的遍历到底是怎么回事
遍历概念 所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础。 遍历方案 1．遍历方案 从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作： （1）访问结点本身(N)，（2）遍历该结点的左子树(L)，（3）遍历该结点的右子树(R)。 以上三种操作有六种执行次序： NLR、LNR、LRN、NRL、RNL、RLN。 注意： 前三种次序与后三种次序对称，故只讨论先左后右的前三种次序。 2．三种遍历的命名 根据访问结点操作发生位置命名： ① NLR：前序遍历(PreorderTraversal亦称(先序遍历)) ——访问结点的操作发生在遍历其左右子树之前。 ② LNR：中序遍历(InorderTraversal) ——访问结点的操作发生在遍历其左右子树之中(间)。③ LRN：后序遍历(PostorderTraversal) ——访问结点的操作发生在遍历其左右子树之后。 注意： 由于被访问的结点必是某子树的根，所以N(Node)、L(Left subtlee)和R(Right subtree)又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。 遍历算法 1．中序遍历的递归算法定义： 若二叉树非空，则依次执行如下操作： (1)遍历左子树； (2)访问根结点； (3)遍历右子树。 2．先序遍历的递归算法定义： 若二叉树非空，则依次执行如下操作： (1) 访问根结点； (2) 遍历左子树； (3) 遍历右子树。 3．后序遍历得递归算法定义： 若二叉树非空，则依次执行如下操作： (1)遍历左子树； (2)遍历右子树； (3)访问根结点。 4．中序遍历的算法实现 用二叉链表做为存储结构，中序遍历算法可描述为： void InOrder(BinTree T) { //算法里①~⑥是为了说明执行过程加入的标号 ① if(T) { // 如果二叉树非空 ② InOrder(T->lchild)；③ printf("％c"，T->data)； // 访问结点 ④ InOrder(T->rchild); ⑤ } ⑥ } // InOrder 遍历序列 1．遍历二叉树的执行踪迹 三种递归遍历算法的搜索路线相同（如下图虚线所示）。 具体线路为： 从根结点出发，逆时针沿着二叉树外缘移动，对每个结点均途径三次，最后回到根结点。 2．遍历序列 （1） 中序序列 中序遍历二叉树时，对结点的访问次序为中序序列 【例】中序遍历上图所示的二叉树时，得到的中序序列为： D B A E C F （2） 先序序列 先序遍历二叉树时，对结点的访问次序为先序序列 【例】先序遍历上图所示的二叉树时，得到的先序序列为： A B D C E F （3） 后序序列 后序遍历二叉树时，对结点的访问次序为后序序列 【例】后序遍历上图所示的二叉树时，得到的后序序列为： D B E F C A 注意： （1） 在搜索路线中，若访问结点均是第一次经过结点时进行的，则是前序遍历；若访问结点均是在第二次(或第三次)经过结点时进行的，则是中序遍历(或后序遍历)。只要将搜索路线上所有在第一次、第二次和第三次经过的结点分别列表，即可分别得到该二叉树的前序序列、中序序列和后序序列。 （2） 上述三种序列都是线性序列，有且仅有一个开始结点和一个终端结点，其余结点都有且仅有一个前趋结点和一个后继结点。为了区别于树形结构中前趋(即双亲)结点和后继(即孩子)结点的概念，对上述三种线性序列，要在某结点的前趋和后继之前冠以其遍历次序名称。 【例】上图所示的二叉树中结点C，其前序前趋结点是D，前序后继结点是E；中序前趋结点是E，中序后继结点是F；后序前趋结点是F，后序后继结点是A。但是就该树的逻辑结构而言，C的前趋结点是A，后继结点是E和F。 二叉链表的构造 1． 基本思想 基于先序遍历的构造，即以二叉树的先序序列为输入构造。 注意： 先序序列中必须加入虚结点以示空指针的位置。 【例】 建立上图所示二叉树，其输入的先序序列是：ABD∮∮CE∮∮F∮∮。 2． 构造算法 假设虚结点输入时以空格字符表示，相应的构造算法为： void CreateBinTree (BinTree *T) { //构造二叉链表。T是指向根指针的指针，故修改*T就修改了实参(根指针)本身 char ch； if((ch=getchar())=='') *T=NULL； //读人空格，将相应指针置空 else{ //读人非空格 *T=(BinTNode *)malloc(sizeof(BinTNode))； //生成结点 (*T)->data=ch； CreateBinTree(&(*T)->lchild)； //构造左子树 CreateBinTree(&(*T)->rchild)； //构造右子树 } } 注意： 调用该算法时，应将待建立的二叉链表的根指针的地址作为实参。 【例】设root是一根指针(即它的类型是BinTree)，则调用CreateBinTree(&root)后root就指向了已构造好的二叉链表的根结点。 C例子： template<class elemtype>//二叉树结点 struct nodetype { elemtype info;//结点信息 nodetype<elemtype> *llink;//左子树 nodetype<elemtype> *rlink;//右子树 }; template<class elemtype> void inorder(nodetype<elemtype> *p)//中序遍历 { if(NULL!=p) {inorder(p->llink);//使用递归算法先遍历左子树 cout<<p->info<<" ";//访问结点 inorder(p->rlink);//遍历右子树 } }
‘叁’ 二叉树的遍历算法
void
preorder(BiTree
root)
/*先序遍历输出二叉树结点，root为指向二叉树根节点的指针*/
{
if（root!=NULL）
{
printf(root->data);
preorder(root->Lchild);
preorder(root->Rchild);
}
}
你看好这个程序,你首先定义了一个preorder函数,然后在函数体中又调用了本函数,这是函数的自调用.执行printf(root->data);语句的时候输出当前遍历的数据,preorder(root->Lchild);在执行到4的时候,root->Lchild=NULL,但是执行preorder(root->Rchild);语句,由此转向下一个结点,即5
‘肆’ 生成并遍历二叉树
C++代码如下：
#include<iostream>
#include<string>
using namespace std;
struct TreeNode { // 二叉树结构
char val;
TreeNode *left, *right;
TreeNode(char ch) : val(ch), left(nullptr), right(nullptr) {}
};
// 由扩展前序序列生成二叉树
TreeNode* construct(string& s, int& i) { // 注意传入的i为引用
if (i == s.length())
return nullptr;
TreeNode *root = nullptr;
if (s[i] != '*') {
root = new TreeNode(s[i]);
++i;
root->left = construct(s, i);
++i;
root->right = construct(s, i);
}
return root;
}
void preOrder(TreeNode* root) { // 前序遍历
if (root) {
cout << root->val;
preOrder(root->left);
preOrder(root->right);
}
}
void inOrder(TreeNode* root) { // 中序遍历
if (root) {
inOrder(root->left);
cout << root->val;
inOrder(root->right);
}
}
void postOrder(TreeNode* root) { // 后序遍历
if (root) {
postOrder(root->left);
postOrder(root->right);
cout << root->val;
}
}
int main() {
string s = "ABC**DE*G**F***";
cout << "扩展前序序列为：" << s << endl;
int i = 0;
TreeNode* root = construct(s, i); // 生成该二叉树
cout << "其前序遍历序列为：";
preOrder(root);
cout << endl;
cout << "其中序遍历序列为：";
inOrder(root);
cout << endl;
cout << "其后序遍历序列为：";
postOrder(root);
cout << endl;
return 0;
}
编译通过，输出如下：
符合示例结果，望采纳~
‘伍’ 二叉树如何遍历
二叉树的遍历，通常用递归的方法来描述。
先根遍历或者先序遍历：首先访问根结点，然后访问左子树，最后访问右子树。
中根便利或者中序遍历：先访问左子树，然后访问根节点，最后访问右子树。
后根遍历或者先后序遍历：首先访问左子树，然后访问根节点，最后访问右子树。
按层次遍历：从最上面一层，也就是根节点所在的一层开始，从上往下从左到右，访问二叉树中的每一个节点。
‘陆’ 请高手发一下PHP版本二叉树按层遍历
#二叉树的非递归遍历
3 class Node {
4 public $data;
5 public $left;
6 public $right;
7 }
8
9 #前序遍历，和深度遍历一样
10 function preorder($root) {
11 $stack = array();
12 array_push($stack, $root);
13 while (!empty($stack)) {
14 $cnode = array_pop($stack);
15 echo $cnode->data . " ";
16 if ($cnode->right != null) array_push($stack, $cnode->right);
17 if ($cnode->left != null) array_push($stack, $cnode->left);
18 }
19 }
‘柒’ 二叉树的遍历算法
这里有二叉树先序、中序、后序三种遍历的非递归算法，此三个算法可视为标准算法。
1.先序遍历非递归算法
#define
maxsize
100
typedef
struct
{
Bitree
Elem[maxsize];
int
top;
}SqStack;
void
PreOrderUnrec(Bitree
t)
{
SqStack
s;
StackInit(s);
p=t;
while
(p!=null
||
!StackEmpty(s))
{
while
(p!=null)
//遍历左子树
{
visite(p->data);
push(s,p);
p=p->lchild;
}//endwhile
if
(!StackEmpty(s))
//通过下一次循环中的内嵌while实现右子树遍历
{
p=pop(s);
p=p->rchild;
}//endif
}//endwhile
}//PreOrderUnrec
2.中序遍历非递归算法
#define
maxsize
100
typedef
struct
{
Bitree
Elem[maxsize];
int
top;
}SqStack;
void
InOrderUnrec(Bitree
t)
{
SqStack
s;
StackInit(s);
p=t;
while
(p!=null
||
!StackEmpty(s))
{
while
(p!=null)
//遍历左子树
{
push(s,p);
p=p->lchild;
}//endwhile
if
(!StackEmpty(s))
{
p=pop(s);
visite(p->data);
//访问根结点
p=p->rchild;
//通过下一次循环实现右子树遍历
}//endif
}//endwhile
}//InOrderUnrec
3.后序遍历非递归算法
#define
maxsize
100
typedef
enum{L,R}
tagtype;
typedef
struct
{
Bitree
ptr;
tagtype
tag;
}stacknode;
typedef
struct
{
stacknode
Elem[maxsize];
int
top;
}SqStack;
void
PostOrderUnrec(Bitree
t)
{
SqStack
s;
stacknode
x;
StackInit(s);
p=t;
do
{
while
(p!=null)
//遍历左子树
{
x.ptr
=
p;
x.tag
=
L;
//标记为左子树
push(s,x);
p=p->lchild;
}
while
(!StackEmpty(s)
&&
s.Elem[s.top].tag==R)
{
x
=
pop(s);
p
=
x.ptr;
visite(p->data);
//tag为R，表示右子树访问完毕，故访问根结点
}
if
(!StackEmpty(s))
{
s.Elem[s.top].tag
=R;
//遍历右子树
p=s.Elem[s.top].ptr->rchild;
}
}while
(!StackEmpty(s));
}//PostOrderUnrec
‘捌’ 二叉树的遍历方法通常有
二叉树的遍历方法通常有：
先根遍历或先序遍历：首先访问根节点，接着遍历左子树，最后遍历右子树。
中根遍历或中序遍历：首先遍历左子树，然后访问根节点，最后遍历右子树。
后根遍历或后序遍历：首先遍历左子树，然后遍历右子树，最后访问根结点。
按层次遍历或宽度优先遍历，从根节点开始访问，从上往下访问每一层节点，在同一层节点中，从左到右访问每一个节点。
‘玖’ 什么是二叉树数的遍历
二叉树遍历（Traversal）是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础。
遍历方案
从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作：访问结点本身（N），遍历该结点的左子树（L），遍历该结点的右子树（R）。
以上三种操作有六种执行次序：NLR、LNR、LRN、NRL、RNL、RLN。
注意：前三种次序与后三种次序对称
遍历命名
根据访问结点操作发生位置命名：
①NLR：前序遍历(PreorderTraversal亦称（先序遍历））
——访问根结点的操作发生在遍历其左右子树之前。
②LNR：中序遍历(InorderTraversal)——访问根结点的操作发生在遍历其左右子树之中（间）。
③LRN：后序遍历(PostorderTraversal)——访问根结点的操作发生在遍历其左右子树之后。注意：由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。
遍历算法
1．先（根）序遍历的递归算法定义：
若二叉树非空，则依次执行如下操作：
⑴ 访问根结点；
⑵ 遍历左子树；
⑶ 遍历右子树。
2．中（根）序遍历的递归算法定义：
若二叉树非空，则依次执行如下操作：
⑴遍历左子树；
⑵访问根结点；
⑶遍历右子树。
3．后（根）序遍历得递归算法定义：
若二叉树非空，则依次执行如下操作：
⑴遍历左子树；
⑵遍历右子树；
⑶访问根结点。