二叉樹遍歷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．後（根）序遍歷得遞歸演算法定義：
若二叉樹非空，則依次執行如下操作：
⑴遍歷左子樹；
⑵遍歷右子樹；
⑶訪問根結點。