如何理解数据结构当中的树?
今天刚看了数据结构当中的树,想讲一讲数据结构当中的树要怎么理解。
首先,来讲一讲树的定义:
树(Tree)是n(n>=0)个结点的有限集。n=0时称为空树。在任意一棵非空树中:(1)有且仅有一个特定的称为根(Root)的结点;(2)当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1、T2、······、Tm,其中每一个集合本身又是一棵树,并且称为根的子树(SubTree)。如下图所示:
如上图所示,图中的A就是根结点,B、D、G、H、I组成的子树和C、E、F、J组成的子树都是根结点A的子树,而D、G、H、I组成的树又是B为根结点的子树。E、J组成的树是以C为根结点的子树。
对于树的定义还需强调两点:
1.n>0时根结点是唯一的,不可能存在多个根结点。
2.m>0时,子树的个数没有限制,但它们一定是互不相交的。
树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树数称为结点的度(Degree)。度为0的结点称为叶结点(Leaf)或终端结点;度不为0的结点称为非终端结点或分支结点。除根结点之外,分支结点也称为内部结点。树的度是树内各结点的度的最大值。
我们依然以上图为例:图中B、E的结点度为1,A、C的结点度为2,D的结点度为3,而F、G、H、I、J的结点度都为0。
结点的子树的根称为该结点的孩子(Child),相应的,该结点称为孩子的双亲(Parent)。同一个双亲的孩子之间互称兄弟(Slbling)。结点的祖先是从根到该结点所经分支上的所有结点。反之,以某结点为根的子树中的任一结点都称为该结点的子孙。
继续看上图:图中A是所有结点的祖先,B是A的孩子,是D的双亲,是D、G、H、I的祖先,同理C是A的孩子,E、J、F是C的子孙,而B和C,D、E、F,D、H、I、J都互称兄弟。
结点的层次(Level)从根开始定义起,根为第一层,根的孩子为第二层。若某结点在第i层,则其子树的根就在第i+1层。其双亲在同一层的结点互为堂兄弟。树中结点的最大层次称为树的深度(Depth)或高度。如下图:
如上图所示:图中的D、E、F是堂兄弟,而G、H、I与J也是堂兄弟,上图中一共有4层,所以当前树的深度或高度为4。
如果将树种结点的各子树看成从左至右是有次序的,不能互换的,则称该树为有序树,否则称为无序树。
以上就是我对数据结构中的树的理解,如果有什么不对的地方欢迎指正!
后续将会更新树的存储结构,敬请期待!!!