php数据结构课程---5、树（树的 存储方式 有哪些）

<?php //双亲表示法//
// A
// / \
// B C
// / / \
// D E F
// /|\ \
// G H I J
//$tree = [];$tree[0] = ["A",-1];
$tree[1] = ["B",0];
$tree[2] = ["C",0];
$tree[3] = ["D",1];
$tree[4] = ["E",2];
$tree[5] = ["F",2];
$tree[6] = ["G",3];
$tree[7] = ["H",3];
$tree[6] = ["I",3];
$tree[8] = ["J",4];echo "<pre>";
var_dump($tree);//双亲表示法.便于找到双亲节点（即父节点）缺点不便于寻找孩子,寻找孩子需要遍历整棵树。

<?php //孩子表示法//节点，
// index 存储链表/数组 索引下标
// next 指向下个兄弟 CTNode 节点
class CTNode{
public $index; //通过索引获取数据值
public $next; public function __construct($index,$ns = null){
$this->index = $index;
$this->next = $ns;
}
}// $data 存储节点数据
// $firstChild 存储第一个孩子节点 类型为CTNode
class CTBox{
public $data;
// public $parent;
public $firstChild; public function __construct($data,$firstChild = null){
$this->data = $data;
$this->firstChild = $firstChild;
}
}//
// A
// / \
// B C
// / / \
// D E F
// /|\ \
// G H I J
////使用数组存储整棵树
$trees = [];
$trees[0] = new CTBox("G");
$trees[1] = new CTBox("H");
$trees[2] = new CTBox("I");
$trees[3] = new CTBox("J");
// 第一个孩子下标 兄弟下标 兄弟下标
$trees[4] = new CTBox("D",new CTNode(0,new CTNode(1,new CTNode(2))));
// 第一个孩子下标
$trees[5] = new CTBox("E",new CTNode(3));
$trees[6] = new CTBox("F");
// 第一个孩子下标
$trees[7] = new CTBox("B",new CTNode(4));
// 第一个孩子下标 兄弟下标 兄弟下标
$trees[8] = new CTBox("C",new CTNode(5,new CTNode(6)));
$trees[9] = new CTBox("A",new CTNode(7,new CTNode(8)));//找到树D节点，以及D的子树
echo "<pre>";
echo "节点为".$trees[4]->data."的子节点如下:";
echo "<br>";
$index = $trees[4]->firstChild->index;
echo $trees[$index]->data;
echo "<br>";
$index = $trees[4]->firstChild->next->index;
echo $trees[$index]->data;
echo "<br>";
$index = $trees[4]->firstChild->next->next->index;
echo $trees[$index]->data;

<?php // 孩子兄弟表示法class CSNode{
public $data;
public $child;
public $rightsb; public function __construct($d,$c,$r){
$this->data = $d;
$this->child = $c;
$this->rightsb = $r;
}}//
// A
// / \
// B C
// / / \
// D E F
// /|\ \
// G H I J
//$trees = [];
$trees[0] = new CSNode("J");
$trees[1] = new CSNode("I");
$trees[2] = new CSNode("H",null,$trees[1]);
$trees[3] = new CSNode("G",null,$trees[2]);
$trees[4] = new CSNode("F");
$trees[5] = new CSNode("E",$trees[0],$trees[4]);
$trees[6] = new CSNode("D",$trees[3]);
$trees[7] = new CSNode("C",$trees[5]);
$trees[8] = new CSNode("B",$trees[6],$trees[7]);
$trees[9] = new CSNode("A",$trees[8]);

<?php //
// 8
// / \
// 3 10
// / \ \
// 1 6 14
// / \ /
// 4 7 13
//class tree{
public $data;
public $left = null ;
public $right = null;
public function __construct($data){
$this->data = $data;
} // DLR
public function preOrder(){
echo $this->data." ";
if($this->left)
$this->left->preOrder();
if($this->right)
$this->right->preOrder();
}
// LDR
public function inOrder(){
if($this->left)
$this->left->inOrder();
echo $this->data." ";
if($this->right)
$this->right->inOrder();
}
// LRD
public function postOrder(){
if($this->left)
$this->left->postOrder();
if($this->right)
$this->right->postOrder();
echo $this->data." ";
}
}$trees = new tree(8);
$trees->left = new tree(3);
$trees->left->left = new tree(1);
$trees->left->right = new tree(6);
$trees->left->right->left = new tree(4);
$trees->left->right->right = new tree(7);$trees->right = new tree(10);
$trees->right->right = new tree(14);
$trees->right->right->left = new tree(13);echo "<pre>";
$trees->preOrder();
echo "<br>";
$trees->inOrder();
echo "<br>";
$trees->postOrder();
echo "<br>";

class tree{
public $data;
public $left;
public $right;
public function preOrder(){
}
public function inOrder(){
}
Public function postOrder(){}
}