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

遍历次序的另一种理解

attachment:traverse.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 }

7.2. 创建

基于先序遍历的构造，即以二叉树的先序序列为输入构造。

先序序列中必须加入虚结点以示空指针的位置。

建立下图所示二叉树，其输入的先序序列是：ABD###CE##F##。

attachment:traverse.jpg

假设虚结点输入时以#字符表示，相应的构造算法为： 

   1 bintree create_bintree() {
   2    bintree T;
   3    char ch = getchar();
   4    if (ch == '#') 
   5       T = NULL;  /*读入空格，将相应指针置空 */
   6    else { /* 读入非空格 */
   7       T=(bintree_node *)malloc(sizeof(bintree_node)); /*生成结点*/
   8       T->data = ch;
   9       T->lchild = create_bintree(); /*构造左子树*/
  10       T->rchild = create_bintree(); /*构造右子树*/
  11    }
  12    return T;
  13 }

7.3. 输出叶子结点

输出二叉树中所有叶子结点的值 

   1 void traverse_leaf(bintree t) {
   2    if (t)  {
   3       if(t->lchild == NULL && t->rchild == NULL)
   4          printf("%c", t->data); /*假定元素类型为char，访问操作为打印元素的值*/ 
   5       preorder(t->lchild); 
   6       preorder(t->rchild);
   7    }
   8 }

7.4. 查找结点

在二叉树t中查找值为x的结点，找到了返回指向元素值为x的结点的指针，找不到返回NULL 

   1 bintree locate(bintree t, ElemType x) {
   2    bintree p;
   3    if (t == NULL)
   4       return NULL;
   5    else if( t->data == x)
   6       return t;
   7    else {
   8       p = locate(t->lchild, x);
   9       if (p)
  10          return p;
  11       else
  12          return locate(t->rchild, x);
  13    }
  14 }

7.5. 计算结点个数

计算二叉树t中的节点个数 

   1 int numofnode(bintree t) {
   2    if( t == NULL)
   3       return 0;
   4    else 
   5       return numofnode(t->lchild) + numofnode(t->rchild) + 1;
   6 }

计算二叉树t中的叶子结点个数 

   1 int numofleaf(bintree t) {
   2    if( t == NULL )
   3       return 0;
   4    else if(t->lchild == NULL && t->rchild == NULL)
   5       return 1;
   6    else 
   7       return numofleaf(t->lchild) + numofleaf(t->rchild);
   8 }

7.6. 判断相等

判断两个二叉树t1和t2是否完全相同。 

   1 int isequal( bintree t1, bintree t2) {
   2    if( t1 == NULL && t2 == NULL)
   3       return 1;
   4    else if( t1 != NULL && t2 != NULL)
   5       return t1->data == t2 -> data && 
   6          isequal( t1->lchild, t2 -> lchild) && 
   7          isequal(t1->rchild, t2->rchild);
   8    else
   9       return 0;
  10 }

7.7. 计算高度

计算二叉树t的高度 

   1 int max(int a, int b) {
   2    return a > b ? a : b;
   3 }
   4 int depth(bintree t) {
   5    if( t == NULL)
   6       return 0;
   7    else
   8       return max( depth(t->lchild), depth(t->rchild) ) +1;
   9 }

8. 练习

树、森林和二叉树的关系

哈夫曼树及其应用

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