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

一、总结

一句话总结：

双亲表示法：data parent：$tree[1] = ["B",0];
孩子表示法：data firstChild：firstChild把他的所有兄弟都用链表存起来
双亲孩子表示法：比孩子表示法，多一个父亲指针。
孩子兄弟表示法：data,存储数据，firstchild第一个孩子节点，rightsib右兄弟节点

1、树的度 是什么意思？

树内各结点的度的 最大值

2、树的 存储方式 中的 双亲表示法 的 代码如何实现，及这种存储方式的 优缺点？

data parent：$tree[1] = ["B",0];
优缺点：便于找到双亲，如果找到孩子则需要遍历所有节点。
<?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);

//双亲表示法.便于找到双亲节点（即父节点）缺点不便于寻找孩子,寻找孩子需要遍历整棵树。

3、树的 存储方式 中的 孩子表示法 的 代码如何实现，及这种存储方式的 优缺点？

data firstChild：firstChild把他的所有兄弟都用链表存起来
$trees[4] = new CTBox("D",new CTNode(0,new CTNode(1,new CTNode(2))));
优缺点:便于查询孩子和兄弟节点，但是查询双亲节点时，显得不方便

节点：index 存储链表/数组 索引下标；next 指向下个兄弟 CTNode 节点；
树：$data 存储节点数据；$firstChild 存储第一个孩子节点 类型为CTNode

<?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;

4、树的 存储方式 中的 双亲孩子表示法 的 代码如何实现，及这种存储方式的 优缺点？

比孩子表示法，多一个父亲指针：

5、树的 存储方式 中的 孩子兄弟表示法 的 代码如何实现，及这种存储方式的 优缺点？

data,存储数据，firstchild第一个孩子节点，rightsib右兄弟节点：$trees[5] = new CSNode("E",$trees[0],$trees[4]);
<?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]);

6、树的遍历方式有哪些？

先根遍历：若树非空，则先访问根结点，再按照从左到右的顺序遍历根结点的每一棵子树。
后根遍历：若树非空，则按照从左到右的顺序遍历根结点的每一棵子树，之后再访问根结点。

7、树有哪些常见的类型？

决策树：比如象棋开局，每个象有两种走法，每个车有两种走法，等等，所以象棋开局有42种走法（各个棋子走法之和），这就是决策树
二叉树：每个结点最多有两个子树的树结构
平衡二叉树：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树

8、决策树是什么？

决策情况：比如象棋开局，每个象有两种走法，每个车有两种走法，等等，所以象棋开局有42种走法（各个棋子走法之和），这就是决策树

9、二叉搜索树/二叉排序树 是什么？

若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；
若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
左、右子树也分别为二叉排序树；

10、二叉搜索树/二叉排序树 如何查找节点？

当前节点比要找的值小就去右子树，否者去左子树

11、二叉树的 遍历方式 有哪些？

先序遍历(DLR) 根左右 preOrder
中序遍历(LDR) 左根右 inOrder
后序遍历(LRD) 左右根 postOrder
<?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>";

12、二叉树代码如何实现？

$data，$left，$right
class tree{

    public $data;

    public $left;

    public $right;

    public function preOrder(){

    }

    public function inOrder(){

    }

    Public function postOrder(){}

}

13、树，森林，二叉树之间的如何转换 ？

任何一棵树都可以按照一定的算法转换成二叉树。
任何森林都可以按照一定的算法转换成树，或者二叉树。
拥有了二叉树，调整成平衡二叉搜索树，我们即拥有了o(log2n)的查询效率。

14、树如何转换为二叉树？

（1）加线。就是在所有兄弟结点之间加一条连线；
（2）抹线。就是对树中的每个结点，只保留他与第一个孩子结点之间的连线，删除它与其它孩子结点之间的连线；
（3）旋转。就是以树的根结点为轴心，将整棵树顺时针旋转一定角度，使之结构层次分明。

15、森林如何转换为二叉树？

（1）先把每棵树转换为二叉树；
（2）变为右孩子节点：第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子结点，用线连接起来。当所有的二叉树连接起来后得到的二叉树就是由森林转换得到的二叉树。

二、内容在总结中

 

最新文章

  1. php的memcache安装，在window10下面
  2. 初识JavaScript 变量, 操作符, 数组
  3. Java初学随笔
  4. Android 检查手机网络是否可用
  5. WordPaster-Chrome浏览器控件安装方法
  6. CDH上执行WordCount的意外和收获
  7. 转：JS日期加减,日期运算
  8. HDU 4337 King Arthur&amp;#39;s Knights 它输出一个哈密顿电路
  9. Java 静态代理与动态代理
  10. 让python bottle框架支持jquery ajax的RESTful风格的PUT和DELETE等请求
  11. JAVA 锁之 Synchronied
  12. unity3d入门教程
  13. Java序列化相关
  14. Sublime Text 执行后只有运行时间，没有执行结果！解决方法！
  15. Linux常用基本命令：三剑客命令之-awk输入输出分隔符
  16. [小问题笔记（九）] SQL语句Not IN 效率低，用 NOT EXISTS试试
  17. CustomValidator控件用法
  18. Ubuntu Linux系统三种方法添加本地软件库
  19. 跳转到appstore下载app的链接 记录一下
  20. python 提示 AttributeError: module &#39;json&#39; has no attribute &#39;dumps&#39;

热门文章

  1. idea中项目发布到svn服务器
  2. Mysql优化-概述
  3. canvas填充规则，非零环绕
  4. sql server 的存储过程
  5. [笔记]Laravel TDD 胡乱记录
  6. day24 模块
  7. 网页存储倒计时与解决网页cookie保存多个相同key问题
  8. golang模块viper读取配置文件
  9. 微信sdk 隐藏右上角菜单项
  10. Git 比较两个分支之间的差异