加文

在这个世界上取得成就的人,都努力去寻找他们想要的机会,如果找不到机会,他们便自己创造机会。 -- 萧伯纳
随笔 - 14, 文章 - 56, 评论 - 1, 引用 - 0
数据加载中……

1. 与树有关的概念

1) 结点的度:结点拥有的子树数。

2) 树的度:树中所有结点的度的最大值。

3) 结点的层数:

4) 树的深度:树中结点的最大层数或者称为树的高度或者深度。

5) 叶子结点:度为0的点或者终端节点。

6) 分支结点:度大于0的结点。

7) 森林:m棵互不相交的树的集合为森林

8) 树不允许为空。但是二叉树允许为空,二叉树不是树,并且二叉树是有序树,左孩子和右孩子是不一样的。

2. 二叉树概念:有限个元素的集合,该集合或者为空、或者有一个称为根的元素以及两两不相交的、分别称为左子树和右子树的组成。

1) 二叉树的性质如下:

① 二叉树的第i层,共有2^(i-1)个结点。

② 深度为k二叉树最多有2^k-1个结点。

③ 二叉树中,终端节点的数目为n0;度为1的结点数目为n1,度为2的结点为n2;则n0 = n2+1;

    据此,可以引出一下结论,对于n个结点的完全二叉树:

a>,若n为奇数,则树中只有度为2和度为0的结点。其中度为2的结点数为  (n-1)/2;度为0的结点数为(n-1)/2+1;

b>,若n为偶数,则树中除了度为2和度为0的结点结点外,还有度为1的结点1个。

④ 如果有一棵n个结点的完全二叉树,自上自下,同一层自左到右连续给结点编号,则有如下关系:

a>,若i=1,则结点为i为根结点,若i>1,则结点i的父节点为『i/2』;

b>,若2i<n,则结点i的左孩子结点为2i;

c>,若2i+1<n;则结点i的右孩子结点为2i+1;

d>,若结点i为奇数,则左子树结点为i-1;

e>,若结点i为偶数,则右子树结点为i+1;

f>,结点i所在的层次为log2i+1;

由此可以引入如下结论:对于完全二叉树编号为i的结点有:

1>,若i<=n/2,则编号为i的结点为分支结点,否则为叶结点

2>,若n为奇数,则每个分支结点都有左子树和右子树;若n为偶数,则编号最大的分支结点只有左子树。

⑤  具有n个结点的完全二叉树的深度为log2(n+1)(向上取整)

2) 二叉树的存储结构

① 二叉树的顺序存储结构一般适用于完全二叉树。

② 二叉树的链式存储结构,有二叉链表和三叉链表。

3) 二叉树的遍历 

① 中序递归遍历

② 先序递归遍历

③ 后序递归遍历

④ 中序非递归

⑤ 后序非递归

⑥ 先序非递归

⑦ 层次遍历

     4) 线索二叉树

3. 树与森林

1) 树的存储结构

2) 森林,树与二叉树的转换

3) 森林与树的遍历

4. 树的应用

1) 二叉排序树

2) 平衡二叉树

3) 哈夫曼树

4) 

 

posted on 2011-10-22 21:30 chxzwj 阅读(322) 评论(0)  编辑 收藏 引用 所属分类: 数据结构


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理