图的开始--第三天打卡之特殊的图——树(有根树)
作者:
lgd123
,
2021-07-27 19:57:40
,
所有人可见
,
阅读 256
/*树
1、树与图的区别 :
①、树是一种特殊的图,图可以有多种方法从一个点到另一个点,但图从一个点到另一个点只有一种方式。
②、树中有一个根节点,所以有种树叫有根树,但图中没有根节点。
③、树的遍历有前序,后序,中序遍历,而图的遍历可以用搜索来实现。
④、对于树来说,它具有图不具有的性质:
若树中有n个顶点,则必定会有n-1条边
⑤、所有的树都是图,但所有的图并不一定是树。
2、对于树:
①、图是一种数据结构,是实现高效算法和数据结构的基础。
②、树是由节点和连接节点的边组成的。其中节点中存在子节点和父节点的关系。
③、深度:从根节点到节点x的长度被称为x的深度,其中根节点到叶节点的最大距离,被称为树的高。
④、度:节点拥有的子树的数量被称为度。
⑤、当该节点度为0是,该点为叶节点。
3、树的储存方法之一:左子右兄弟表示法。
①、对于一个节点,它会有俩附属节点,它左边的节点,叫子节点,它右边的节点叫右兄弟节点。
②、俩节点共有一个父节点,则这俩点是兄弟节点,在该存储方法中,它会将一个节点的,不是最左边的子节点,当成自己的兄弟节点。
③、所以一个节点的所有子节点,可以转化成以该节点为首的从左到右依次是自己子节点的一个链表。
④、所以该储存方法可以将任意一颗树转化成二叉树。故:该储存方法又被称作二叉树表示法或二叉链表表示法。
⑤、实现步骤:用结构体或三个数组表示,
因为需要记录和表示节点U的父节点,节点U的最左侧的子节点、节点U右侧紧邻的兄弟节点。
*/
----------
//今天没例子了。。。。
#include<iostream>
using namespace std;
int main()
{
return 0;
}