数据结构---树

树结构

树的内部结构, 依靠节点和节点之间的关系, 如果说链表是一种"一对一"的关系的话, 那么树结构就是一种"一对多"的关系

但是一般画图表示树结构, 会以下面的形式来表现

下面是树结构所涉及的一些专业术语, 会根据上图来进行讲解

• 父节点和子节点

   如果已经知道什么是双向链表的中当前节点的的前一个节点, 那么当前节点的前一个节点就是父节点,

  如果不知道什么是双向链表, 那么父节点的概念也很容易理解

   像下图那样的一个树的结构, 是自上而下存在的, 那么想要到达某个节点之前, 比必然会经过另外的一些节点, 那么所经过的节点中, 离当前节点最近的节点 ,

就是当前节点的父节点(也可以称作双亲节点), 同时当前节点也被称作该父节点的一个子节点(也可以称作孩子节点)

• 根节点

  在父节点和子节点的图中, 有一个比较特殊的存在, 就是A节点, 它只有两个子节点 C和B, 但是没有父节点, 这种特殊的节点被称作根节点, 也就是一个树的根

• 兄弟节点

  当多个节点有共同的一个父节点的时候, 这些节点互为兄弟节点

• 阶度

  一颗树结构, 可以划分很多个阶度, 其实就是有多少层, 从根节点开始自上而下,根节点为1, 每经过一个节点, 以及当前节点的兄弟节点归为一层, 阶度加1.

• 宽度

  就是每个节点的分支数,

  例如:

           对于C节点, 它有3个分支, 那么C节点的宽度为3

           对于B节点, 它有2个分支, 那么B节点的宽度为2

• 深度

  一个节点的深度, 就是从根节点开始自上而下到某个节点的路径,

  例如:

          C和B节点的深度为1

          D,E,F,G,H的深度为2

  这里和阶度很像, 阶度减1正好是深度