本文目錄一覽：
請高手發一下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.構造二叉樹給定一棵二叉樹，要對它進行操作必須先把它存儲到計算機中，二叉樹的存儲可以採用順序存儲結構，也可以採用鏈式存儲結構，鏈式存儲結構有二叉鏈表和三叉鏈表等。在這裡主要討論二叉鏈表存儲結構。
（1）以先序遞歸遍歷思想建立二叉樹。
①建立二叉樹的根結點；②先序建立二叉樹的左子樹；③先序建立二叉樹的右子樹。
（2）構造二叉樹的操作算法。
輸入一個二叉樹的先序序列，構造這棵二叉樹。為了保證唯一地構造出所希望的二叉樹，在鍵入這棵樹的先序序列時，需要在所有空二叉樹的位置上填補一個特殊的字符，比如#。在算法中，需要對每個輸入的字符進行判斷，如果對應的字符是#，則在相應的位置上構造一棵空二叉樹；否則，創建一個新結點。整個算法結構以先序遍歷遞歸算法為基礎，二叉樹中結點之間的指針連接是通過指針參數在遞歸調用返回時完成的。
二叉樹的基本操作
// 創建二叉樹,請輸入節點的總數量: 7
// 請連續輸入7個節點的數據: 4 2 6 1 3 5 7
// 前序遍歷序列: 4 2 1 3 6 5 7
// 中序遍歷序列: 1 2 3 4 5 6 7
// 後序遍歷序列: 1 3 2 5 7 6 4
// 二叉樹的節點一共有7個,度為1的節點有0個,度為2的節點有3個,
// 葉子節點有4個,數據值的最大值是7,最小值是1
//
// 對應的二叉樹:
//
// 4
// / \
// 2 6
// / \ / \
// 1 3 5 7
#include “stdio.h”
#include “stdlib.h”
struct Tree
{
int data;
struct Tree *left;
struct Tree *right;
};
typedef struct Tree TreeNode;
typedef TreeNode *Bitree;
typedef struct stack_node //棧的結構體
{
Bitree bt;
struct stack_node *next;
} stack_list, *stack_link;
Bitree insertNode(Bitree root,int data) //插入結點
{
Bitree newnode;
Bitree current;
Bitree back;
newnode=(Bitree)malloc(sizeof(TreeNode));
if(newnode==NULL)
{
printf(“\n動態分配內存出錯.\n”);
exit(1);
}
newnode-data=data;
newnode-left=NULL;
newnode-right=NULL;
if(root==NULL)
{
return newnode;
}
else
{
current=root;
while(current!=NULL)
{
back=current;
if(current-data data)
current=current-left;
else
current=current-right;
}
if(back-data data)
back-left=newnode;
else
back-right=newnode;
}
return root;
}
Bitree createTree() //創建二叉樹(非遞歸)
{
Bitree root=NULL;
int len;
int data;
int i;
printf(“創建二叉樹,請輸入節點的總數量: “);
scanf(“%d”,len);
printf(“請連續輸入%d個節點的數據: “,len);
for(i=0;ilen;i++)
{
scanf(“%d”,data);
root=insertNode(root,data);
}
return root;
}
void preOrder(Bitree ptr) //先序遍歷(遞歸法)
{
if(ptr!=NULL)
{
printf(“%d “,ptr-data);
preOrder(ptr-left);
preOrder(ptr-right);
}
}
void inOrder(Bitree ptr) //中序遍歷(遞歸法)
{
if(ptr!=NULL)
{
inOrder(ptr-left);
printf(“%d “,ptr-data);
inOrder(ptr-right);
}
}
void postOrder(Bitree ptr) //後序遍歷(遞歸法)
{
if(ptr!=NULL)
{
postOrder(ptr-left);
postOrder(ptr-right);
printf(“%d “,ptr-data);
}
}
//檢查[棧]是否是空
int isEmpty(stack_link stack)
{
if(stack == NULL)
{
return 1;
}
else
{
return 0;
}
}
//入棧
stack_link push(stack_link stack,Bitree bt)
{
stack_link new_node;
new_node=(stack_link)malloc(sizeof(stack_list));
if(!new_node)
{
return NULL;
}
new_node-bt=bt;
new_node-next=stack;
stack=new_node;
return stack;
}
//出棧
stack_link pop(stack_link stack,Bitree *bt)
{
stack_link top;
if(isEmpty(stack))
{
*bt = NULL;
return NULL;
}
top=stack;
*bt=top-bt;
stack=top-next;
free(top);
return stack;
}
//統計節點(非遞歸)
void reportByStack(Bitree bt,int *pTotal,int *pCount0,int *pCount1,
int *pCount2,int *pMaxValue,int *pMinValue)
{
Bitree p=NULL;
stack_link oneStack=NULL;
int total=0;
int count0=0,count1=0,count2=0;
int maxValue=0,minValue=0;
if(bt == NULL)
{
return;
}
p=bt; //當前二叉樹的節點
minValue=p-data;
maxValue=minValue;
while(p != NULL)
{
if(minValue p-data)
{
minValue = p-data;
}
if(maxValue p-data)
{
maxValue = p-data;
}
total++; //total=count0+count1+count2
if(p-right == NULL p-left == NULL) //葉子
{
count0++;
}
else if(p-right != NULL p-left != NULL) //度2
{
count2++;
}
else //度1
{
count1++;
}
if(p-right != NULL) //如果有右子樹,馬上入棧
{
oneStack=push(oneStack,p-right);
}
if(p-left != NULL) //如果有左子樹,設為當前節點
{
p=p-left;
}
else
{
oneStack=pop(oneStack,p);
if(p == NULL)
{
break;
}
}
}
*pTotal=total;
*pCount0=count0;
*pCount1=count1;
*pCount2=count2;
*pMaxValue=maxValue;
*pMinValue=minValue;
}
int main()
{
Bitree root=NULL;
int total=0;
int count0=0,count1=0,count2=0;
int maxValue=0,minValue=0;
root=createTree(); //創建二叉樹
printf(“\n前序遍歷序列: “);
preOrder(root);
printf(“\n中序遍歷序列: “);
inOrder(root);
printf(“\n後序遍歷序列: “);
postOrder(root);
//統計節點(非遞歸)
reportByStack(root,total,count0,count1,count2,maxValue,minValue);
printf(“\n二叉樹的節點一共有%d個,度為1的節點有%d個,度為2的節點有%d個,\n”,
total,count1,count2);
printf(“葉子節點有%d個,數據值的最大值是%d,最小值是%d”,
count0,maxValue,minValue);
printf(“\n”);
return 0;
}
如何根據制定的數據使用PHP生成一個二叉樹
假如你所說的二叉樹是指這種的話
那麼你的數據結構一定要滿足一個條件，則每一條數據必須記錄好父級的標識
?php
$data = array(
array(
‘id’ = 1,
‘pid’ = 0,
‘name’ = “”新建腦圖,
),
array(
‘id’ = 2,
‘pid’ = 1,
‘name’ = “分支主題”,
),
array(
‘id’ = 3,
‘pid’ = 1,
‘name’ = “分支主題”,
),
);
?
上述二位數組中的 id為2，3的子數組的父級（pid）id均是1，則他們的父級就是id為1的數組
?php
foreach($data as $key=$value){
if( $value[‘pid’] == ‘0’){
$parent[] = $value;
unset($data[$key]);
}
}
foreach($parent as $key=$value){
foreach($data as $k=$v){
if( $v[‘pid’] == $value[‘id’] ){
$parent[$key][‘_child’][] = $v;
unset($data[$k]);
}
}
}
?
通過以上循環過後，對應二叉樹關係的數組就可以做出來了
當然上述代碼只能進行到二級二叉樹，如果想做出無限級二叉樹的數組，則必須使用到遞歸函數了
PS：上述代碼是網頁裏手打的，沒經過測試，但思路肯定是沒問題的哈
PHP版本二叉樹按層 從上到下左到右完全二叉樹
?php
/** * 二叉樹的定義 */
class BinaryTree {
protected $key = NULL; // 當前節點的值
protected $left = NULL; // 左子樹
protected $right = NULL; // 右子樹
/** * 以指定的值構造二叉樹，並指定左右子樹 *
* @param mixed $key 節點的值.
* @param mixed $left 左子樹節點.
* @param mixed $right 右子樹節點.
*/
public function __construct( $key = NULL, $left = NULL, $right = NULL) {
$this-key = $key;
if ($key === NULL) {
$this-left = NULL;
$this-right = NULL;
}
elseif ($left === NULL) {
$this-left = new BinaryTree();
$this-right = new BinaryTree();
}
else {
$this-left = $left;
$this-right = $right;
}
}
/**
* 析構方法.
*/
public function __destruct() {
$this-key = NULL;
$this-left = NULL;
$this-right = NULL;
}
/**
* 清空二叉樹.
**/
public function purge () {
$this-key = NULL;
$this-left = NULL;
$this-right = NULL;
}
/**
* 測試當前節點是否是葉節點.
*
* @return boolean 如果節點非空並且有兩個空的子樹時為真，否則為假.
*/
public function isLeaf() {
return !$this-isEmpty()
$this-left-isEmpty()
$this-right-isEmpty();
}
/**
* 測試節點是否為空
*
* @return boolean 如果節點為空返回真，否則為假.
*/
public function isEmpty() {
return $this-key === NULL;
}
/**
* Key getter.
*
* @return mixed 節點的值.
*/
public function getKey() {
if ($this-isEmpty()) {
return false;
}
return $this-key;
}
/**
* 給節點指定Key值,節點必須為空
*
* @param mixed $object 添加的Key值.
*/
public function attachKey($obj) {
if (!$this-isEmpty())
return false;
$this-key = $obj;
$this-left = new BinaryTree();
$this-right = new BinaryTree();
}
/**
* 刪除key值，使得節點為空.
*/
public function detachKey() {
if (!$this-isLeaf())
return false;
$result = $this-key;
$this-key = NULL;
$this-left = NULL;
$this-right = NULL;
return $result;
}
/**
* 返回左子樹
*
* @return object BinaryTree 當前節點的左子樹.
*/
public function getLeft() {
if ($this-isEmpty())
return false;
return $this-left;
}
/**
* 給當前結點添加左子樹
*
* @param object BinaryTree $t 給當前節點添加的子樹.
*/
public function attachLeft(BinaryTree $t) {
if ($this-isEmpty() || !$this-left-isEmpty())
return false;
$this-left = $t;
}
/**
* 刪除左子樹
*
* @return object BinaryTree 返回刪除的左子樹.
*/
public function detachLeft() {
if ($this-isEmpty())
return false;
$result = $this-left;
$this-left = new BinaryTree();
return $result;
}
/**
* 返回當前節點的右子樹
*
* @return object BinaryTree 當前節點的右子樹.
*/
public function getRight() {
if ($this-isEmpty())
return false;
return $this-right;
}
/**
* 給當前節點添加右子樹
*
* @param object BinaryTree $t 需要添加的右子樹.
*/
public function attachRight(BinaryTree $t) {
if ($this-isEmpty() || !$this-right-isEmpty())
return false;
$this-right = $t;
}
/**
* 刪除右子樹，並返回此右子樹
* @return object BinaryTree 刪除的右子樹.
*/
public function detachRight() {
if ($this-isEmpty ())
return false;
$result = $this-right;
$this-right = new BinaryTree();
return $result;
}
/**
* 先序遍歷
*/
public function preorderTraversal() {
if ($this-isEmpty()) {
return ;
}
echo ‘ ‘, $this-getKey();
$this-getLeft()-preorderTraversal();
$this-getRight()-preorderTraversal();
}
/**
* 中序遍歷
*/
public function inorderTraversal() {
if ($this-isEmpty()) {
return ;
}
$this-getLeft()-preorderTraversal();
echo ‘ ‘, $this-getKey();
$this-getRight()-preorderTraversal();
}
/**
* 後序遍歷
*/
public function postorderTraversal() {
if ($this-isEmpty()) {
return ;
}
$this-getLeft()-preorderTraversal();
$this-getRight()-preorderTraversal();
echo ‘ ‘, $this-getKey();
}
}
/**
* 二叉排序樹的PHP實現
*/
class BST extends BinaryTree {
/**
* 構造空的二叉排序樹
*/
public function __construct() {
parent::__construct(NULL, NULL, NULL);
}
/**
* 析構
*/
public function __destruct() {
parent::__destruct();
}
/**
* 測試二叉排序樹中是否包含參數所指定的值
*
* @param mixed $obj 查找的值.
* @return boolean True 如果存在於二叉排序樹中則返回真，否則為假期
*/
public function contains($obj) {
if ($this-isEmpty())
return false;
$diff = $this-compare($obj);
if ($diff == 0) {
return true;
}elseif ($diff 0) return $this-getLeft()-contains($obj);
else
return $this-getRight()-contains($obj);
}
/**
* 查找二叉排序樹中參數所指定的值的位置
*
* @param mixed $obj 查找的值.
* @return boolean True 如果存在則返回包含此值的對象，否則為NULL
*/
public function find($obj) {
if ($this-isEmpty())
return NULL;
$diff = $this-compare($obj);
if ($diff == 0)
return $this-getKey();
elseif ($diff 0) return $this-getLeft()-find($obj);
else
return $this-getRight()-find($obj);
}
/**
* 返回二叉排序樹中的最小值
* @return mixed 如果存在則返回最小值，否則返回NULL
*/
public function findMin() {
if ($this-isEmpty ())
return NULL;
elseif ($this-getLeft()-isEmpty())
return $this-getKey();
else
return $this-getLeft()-findMin();
}
/**
* 返回二叉排序樹中的最大值
* @return mixed 如果存在則返回最大值，否則返回NULL
*/
public function findMax() {
if ($this-isEmpty ())
return NULL;
elseif ($this-getRight()-isEmpty())
return $this-getKey();
else
return $this-getRight()-findMax();
}
/**
* 給二叉排序樹插入指定值
*
* @param mixed $obj 需要插入的值.
* 如果指定的值在樹中存在，則返回錯誤
*/
public function insert($obj) {
if ($this-isEmpty()) {
$this-attachKey($obj);
} else {
$diff = $this-compare($obj);
if ($diff == 0)
die(‘argu error’);
if ($diff 0) $this-getLeft()-insert($obj);
else
$this-getRight()-insert($obj);
}
$this-balance();
}
/**
* 從二叉排序樹中刪除指定的值
*
* @param mixed $obj 需要刪除的值.
*/
public function delete($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();
} else if ($diff 0) $this-getLeft()-delete($obj);
else
$this-getRight()-delete($obj);
$this-balance();
}
public function compare($obj) {
return $obj – $this-getKey();
}
/**
* Attaches the specified object as the key of this node.
* The node must be initially empty.
*
* @param object IObject $obj The key to attach.
* @exception IllegalOperationException If this node is not empty.
*/
public function attachKey($obj) {
if (!$this-isEmpty())
return false;
$this-key = $obj;
$this-left = new BST();
$this-right = new BST();
}
/**
* Balances this node.
* Does nothing in this class.
*/
protected function balance () {}
/**
* Main program.
*
* @param array $args Command-line arguments.
* @return integer Zero on success; non-zero on failure.
*/
public static function main($args) {
printf(“BinarySearchTree main program.\n”);
$root = new BST();
foreach ($args as $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();
原創文章，作者：小藍，如若轉載，請註明出處：https://www.506064.com/zh-hant/n/308810.html
微信掃一掃 
支付寶掃一掃 