专业定义:
有且只有一个称为根的节点
有若干个互不相交的子树,这些子树本身也是一颗树
通俗定义:
树是由节点和边组成
每个节点只有一个父节点但可以有多个子节点
但有一个节点例外,该节点没有父节点,此节点称为根节点
专业术语:
节点,父节点,子节点
子孙,堂兄弟
深度:从根节点到最底层节点的层数称之为深度,根节点是第一层
叶子节点:没有子节点的节点
非终端节点:实际就是非叶子节点
度:子节点的个数
一般树:任意一个节点的子节点的个数都不受限制
二叉树:任意一个节点的子节点个数最多两个,且子节点的位置不可更改
分类
一般二叉树
满二叉树:在不增加树层数的前提下,无法再多添加一个节点的二叉树就是满二叉树
完全二叉树:如果只是删除了满二叉树最底层最右边的连续若干个节点,这样形成的二叉树就是完全二叉树。(满二叉树是完全二叉树的一个特例)
森林:n个互不相交的树的集合
二叉树的存储
连续存储【完全二叉树】
优点:查找某个节点的父节点和子节点(也包括判断有没有子节点)
缺点:耗用内存空间过大
链式存储
一般树的存储
双亲表示法:求父节点方便
孩子表示法:求子节点方便
双亲孩子表示法:求父节点和子节点都很方便
二叉树表示法:把一个普通树转化成二叉树来存储
具体转换方法:
设法保证任意一个节点的左指针域指向它的第一个孩子,右指针域指向它的兄弟,只要满足此条件,就可以把一个普通树转化为二叉树。
一个普通树转化成的二叉树一定没有右子树
森林的存储
先把森林转化为二叉树,再存储二叉树:
将相邻的父节点依次作为节点的右子树再对各父节点进行转化
原文:https://www.cnblogs.com/codeke/p/12585166.html