Py008-01-07堆排序前传树与二叉树

树

树是一种数据结构

比如：目录结构

  • 树是一种可以递归定义的数据结构
  • 树由n个节点组成的集合
    • 如果n=0,那是一棵空树
    • 如果n>0,那存在一个节点作为树的根节点，其他节点可以分为m个集合，每个集合本身又是一棵树

树的基本概念

根节点，叶子节点

  • 如上图，A就是根节点
  • 不能分叉的节点就是叶子节点 如B,C,H,I,P,Q,K,L,M,N

树的深度(高度)

  • 看它的递归深度 如上为 4

树的度

  • 就是最大分叉的个数
1
2
3
4
5
如 E 的度是2
如 F 的度是3
如 A 的度是6

所以如上图   树的度就是6

孩子节点，父节点

1
2
E是I的父节点
I是E的子节点

子树

1
如 把 E,I,J,P,Q拎出来 E就是一个子树

二叉树

  • 二叉树就是度不超过2的树
  • 每个节点最多有两个子节点
  • 两个孩子节点被区分为左孩子节点和右孩子节点

二叉树的存储方式

  • 链式存储方式
  • 顺序存储方式(就是用一个列表来存储)

思考：如果从孩子找父亲该怎么找？

1
2
如子节点下标为9
(9-1)整除2=4