TableOfContents

树

树形结构是一种非线性结构。

树形结构是结点之间有分支，并具有层次关系的结构。它非常类似于自然界中的树。

树结构在客观世界中是大量存在的，例如家谱、行政组织机构都可用树形象地表示。

树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程。

1. 树的实例

家族树：在现实生活中，有入如下血统关系的家族可用树形图表示：

attachment:tree.jpg

2. 树的定义

树是由n (n≥0)个结点构成的有限集合；n=0的树称为空树；当n≠0时，树中的结点应该满足以下两个条件：

3. 树的图示

倒置的树形图表示

attachment:tree2.jpg

凹入表示

attachment:indenttree.jpg

嵌套集合表示（文氏图表示）

attachment:treeset.jpg

嵌套括号表示（广义表表示）

(A(B(E,F),C,D(G,H(J,K),I)))

4. 树的相关术语

5. 树形结构的特点

6. 树的基本操作

二叉树

1. 二叉树的定义

二叉树(BinaryTree)是n(n≥0)个结点的有限集，它或者是空集(n=0)，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。

二叉树与度为2的有序树不同：在有序树中，虽然一个结点的孩子之间是有左右次序的，但是若该结点只有一个孩子，就无须区分其左右次序。而在二叉树中，即使是一个孩子也有左右之分。

2. 二叉树的相关术语

3. 二叉树五种基本形态

attachment:binarytree.jpg

二叉树可以是空集；根可以有空的左子树或右子树；或者左、右子树皆为空。

4. 二叉树的特殊形态

1、满二叉树(FullBinaryTree)

一棵深度为k且有2k-1个结点的二又树称为满二叉树。

满二叉树的特点：

2、完全二叉树(Complete BinaryTree)

若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。

attachment:completetree.jpg

完全二叉树的特点：

编号：在一棵n个结点的完全二叉树中，从树根起，自上层到下层，每层从左至右，给所有结点编号，能得到一个反映整个二叉树结构的线性序列。

从一个结点的编号就可推得其双亲，左、右孩子，兄弟等结点的编号。假设编号为i的结点是ki(1≤i≤n)，则有：

5. 二叉树的重要性质

性质1 二叉树第i层上的结点数目最多为2i-1(i≥1)。

证明：使用数学归纳法证明。

那么，因为二叉树中每个节点的度最大为2，则第k+1层的结点总数最多为第k层上结点最大数的两倍，即latex($$2\times 2^{i-1}=2^k$$)，故结论成立。证毕。

性质2 深度为k的二叉树至多有2k-1个结点(k≥1)。

性质3 在任意-棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则no=n2+1。

性质4 具有n个结点的完全二叉树的深度为

6. 二叉树的存储结构

6.1. 顺序存储

完全二叉树的顺序存储

将完全二叉树中所有结点按编号顺序依次存储在一个数组bt[0..n]中。其中：

attachment:completetree.jpg

attachment:treearray.jpg

非完全二叉树的顺序存储

将一般二叉树添上一些 "虚结点"，成为"完全二叉树"

attachment:noncompletetree.jpg

attachment:treearray2.jpg

顺序存储的特点：

顺序存储结构的定义 

   1 #define MAXSIZE 100
   2 typedef char ElemType;
   3 typedef char BOOL;
   4 struct sequence_bin_tree {
   5    ElemType elem[MAXSIZE+1]; /* 元素的值 */
   6    BOOL used[MAXSIZE+1]; /* 对应完全二叉树的编号上是否有元素 */
   7    int size; /*最大结点编号*/
   8 }
   9 typedef struct sequence_bin_tree sequence_bin_tree;

6.2. 链式存储

二叉链表

二叉树的每个结点最多有两个孩子，可以用链接方式存储二叉树。每个结点除了存储结点本身的数据外，还应设置两个指针域lchild和rchild，分别指向该结点的左孩子和右孩子。结点bintree_node的结构为：

attachment:bintreenode.jpg

attachment:linkedbintree.jpg

一棵二叉树中，所有类型为bintree_node的结点，再加上一个指向开始结点(即根结点)的bintree_node型指针root，就构成了二叉树的链式存储结构，并将其称为二叉链表。 

   1 typedef char ElemType;
   2 struct bintree_node{
   3    ElemType data; /*元素的值*/
   4    struct bintree_node *lchild; /*左孩子结点的地址*/
   5    struct bintree_node *rchild; /*右孩子结点的地址*/
   6 };
   7 typedef struct bintree_node bintree_node;
   8 typedef struct bintree_node *bintree;

二叉链表的特点：

带父节点指针的链式表示

经常要在二叉树中寻找某结点的父节点时，可在每个结点上再加一个指向其父节点的指针parent，形成一个带双亲指针的二叉链表，称作三叉链表。

attachment:link3tree.jpg 

   1 typedef char ElemType;
   2 struct tritree_node{
   3    ElemType data; /*元素的值*/
   4    struct tritree_node *lchild; /*左孩子结点的地址*/
   5    struct tritree_node *rchild; /*右孩子结点的地址*/
   6    struct tritree_node *parent; /*父结点的地址*/
   7 };
   8 typedef struct tritree_node tritree_node;
   9 typedef struct tritree_node *tritree;

7. 二叉树的操作

此处所列操作均以二叉链表为例

7.1. 遍历

遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。

访问结点所做的操作依赖于具体的应用问题，比如打印节点的数据，或者修改节点的数据等。

遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础。

三种遍历的顺序：从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作：

以上三种操作有六种执行次序： 

VLR、LVR、LRV、VRL、RVL、RLV

前三种次序与后三种次序对称，故只讨论先左后右的前三种次序：

例：如图 attachment:linkedbintree.jpg

递归实现 

   1 /*前序遍历*/
   2 void preorder(bintree t) {
   3    if (t)  {
   4       printf("%c", t->data); /*假定元素类型为char，访问操作为打印元素的值*/ 
   5       preorder(t->lchild); 
   6       preorder(t->rchild);
   7    }
   8 } 
   9 
  10 void inorder(bintree t) {
  11    if (t)  {
  12       inorder(t->lchild); 
  13       printf("%c", t->data); /*假定元素类型为char，访问操作为打印元素的值*/ 
  14       inorder(t->rchild);
  15    }
  16 } 
  17 
  18 void postorder(bintree t) {
  19    if (t)  {
  20       postorder(t->lchild); 
  21       postorder(t->rchild);
  22       printf("%c", t->data); /*假定元素类型为char，访问操作为打印元素的值*/ 
  23    }
  24 }

采用函数指针实现可以将访问与遍历分开 

   1 /*前序遍历*/
   2 void preorder(bintree t, void (*visit)(ElemType)) {
   3    if (t)  {
   4       visit(t->data);
   5       preorder(t->lchild, visit); 
   6       preorder(t->rchild, visit);
   7    }
   8 } 
   9 
  10 void inorder(bintree t, void (*visit)(ElemType)) {
  11    if (t)  {
  12       inorder(t->lchild, visit); 
  13       visit(t->data);
  14       inorder(t->rchild, visit);
  15    }
  16 } 
  17 
  18 void postorder(bintree t, void (*visit)(ElemType)) {
  19    if (t)  {
  20       postorder(t->lchild, visit); 
  21       postorder(t->rchild, visit);
  22       visit(t->data); 
  23    }
  24 }

8. 练习

树、森林和二叉树的关系

哈夫曼树及其应用

ch3n2k.com | Copyright (c) 2004-2020 czk.