定义

1.有且只有一个称为根的节点
2.有若干个互不相交的子树,这些子树本身也是一棵树
3.每个子节点只有一个父节点,但可以有多个子节点
4.没有父节点的节点称为根节点

术语解释

节点:
父节点:最上面
子节点:
子孙:
堂兄弟:
深度:从根节点到最底层节点的层数称为深度,根节点是第一层
叶子节点:没有子节点的节点
非叶子节点:有子节点的节点
度:子节点的个数

树的分类

一般树

任意一个节点的子节点的个数都不受限制

二叉树

任意一个节点的子节点的个数最多两个,且子节点的位置不可更改

分类
满二叉树

每一层的节点数都是最大节点数。
在不增加树的层数的前提下无法再多添加一个节点的二叉树。

完全二叉树

只是删除了满二叉树最底层最右边连续的若干个节点,这样形成的二叉树就是完全二叉树。
完全二叉树包含满二叉树,满二叉树是完全二叉树的一个特例。
特点:
1.知道节点的个数就能得出树的层数。
2.已知一个节点可以得出该节点的父节点和子节点,注:根节点没有父节点,叶子节点没有子节点。

二叉树的存储

通常会把一个二叉树转换成一个满二叉树后再把树的最再进行存储

森林

N个互不相交的树的集合

SICP笔记 二叉堆
You need to set install_url to use ShareThis. Please set it in _config.yml.

评论

You forgot to set the shortname for Disqus. Please set it in _config.yml.
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×