数据结构 -- 树(一 基本概念和示意)

时间:2024-03-14 16:41:17

1.基本概念

    树是n个结点的有限集合,是一组由边相连的结点的元素组织结构。

    树结构示意图:

    数据结构 -- 树(一 基本概念和示意)

   结点的度:一个结点的子树的个数记为该结点的度;如A结点的度为3,B结点的度为2

   树的度:结点树的度数最大的值为树的度,如上图的树的度为2,因为B结点的度为2,是这颗树最大的结点度

   叶子结点:没有下一级相关联的结点为叶子结点,如E,F,C,G

   分支结点:非叶子结点为分支结点,包括根结点

   内部结点:除根结点外,分支结点为内部结点

2.二叉树

  二叉树每个结点最多只能有两个子树,称为左子树和右子树

 示意:

   数据结构 -- 树(一 基本概念和示意)

 满二叉树:非叶子结点恰好有两个子结点

 完全二叉树:除最后一层恰好有两个子结点,最后一层结点从左到右填充

结点数n与高度h关系如下:

               n=2^h-1

               2^h = n + 1

               数据结构 -- 树(一 基本概念和示意)

叶子节点数n0,度数为2的结点数n2之间的关系:

    n0 = n2 + 1

3.树的遍历

   注:遍历一个结点但是在那个时刻并不访问它。

  遍历二叉树:   

 二叉树的遍历方法:

   * 访问根

   * 访问根的左子树中的所有结点

   * 访问根的右子树中的所有结点

  前序遍历:访问根的子树之前访问根,然后访问根的左子树中的所有结点,再访问根的右子树中的所有结点

 

   * 访问根的左子树中的所有结点

  * 访问根

  * 访问根的右子树中的所有结点

  中序遍历:递归访问左子树中的结点,首先访问最左叶子结点,接下来访问该叶子结点的根结点,然后访问其右子结点

 

  * 访问根的左子树中的所有结点

  * 访问根的右子树中的所有结点

  * 访问根

  后序遍历:递归访问左子树的结点,首先访问最左叶子结点,然后访问该叶子结点的兄弟结点,再然后访问其父结点

  层序遍历:从根结点开始,每次访问一层中的结点,同一层中,从左到右访问结点

                                数据结构 -- 树(一 基本概念和示意)

前序遍历结果:A,B,C,E,F,D,G,H,I,J,K

中序遍历结果:E,C,F,B,D,A,H,G,J,I,K

 后序遍历结果:E,F,C,D,B,H,J,K,I,G,A

层序遍历结果:A,B,G,C,D,H,I,E,F,J,K

 

相关文章