版本比较
比较
标识
- 该行被添加。
- 该行被删除。
- 格式已经改变。
树的概念
树是一种用于描述一对多的数据结构,比如文件目录结构就可以用树来描述。树的定义如下:
树是n(n≥0)个结点的有限集合,n=0时称为空树,在任意一棵非空树中:
- 有且仅有一个特定的称为根的结点。
- 当n>1时,其余结点可分为m个互不相交的有限集T1,T2,……Tm,每个集合本身又是一棵树,并且称为根的子树。
注意两点,根结点是唯一的,子树互不相交。
二叉树是一种常用的树,它只有两个子结点,除此外多叉树也可能用到。
树的存储
树的存储分为顺序存储和链式存储。顺序存储是指通过数组来存储树,分为双亲表示法,孩子表示法,双新孩子表示法,如下:
Image Added
链式存储使用链表来存储树,分为孩子链表表示法和孩子兄弟表示法,如下:
Image Added
- 二叉树按层遍历。
- 二叉树前序、中序、后序遍历递归写法,非递归写法。
- 二叉树的层次遍历,双端队列写法。
目录 |
---|