树的定义

树是n (n>0)个结点的有限集合 n = 0 就是空树了
树有一下几个条件.

  • 有且仅有有个根结点

  • 除了跟结点外 其余结点呗分成了 n 个互不相交的子树

    基本术语

  • 结点 树中的数据元素 节点的度 这个节点的子树的个数

  • 树的度 树中结点度的最大值
  • 叶子结点 度为0的结点 也叫终端结点
  • 分支结点 也叫非终端结点 不是叶子结点就是分支结点
  • 孩子 、双亲、兄弟节点 这个不知道咋说 很好理解吧 还有祖先 子孙
  • 路径
  • 路径长度
  • 结点的层数
  • 树的深度
  • 层序编号
  • 有序树

  • 无序树

    常用操作

  • 前序遍历

    • 中左右
  • 后序遍历
    • 左右中

  • 层序遍历（广度遍历）

    • 一层一层

      树的表示方法

  • 双亲表示法

数据域含有两个元素 一个是我们存着的数据，另一个是这个节点双亲的坐标

  • 孩子表示法
  • 多重链表表示法
    • 指针域指向该节点的所有孩子节点，指针数等于该节点的度
    • 指针域指向该节点的所有孩子节点，指针数等于树的度
  • 孩子链表表示法
  • 双亲孩子表示法
  • 孩子兄弟表示法