数据结构与算法
树与二叉树
2017年春
本次课内容
前面讨论的数据结构都属于线性结构，线性结构的特点是逻辑结构简单，易于进行查找、插入和删除等操作。它主要用于对客观世界中具有单一的前驱和后继的数据关系进行描述，而现实中的许多事物的关系并非这样简单。如人类社会的家族谱、各种社会组织机构以及城市交通、通讯等，这些事物中的联系都是非线性的，采用非线性结构进行描绘会更明确和便利。
在计算机科学中树（tree）是非常有用的抽象概念，其中以树和二叉树最为常用，直观看来，树是以分支关系定义的层次结构，树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织都可以用树来形象表示。树在计算机领域中也得到了广泛应用，如在编译程序中，可用树来表示源程序的语法结构。又如在数据库系统中，树形结构也是信息的重要组织形式之一。
树的基础知识
树（tree）是\(n(n\geq 0)\)个节点的有限集。在任意一棵非空树中：（1）有且仅有一个特定的称为根（root）的节点；（2）当\(n>1\)时，其余节点可分为\(m(m>0)\)个互不相交的有限集\(T_1\)，\(T_2\)，…，\(T_m\)，其中每一个集合本身又是一棵树，并且称为根的子树（subtree）。
树具有下面两个特点：
- 树的根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点。
- 树中所有结点可以有零个或多个后继结点。
树的相关术语
一棵树是一些节点的集合。这个集合可以是空集；若非空，则一棵树由根节点以及0个或多个非空的（子）树\(T_1\)，\(T_2\)，…\(T_m\)组成，这些子树中每一棵的根都被来自根节点的一条有向的边（edge）连接。树的节点包含一个数据元素及若干指向其子树的分支。
节点拥有的子树数被称为节点的度（degree）。度为0的节点称为叶子（leaf）或终端节点。度不为0的节点称为非终端节点或分支节点。除根节点之外，分支节点也称为内部节点。树的度是树内各节点的度的最大值。
节点的子树的根称为该节点的孩子（child），相应地，该节点称为孩子的双亲（parent）。同一个双亲的孩子之间互称兄弟（sibling）。将这些关系进一步推广，节点的祖先是从根到该节点所经分支上的所有节点。
树的相关术语二
从节点\(n_1\)到\(n_k\)的路径（path）定义为节点\(n_1\)，\(n_2\)，…，\(n_k\)的一个序列，使得对于\(1\leq i<k\)，节点\(n_i\)是\(n_{i+1}\)的父亲。这个路径的长（length）为该路径上的边的条数，即\(k-1\)。从每一个节点到它自己有一条长为0的路径。注意，在一棵树中从根到每个节点只存在一条路径。
节点的层次（level）从根开始定义起，根为第一层，根的孩子为第二层。若某节点在第\(l\)层，则其子孙的根就在第\(l+1\)层。其双亲在同一层的节点互为堂兄弟。根的深度为0。\(n_i\)的高（height）是从\(n_i\)到一片树叶的最大路径的长。因此所以的树叶的高都是0，而一棵树的高等于它的根的高。一棵树的深度等于它的最深的树叶的深度，该深度等于这棵树的高。
如果将树中节点的各子树看成从左至右是有次序的（即不能互换），则称该树为有序树，否则称为无序树。在有序树中最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子。
森林的概念
森林（forest）是\(m(m\geq 0)\)棵互不相交的树的集合。对树中每个节点而言，其子树的集合即为森林。由此，也可以由森林和树相互递归的定义来描述树。
就逻辑结构而言，任何一棵树都是一个二元组\(Tree=(root,F)\)，其中：\(root\)是数据元素，称作树的根节点；\(F\)是\(m(m\geq 0)\)棵树的森林，\(F\)=(\(T_1\)，\(T_2\)，…，\(T_m\))，其中\(T_i\)=(\(r_i\)，\(F_i\))称作根\(root\)的第\(i\)棵子树；当\(m\neq 0\)时，在树根和其子树森林之间存在下列关系： \[RF=\lbrace <root,r_i>|i=1,2,\text{…},m,m>0 \rbrace\]
上述定义将有助于得到森林和树之间转换的递归定义
树的表示
树的结构定义是一个递归的定义，即在树的定义中又用到树的概念，它道出了树的固有特性。有三种常见的表示方法：
- 直观表示法
- 是以嵌套集合（即是一些集合的集体，对于其中任何两个集合，或者不相交，或者一个包含另一个）的形式表示的；
- 凹入表示法（类似书的编目）。
表示方法的多样化，正说明了树结构在日常生活中及计算机程序设计中的重要性。一般来说，分等级的分类方案都可用层次结构来表示，也就是说，都可形成一个树结构。
树ADT
// 初始化一棵空树t
Initiate（t）
// 求结点x所在树的根结点
Root（x）
//求树t中结点x的双亲结点
Parent（t，x）
// 求树t中结点x的第i个孩子结点
Child（t，x，i）
// 求树t中结点x的第一个右边兄弟结点，简称求右兄弟结点
RightSibling（t，x）
// 把以s为根结点的树插入到树t中作为结点x的第i棵子树
Insert（t，x，i，s）
// 在树t中删除结点x的第i棵子树
Delete（t，x，i）
// 树的遍历操作，即按某种方式访问树t中的每个结点，且使每个结点只被访问一次
Traverse（t）树的存储方法
双亲表示法
实现：定义结构数组存放树的结点，每个结点含两个域：
- 数据域：存放结点本身信息
- 双亲域：指示本结点的双亲结点在数组中位置
孩子表示法
多重链表：每个结点有多个指针域，分别指向其子树的根
孩子兄弟表示法(二叉树表示法)
实现：用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和右兄弟结点的指针。
树的二叉树表示法实现
为了实现一棵树，在每一个节点除数据外还要有一些指针，使得该节点的每一个儿子都有一个指针指向它。然而，由于每个节点的儿子数变化可以很大并且事先不知道，因此在数据结构中建立到各儿子节点直接的链接是不可行的，因为这样会浪费太多空间。解法很简单：将每个节点的所有儿子都放在树节点的链表中。如程序中的声明就是典型的声明。
typedef struct _Tree Tree; /* 树结构 */
typedef struct _TreeNode TreeNode; /* 树的节点 */
typedef void *TreeValue; /* 树中存储的数据 */
#define TREE_NULL ((void *) 0) /* 树的空指针数据 */
struct TreeNode {
TreeValue value;
TreeNode *firstchild;
TreeNode *nextsibling;
};
struct _Tree {
TreeNode *rootnode;
unsigned int nodenum;
};树的遍历
树有很多应用。流行的用法之一是包括UNIX、VAX/VMS和DOS在内的许多常用操作系统中的目录结构。
设想我们要列出目录中所有文件的名字。
我们的输出格式将是：深度为\(d_i\)的文件的名字将被\(d_i\)次跳格（tab）缩进后输出。该算法的伪代码为：
static void list_dir(DirectoryOrFile D, int depth) {
if(D is a legitimate entry) { /* D合法 */
print_name(D, depth);
if(D is a directory) /* D是一个目录 */
for each child, C, of D
list_dir(C, depth-1);
}
}
void list_directory(DirectoryOrFile D) {
list_dir(D, 0);
}树的前序遍历
算法的核心为递归过程list_dir。为了显示根时不进行缩进，该例程需要从目录名和深度0开始。这里的深度是一个内部簿记变量，而不是主调例程能够期望知道的那种参数。因此，驱动例程list_directory用于将递归例程和外界连接起来。 这种遍历的策略叫做前序遍历（preorder traversal）。在前序遍历中，对节点的处理工作是在它的诸儿子节点被处理之前（pre）进行的。
/usr
mark
book
ch1.r
ch2.r
ch3.r
course
cop3530
fall96
syl.r
spr97
syl.r
sum97
syl.r
junk.c
alex
junk.c
bill
work
course
cop3212
fall96
grades
prog1.r
prog2.r
fall97
prog2.r
prog1.r
grades树的后序遍历
另一种遍历树的方法是后序遍历（postorder traversal）。在后序遍历中，在一个节点处的工作是在它的诸儿子节点被计算后（post）进行的。
由于目录本身也是文件，因此它们也有大小。设想我们要计算被该树所有文件占用的磁盘块的总数。最自然的做法是找出含于子目录“/usr/mark(30)”、“/usr/alex(9)”和“/usr/bill(32)”的块的个数。于是，磁盘块的总数就是子目录中的块的总数（71）加上“/usr”使用的一个快，共72个块。下面是这种遍历策略的伪代码：
static void size_directory(DirectoryOrFile D) {
int totalsize;
totalsize = 0;
if(D is a legitimate entry) {
totalsize = file_size(D);
if(D is a directory)
for each child, C, of D
totalsize += size_dirctory(C);
}
return totalsize;
}后序遍历的结果
ch1.r 3
ch2.r 2
ch3.r 4
book 10
syl.r 1
fall96 2
syl.r 5
spr97 6
syl.r 2
sum97 3
cop3530 12
course 13
junk.c 6
mark 30
junk.c 8
alex 9
work 1
grades 3
prog1.r 4
prog2.r 1
fall96 9
prog2.r 2
prog1.r 7
grades 9
fall97 19
cop3212 29
course 30
bill 32
/usr 72
二叉树定义
二叉树（binary tree）是一种树型结构，其中每个节点至多有两棵子树（即二叉树中不存在度大于2的节点），并且，二叉树的子树有左右之分，其次序不能任意颠倒。
二叉树是树形结构中的一个重要类型，许多实际问题抽象出来的数据结构往往是二叉树的形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此，二叉树显得特别重要。
几种特殊形式的二叉树
完全二叉树和满二叉树是两种特殊形态的二叉树。
一棵深度为\(k\)且有\(2^k-1\)个节点的二叉树称为满二叉树。这种树的特点是每一层上的节点数都是最大节点数。
可以对满二叉树的节点进行连续编号，约定编号从根节点起，自上而下，自左至右。由此可引出完全二叉树的定义。深度为\(k\)的，有\(n\)个节点的二叉树，当且仅当其每一个节点都与深度为\(k\)的满二叉树中编号从1至\(n\)的节点一一对应时，称之为完全二叉树。显然，这种树的特点是：
- 叶子节点只可能在层次最大的两层上出现；
- 对任一节点，若其右分支下的子孙的最大层次为\(l\)，则其左分支下的子孙的最大层次必为\(l\)或\(l+1\)。
二叉树的性质
性质1 \(\text{ }\)在二叉树的第\(i\)层上至多有\(2^{i-1}\)个节点（\(i\geq 1\)）。
利用归纳法容易证得此性质。
\(i=1\)时，只有一个根节点。相反，\(2^{i-1}=2^0=1\)是成立的。
现在假定对所以的\(j\)，\(1\leq j<i\)，命题成立，即第\(j\)层上至多有\(2^{j-1}\)个节点。那么，可以证明\(j=i\)时命题也成立。
由归纳假设：第\(i-1\)层上至多有\(2^{i-2}\)个节点。由于二叉树的每个节点的度至多为2，故在第\(i\)层上的最大节点数为\(i-1\)层上的最大节点数的2倍，即\(2\times 2^{i-2}=2^{i-1}\)。
二叉树的性质二
性质2\(\text{ }\)深度为\(k\)的二叉树至多有\(2^k-1\)个节点，（\(k\geq 1\)）。
由性质1可见，深度为\(k\)的二叉树的最大节点数为 \[\sum_{i=1}^{k}{\text{(第i层上的最大节点数)}}=\sum_{i=1}^{k}{2^{i-1}}=2^k-1\]
二叉树的性质三
性质3 \(\text{ }\)对任何一棵二叉树\(T\)，如果其终端节点数为\(n_0\)，度为2的节点数为\(n_2\)，则\(n_0=n_2+1\)。
设\(n_1\)为二叉树\(T\)中度为1的节点数。因为二叉树中所有节点的度均小于或等于2，所以其节点总数为
\[n=n_0+n_1+n_2\]
再看二叉树中的分支数。除了根节点外，其余节点都有一个分支进入，设\(B\)为分支总数，则\(n=B+1\)。由于这些分支是由度为1或2的节点射出的，所以又有\(B=n_1+2n_2\)。于是得
\[n=n_1+2n_2+1\]
由上可得
\[n_0=n_2+1\]
二叉树的性质四
性质4 \(\text{ }\)具有\(n\)个节点的完全二叉树的深度为\(\lfloor \log_2 n \rfloor+1\)（\(\lfloor x\rfloor\)为不大于x的最大整数，反之，\(\lceil x\rceil\)为不小于x的最小整数）。
证明：假设深度为\(k\)，则根据性质2和完全二叉树的定义有 \[2^{k-1}-1<n\leq 2^k-1\text{ 或}2^{k-1}\leq n<2^k\]
于是\(k-1\leq \log_2 n<k\)，因为\(k\)是整数，所以\(k=\lfloor \log_2 n \rfloor+1\).
二叉树的性质五
性质5 \(\text{ }\)如果对一棵有n个节点的完全二叉树（其深度为\(\lfloor \log_2 n \rfloor+1\)）的节点按层序编号（从第1层到第\(\lfloor \log_2 n \rfloor+1\)层，每层从左到右），则对任一节点\(i(1\leq i\leq n)\)，有
（1）如果\(i=1\)，则节点\(i\)是二叉树的根，无双亲；如果\(i>1\)，则其双亲\(PARENT(i)\)是节点\(\lfloor i/2\rfloor\)。
（2）如果\(2i>n\)，则节点\(i\)无左孩子（节点\(i\)为叶子节点）；否则其左孩子\(LCHILD(i)\)是节点\(2i\)。
（3）如果\(2i+1>n\)，则节点\(i\)无右孩子；否则其右孩子\(RCHILD(i)\)是节点\(2i+1\)。
二叉树的性质五证明
我们只要先证明（2）和（3），便可以从（2）和（3）导出（1）。
对于\(i=1\)，由完全二叉树的定义，其左孩子是节点2。若\(2>n\)，即不存在节点2，此时节点\(i\)无左孩子。节点\(i\)的右孩子也只能是节点3，若节点3不存在，即\(3>n\)，此时节点\(i\)无右孩子。
对于\(i>1\)，可分两种情况讨论：
（1）设第\(j(1\leq j \leq \lfloor \log_2 n \rfloor)\)层的第一个节点的编号为\(i\)（由二叉树的定义和性质2可知\(i=2^{j-1}\)），则其左孩子必为第\(j+1\)层的第一个节点，其编号为\(2^j=2(2^{j-1})=2i\)，若\(2i>n\)，则无左孩子；其右孩子必为第\(j+1\)层第二个节点，其编号为\(2i+1\)，若\(2i+1>n\)，则无右孩子；
（2）假设第\(j(1\leq j \leq \lfloor \log_2 n \rfloor)\)层上某个节点的编号为\(i(2^{j-1}\leq i<2^j-1)\)，且\(2i+1<n\)，则其左孩子为\(2i\)，右孩子为\(2i+1\)，又编号为\(i+1\)的节点是编号为\(i\)的节点的右兄弟或者堂兄弟，若它有左孩子，则编号必为\(2i+2=2(i+1)\)，若它有右孩子，则其编号必为\(2i+3=2(i+1)+1\)。
二叉树结构体定义
因为一棵二叉树最多有两个儿子，所以我们可以用指针直接指向它们。树节点的声明在结构上类似于双链表的声明。在声明中，一个节点就是由value（数据）信息加上两个指向孩子节点的指针（children[2]）和指向双亲节点的指针（parent）组成的结构
/* 二叉树的左、右孩子标记 */
typedef enum {
BITREE_NODE_LEFT = 0,
BITREE_NODE_RIGHT = 1
} BiTreeNodeSide;
typedef struct _BiTree BiTree; /* 二叉树结构 */
typedef struct _BiTreeNode BiTreeNode; /* 二叉树节点 */
typedef void *BiTreeValue; /* 二叉树中存储的数据 */
#define BITREE_NULL ((void *) 0) /* 二叉树的空指针数据 */
struct _BiTreeNode {
BiTreeNode *children[2];
BiTreeNode *parent;
BiTreeValue value;
};
struct _BiTree {
BiTreeNode *rootnode; /* 根节点 */
unsigned int nodenum; /* 节点数 */
};注意: 树与节点是分开定义的, 这样逻辑比较清楚.
定义二叉树的方法
// 生成一颗二叉树
BiTree *bi_tree_new();
// 销毁一个二叉树
void bi_tree_free(BiTree *tree);
/**
* Insert a new key-value pair into an binary tree.
*
* @param tree The tree.
* @param value The value to insert.
* @param parent The parent where to insert.
* @param side Insert to left or right.
* @return The newly created tree node containing the
* key and value, or NULL if it was not possible
* to allocate the new memory.
*/
BiTreeNode * bi_tree_insert(BiTree *tree, BiTreeValue value, BiTreeNode *parent, BiTreeNodeSide side);
// 删除一个节点
void bi_tree_remove_node(BiTree *tree, BiTreeNode *node);
// 得到根节点
BiTreeNode *bi_tree_root_node(BiTree *tree);
// 得到节点上的对象
BiTreeValue bi_tree_node_value(BiTreeNode *node);
// 得到节点的子节点
BiTreeNode *bi_tree_node_child(BiTreeNode *node, BiTreeNodeSide side);
// 得到父节点
BiTreeNode *bi_tree_node_parent(BiTreeNode *node);注意:
- 上述定义都放在bi-tree.h文件中, 对于调用者只需要头文件即可.
- 注释,变量和函数的命名都要规范, 清晰, 一致.
实现生成二叉树的方法
算法的实现依赖于具体的存储结构，当二叉树采用不同的结构存储时，各种基本操作的实现算法是不同的。基于上述二叉树的存储结构，下面讨论一些常用操作的实现算法。
BiTree * bi_tree_new() {
BiTree *new_tree;
new_tree = (BiTree *) malloc(sizeof(BiTree));
if (new_tree == NULL) {
return NULL;
}
new_tree->root_node = NULL;
new_tree->num_nodes = 0;
return new_tree;
}注意: 根节点要置为NULL, 节点个数置为0.
销毁二叉树的方法
static void bi_tree_free_subtree(BiTree *tree, BiTreeNode *node) {
if (node == NULL) {
return;
}
bi_tree_free_subtree(tree, node->children[BI_TREE_NODE_LEFT]);
bi_tree_free_subtree(tree, node->children[BI_TREE_NODE_RIGHT]);
free(node);
tree->num_nodes--;
}
void bi_tree_free(BiTree *tree) {
/* Destroy all nodes */
bi_tree_free_subtree(tree, tree->root_node);
/* Free back the main tree data structure */
free(tree);
}注意:
- static关键字的用法
- 只销毁了bi-tree.c中malloc出来的内存,BiTreeValue并没有销毁
- 遵循谁产生,谁销毁的原则
二叉树插入节点方法
BiTreeNode * bi_tree_insert(BiTree *tree, BiTreeValue value,
BiTreeNode *parent, BiTreeNodeSide side) {
BiTreeNode * newNode;
if((newNode = (BiTreeNode *)malloc(sizeof(BiTreeNode))) == NULL)
return NULL;
//初始化
newNode->children[BI_TREE_NODE_LEFT] = NULL;
newNode->children[BI_TREE_NODE_RIGHT] = NULL;
newNode->value = value;
newNode->parent = parent;
if(parent == NULL) {
//插入根节点
if(tree->root_node != NULL)
tree->root_node->parent = newNode;
newNode->children[side] = tree->root_node;
tree->root_node = newNode;
} else {
if(parent->children[side] != NULL)
parent->children[side]->parent = newNode;
newNode->children[side] = parent->children[side];
parent->children[side] = newNode;
}
tree->num_nodes++;
return newNode;
}应用于链表上的许多法则也可以应用到树上。当进行一次插入时，必须调用\(malloc\)创建一个节点。若要插入的位置上已经存在节点，则将该节点作为新节点的孩子节点。 注意, 新的节点产生后左右子树以及其他变量都要初始化.
二叉树删除节点方法
void bi_tree_remove_node(BiTree *tree, BiTreeNode *node) {
BiTreeNode *parent = node->parent;
if(parent != NULL) {
if(parent->children[BI_TREE_NODE_LEFT] == node) {
parent->children[BI_TREE_NODE_LEFT] = NULL;
} else if(parent->children[BI_TREE_NODE_RIGHT] == node) {
parent->children[BI_TREE_NODE_RIGHT] = NULL;
}
} else
tree->root_node = NULL;
bi_tree_free_subtree(tree, node);
}注意: 删除节点后一定要回收内存.
二叉树其他方法的实现
BiTreeNode *bi_tree_root_node(BiTree *tree) {
return tree->root_node;
}
BiTreeValue bi_tree_node_value(BiTreeNode *node) {
return node->value;
}
BiTreeNode *bi_tree_node_child(BiTreeNode *node, BiTreeNodeSide side) {
if (side == BI_TREE_NODE_LEFT || side == BI_TREE_NODE_RIGHT) {
return node->children[side];
} else {
return NULL;
}
}
BiTreeNode *bi_tree_node_parent(BiTreeNode *node) {
return node->parent;
}二叉树单元测试
void test_bi_tree_new(void) {
BiTree * tree = bi_tree_new();
int a = 10, b = 3;
BiTreeNode * rootNode = bi_tree_insert(tree, &a, NULL, BI_TREE_NODE_LEFT);
BiTreeNode * rightNode = bi_tree_insert(tree, &b, rootNode, BI_TREE_NODE_RIGHT);
assert(tree->num_nodes == 2);
assert(*(int *)(tree->root_node->value) == a);
assert(*(int *)(rightNode->value) == b);
bi_tree_remove_node(tree, rightNode);
assert(tree->num_nodes == 1);
bi_tree_free(tree);
}二叉树的遍历
二叉树的遍历是按照某种实现访问顺序访问二叉树中的每个节点，使每个节点被访问一次且仅被访问一次。
遍历是二叉树中经常要用到的一种操作。因为在实际应用问题中，常常需要按一定顺序对二叉树中的每个节点逐个进行访问，查找具有某一特定的节点，然后对这些满足条件的节点进行处理。
通过一次完整的遍历，可使二叉树中节点信息由非线性排列变为某种意义上的线性序列。也就是说，遍历操作使非线性结构线性化。
由二叉树的定义可知，一棵二叉树由根节点、根节点的左子树和根节点的右子树三部分组成。因此，只要依次遍历这三部分，就可以遍历整棵二叉树。若以D、L、R分别表示访问根节点、遍历根节点的左子树、遍历根节点的右子树，则二叉树的遍历方式有六种：DLR、LDR、LRD、DRL、RDL和RLD。如果限定先左右后，则只有前三种方式，即DRL（称为前序遍历），LDR（称为中序遍历）和LRD（称为后序遍历）。
二叉树的前序遍历
前序遍历的递归过程为：若二叉树为空，遍历结束，否则：
（1）访问根节点；
（2）前序遍历根节点的左子树；
（3）前序遍历根节点的右子树。
/* visit是访问节点的函数指针 */
void bitree_pre_order(BiTreeNode *node, BitreeValue (*visit)(BiTreeNode *)) {
if(node) {
(*visit)(node); /* 访问节点 */
/* 前序遍历左子树 */
if(bitree_pre_order(node->children[BITREE_NODE_LEFT], visit)) {
/* 前序遍历右子树 */
if(bitree_pre_order(node->children[BITREE_NODE_RIGHT], visit))
return 1;
return 0;
}
}
return 1;
}二叉树的中序遍历
中序遍历的递归过程为：若二叉树为空，遍历结束，否则：
（1）中序遍历根节点的左子树；
（2）访问根节点；
（3）中序遍历根节点的右子树。
int bitree_in_order(BiTreeNode *node, BitreeValue(*visit)(BiTreeNode *)) {
if(node) {
/* 中序遍历左子树 */
if(bitree_in_order(node->children[BITREE_NODE_LEFT], visit)) {
(*visit)(node); /* 访问节点 */
/* 中序遍历右子树 */
if(bitree_in_order(node->children[BITREE_NODE_RIGHT], visit))
return 1;
return 0;
}
return 0;
}
return 1;
}二叉树的后序遍历
后序遍历的递归过程为：若二叉树为空，遍历结束，否则：
（1）后序遍历根节点的左子树；
（2）后序遍历根节点的右子树；
（3）访问根节点。
void bitree_post_order(BiTreeNode *node, BitreeValue(*visit)(BiTreeNode *)) {
if(node) {
/* 后序遍历左子树 */
if(bitree_post_order(node->children[BITREE_NODE_LEFT], visit)) {
/* 后序遍历右子树 */
if(bitree_post_order(node->children[BITREE_NODE_RIGHT], visit)) {
(*visit)(node); /* 访问节点 */
return 1;
}
return 0;
}
return 0;
}
return 1;
}树的层次遍历
所谓树的层次遍历，是指从树的第一层（根节点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对节点逐个访问。
下面讨论层次遍历的算法。
由层次遍历的定义可以推知，在进行层次遍历时，对一层节点访问完后，再按照它们的访问程序对各个节点的左孩子和右孩子顺序访问，这样一层一层进行，先遇到的节点先访问，这与队列的操作原则比较吻合。因此在进行层次遍历时，可设置一个队列结构，遍历从树的根节点开始，首先将根节点指针入队列，然后从队头取出一个元素，每取一个元素，执行下面两个操作：
（1）访问该元素所指结点；
（2）若该元素所指结点的子节点非空，则该元素所指节点的子节点指针顺序入队。
此过程不断进行，当队列为空时，树的层次遍历结束。
二叉树的层次遍历
在下面的层次遍历算法中，二叉树以二叉链表存放，队列\(queue\)采用前面已经编写过的seqqueue结构方便实现。
void bitree_level_order(BiTreeNode *node, BitreeValue(*visit)(BiTreeNode *)) {
Queue *queue = new_queue();
if(node == NULL)
return;
while(!queue_is_empty(queue)) {
visit(queue->array[0]); /* 访问队首节点 */
queue_pop_head(queue);
if(queue->array[0]->children[BITREE_NODE_LEFT] != NULL)
/* 将队首节点的左孩子节点入队列 */
queue_push_tail(queue, queue->array[0]->children[BITREE_NODE_LEFT]);
if(queue->array[0]->children[BITREE_NODE_RIGHT] != NULL)
/* 将队首节点的右孩子节点入队列 */
queue_push_tail(queue, queue->array[0]->children[BITREE_NODE_RIGHT]);
queue_push_tail(queue, node);
}
}二叉树遍历的非递归实现
前面给出的二叉树前序、中序和后序三种遍历算法都是递归算法。当给出二叉树的链式存储结构以后，用具有递归功能的程序设计语言很方便就能实现上述算法。然而，并非所有程序设计语言都允许递归；另一方面，递归程序虽然简洁，但可读性一般不好，执行效率也不高。因此，就存在如何把一个递归算法转化为非递归算法的问题。
前序和中序遍历的非递归实现
在下面算法中，二叉树以二叉链表存放，栈\(stack\)采用前面已编写过的seqstack结构实现。
#include "seqstack.h"
void bitree_nrpre_order(BiTreeNode *node, BitreeValue(*visit)(BiTreeNode *)) {
ArrayList *stack = seqstack_new(MAXNODE);
BiTreeNode *p;
if(node == NULL)
return;
p = node;
while(!(p == NULL && seqstack_is_empty(stack))) {
while(p != NULL) {
(*visit)(p); /* 访问节点 */
seqstack_push(stack, p);
p = p->children[BITREE_NODE_LEFT];
}
if(seqstack_is_empty(stack)) /* 栈空时结束 */
return;
else {
p = (BiTreeNode *)seqstack_pop(stack);
p = p->children[BITREE_NODE_RIGHT];
}
}
}中序遍历的非递归算法的实现，只需将前序遍历的非递归算法中的(*visit)(p)移到seqstack_push(stack,p)和p=p->children[BITREE_NODE_LEFT]之间即可。
后序遍历的非递归实现要点
后序遍历与前序遍历和中序遍历不同，在后序遍历过程中，节点在第一次出栈后，还需再次入栈，也就是说，节点要入两次栈，出两次栈，而访问节点是在第二次出栈时访问。因此，为了区别同一个节点指针的两次出栈，设置一标志\(flag\)
当节点指针进、出栈时，其标志\(flag\)也同时进、出栈。因此，可将栈中元素的数据类型定义为指针和标志\(flag\)合并的结构体类型。定义如下：
typedef struct{
BiTreeNode *link;
int flag;
} stacktype;后序遍历的非递归实现
#include "seqstack.h"
void bitree_nrpost_order(BiTreeNode *node){
ArrayList *stack = seqstack_new(MAXNODE);
BiTreeNode *p;
stacktype *q;
int sign;
if(tree == NULL)
return;
while(!(p == NULL && seqstack_is_empty(stack))) {
if(p != NULL) { /* 节点第一次进栈 */
q = malloc(sizeof(stacktype));
q->link = p;
q->flag = 1;
seqstack_push(stack, q);
p = p->children[BITREE_NODE_LEFT];
}
else {
p = seqstack_peek(stack)->link;
sign = seqstack_peek(stack)->flag;
seqstack_pop(stack);
if(sign == 1) {
q = malloc(sizeof(stacktype));
q->link = p;
q->flag = 2;
seqstack_push(stack, q);
p = p->children[BITREE_NODE_RIGHT];
}
else {
(*visit)(p);
p = NULL;
}
}
}
}表达式树
最早提出遍历问题的是对存储在计算机中的表达式求值。例如：\((a+b×(c-d))-e/f\)。
表达式用树形来表示，如下图所示。运算符在树中放在非终端结点的位置上，操作数放在叶子结点处。
三种表达式
当我们对此二叉树进行先序、中序和后序遍历后，便可得到表达式的前缀、中缀和后缀书写形式：
前缀：\(-+a*b-cd/ef\)
中缀：\(a+b*c-d-e/f\)
后缀：\(abcd-*+ef/-\)
其中，中缀形式是算术表达式的通常形式，只是没有括号。在计算机内，使用后缀表达式易于求值。
表达式计算的需求
需求：输入一个算术表达式，判断该表达式是否合法，若不合法，给出错误信息；若合法，则输出合法表达式的表达式树。
表达式不合法的情况：①左右括号不匹配；②运算符两旁无参与运算的变量或数。
算法思路
例子: \((a+b×(c-d))-e/f\)
- 处理时，首先找到运算级别最低的运算符“+”或者“-”作为根结点
- 继而确定该根结点的左、右子树结点在表达式串中的范围，例如上面表达式中是\(a\)和\((b-c)/d\)
- 再在对应的范围内寻找运算级别最低的运算符作为子树的根结点，直到范围内无运算符，则剩余的变量或数为表达式树的叶子
测试先行
void test_expression_tree(void) {
char exp1[] = "2*3";
char exp2[] = "2+3/1.5-10*3+40";
char exp3[] = "-2+3/1.5-(10*3)+40";
char exp4[] = "-(3+4*5)+1*2.5";
double rst = 0;
doExpressionCal(exp1, &rst);
assert(rst == 6.0);
doExpressionCal(exp2, &rst);
assert(rst == 14.0);
doExpressionCal(exp3, &rst);
assert(rst == 10.0);
doExpressionCal(exp4, &rst);
assert(rst == -20.5);
}注意: 测试要尽可能充分, 把能想到的都测一遍.
表达式计算的方法
int doExpressionCal(char * exp, double * rst) {
int l = strlen(exp);
printf("Creating expression tree...\n");
BiTree * tree = bi_tree_new();
create_expression_tree(tree, tree->root_node, BI_TREE_NODE_LEFT, exp, l);
printf("Print tree...\n");
in_order_print(tree->root_node);
printf("\n");
calculate(tree->root_node, rst);
printf("Destroying expression value...\n");
post_order_free(tree->root_node);
printf("Destroying expression tree...\n");
bi_tree_free(tree);
}两个关键的方法:
- create_expression_tree
- calculate
形成表达式树方法实现
int create_expression_tree(BiTree* tree, BiTreeNode* parent, BiTreeNodeSide side, char * p, int l) {
// lnum记录"("的未成对个数；
// rpst1/rpst2记录表达式中("*"、"/")/("+"、"-")的位置;
// pn记录操作数中"."的个数,以判断输入操作数是否合法
int i = 0, lnum = 0, rpst1 = -1, rpst2 = -1, pn = 0;
if(l == 0)
return 1;
//判断表达式是否正确
if(*p=='+' || *p=='*' || *p=='/' || *p=='.' || *p==')') {
printf("Wrong expression：not start with number or left bracket!\n");
return 0;
}
if(!(*(p+l-1)==')' || *(p+l-1)>='0' && *(p+l-1)<='9')) {
printf("Wrong expression：not end with number or right bracket!\n");
return 0;
}
if(*p=='(')
lnum++;
for(i = 1; i < l ; i++) {
if(*(p+i)=='.') {
if(!(*(p+i-1) >= '0' && *(p+i-1) <= '9')) {
printf("Wrong expression: no number following dot(.)!\n");
return 0;
}
} else if(*(p+i)=='*' || *(p+i)=='/') {
if(!(*(p+i-1)>='0'&&*(p+i-1)<='9'||*(p+i-1)==')')) {
printf("Wrong expression: not number or right bracket on the left of (*)!\n");
return 0;
}
if(lnum == 0)
rpst1 = i;
} else if(*(p+i) == '(') {
if(*(p+i-1)=='+'||*(p+i-1)=='-'||*(p+i-1)=='*'||*(p+i-1)=='/'||*(p+i-1)=='(')
lnum++;
else {
printf("Wrong expression: unexpected char appears on the left of left bracket!\n");
return 0;
}
} else if(*(p+i)==')') {
if(*(p+i-1)==')' || *(p+i-1)>='0' && *(p+i-1)<='9')
lnum--;
else {
printf("Wrong expression: unexpected char appears on the left of right bracket!\n");
return 0;
}
if(lnum < 0) {
printf("Wrong expression: left bracket and right bracket not equal!\n");
return 0;
}
} else if(*(p+i) == '+' || *(p+i) == '-') {
if(*(p+i)=='+' && !(*(p+i-1)>='0' && *(p+i-1)<='9' || *(p+i-1)==')')) {
printf("Wrong expression: unexpected char appears on the left of (+)!\n");
return 0;
} else if(*(p+i)=='-'&&!(*(p+i-1)>='0'&&*(p+i-1)<='9'||*(p+i-1)==')'||*(p+i-1)=='(')) {
printf("Wrong expression: unexpected char appears on the left of (-)!\n");
return 0;
}
if(lnum == 0)
rpst2 = i;
}
}
//"("、")"未能完全配对,表达式输入不合法
if(lnum != 0) {
printf("Wrong expression： left bracket and right bracket not equal!\n");
return 0;
}
if(rpst2 > -1) {
char * value = (char *)malloc(2 * sizeof(char));
strncpy(value, p + rpst2, 1);
*(value + 1) = '\0';
BiTreeNode * newNode = bi_tree_insert(tree, value, parent, side);
if(create_expression_tree(tree, newNode, BI_TREE_NODE_LEFT, p, rpst2))
if(create_expression_tree(tree, newNode, BI_TREE_NODE_RIGHT, p+rpst2+1, l-rpst2-1))
return 1;
return 0;
}
//此时表明表达式或者是一个数字，或是表达式整体被一对括弧括起来
if(rpst1 < 0) {
if(*p=='(') { //此时表达式整体被一对括弧括起来
if(create_expression_tree(tree, parent, side, p+1, l-2))
return 1;
else
return 0;
} else {
if(*(p+1)!='(') {//此时表达式一定是一个数字
for(i = 0; i < l; i++) {
if(*(p+i)=='.')
pn++;
if(pn > 1) {
printf("Wrong expression: more than one dot(.) found in a number!\n");
return 0;
}
}
char * value = (char *)malloc((l + 1) * sizeof(char));
strncpy(value, p, l);
*(value+l) = '\0';
bi_tree_insert(tree, value, parent, side);
return 1;
} else {//此时表达式首一定是操作符"-"，其余部分被一对括弧括起来
char * value = (char *)malloc(2 * sizeof(char));
strncpy(value, p, 1);
*(value + 1) = '\0';
BiTreeNode * newNode = bi_tree_insert(tree, value, parent, side);
if(create_expression_tree(tree, newNode, BI_TREE_NODE_RIGHT, p + 2, l - 3))
return 1;
else
return 0;
}
}
} else {//此时表明表达式为几个因子想乘或相除而组成的
char * value = (char *)malloc(2 * sizeof(char));
strncpy(value, p + rpst1, 1);
*(value + 1) = '\0';
BiTreeNode * newNode = bi_tree_insert(tree, value, parent, side);
if(create_expression_tree(tree, newNode, BI_TREE_NODE_LEFT, p, rpst1))
if(create_expression_tree(tree, newNode, BI_TREE_NODE_RIGHT, p+rpst1+1, l-rpst1-1))
return 1;
return 0;
}
}计算表达方法实现
int calculate(BiTreeNode * node, double* rst) {
double l = 0, r = 0;//l、r分别存放左右子树所代表的字表达式的值
if(!node) {
*rst = 0;
return 1;
}
if(node->children[BI_TREE_NODE_LEFT] == NULL && node->children[BI_TREE_NODE_RIGHT] == NULL) {
*rst = atof(node->value);
return 1;
} else {
//先计算左子树和右子树
if(calculate(node->children[BI_TREE_NODE_LEFT], &l))
if(calculate(node->children[BI_TREE_NODE_RIGHT], &r)) {
switch(((char *)node->value)[0]) {
case '+' :
*rst = l + r;
break;
case '-' :
*rst = l - r;
break;
case '*' :
*rst = l*r;
break;
case '/' :
if(r == 0) {
//告警,除数为0
printf("Divided by 0!\n");
return 0;
} else {
*rst = l/r;
break;
}
default :
return 0;
}
return 1;
}
return 0;
}
}其他需要注意的地方
int post_order_free(BiTreeNode * node) {
if(node) {
if(post_order_free(node->children[BI_TREE_NODE_LEFT])) {
if(post_order_free(node->children[BI_TREE_NODE_RIGHT])) {
free(node->value);
return 1;
}
return 0;
}
return 0;
}
return 1;
}注意: 要把create_expression_tree方法中malloc的内存回收.
哈夫曼树(Huffman)
定义
路径、路径长度：如果有一棵树的一串结点 \(n_1,n_2,\ldots,n_k\) ， 结点\(n_i\)是\(n_{i+1}\)的父结点 \(（1≤i<k）\) ,就把\(n_1,n_2,\ldots,n_k\)称为一条由\(n_1\)至\(n_k\)的路径，这条路径的长度是 \(k-1\) 。
二叉树的路径长度PL：从树根到每一个叶结点的路径长度之和。
有的书上：\(PL= 1+1+2+2+2+2=10\)
本书：\(PL= 2+2+2+2=8\)
带权路径长度
在许多应用中，常常将树中结点赋予一个有某种意义的实数，称为该结点的权。
结点的带权路径长度：是该结点到树根之间的路径长度与结点上权的乘积。
二叉树的带权路径长度：树中所有叶子结点的带权路径长度\(ω_kl_k\)之和，记作： \[wpl=\sum_{k=1}^{n}w_kl_k\]
其中：
\(w_k\)为权值
\(l_k\)为结点到根的路径长度
\(n\)为叶子结点数
哈夫曼树的定义
哈夫曼树:又称最优二叉树，是指对于一组带有确定权值的叶结点构造的具有最小带权路径长度的二叉树。
哈夫曼树构造算法
由相同权值的一组叶子结点所构成的二叉树有不同的形态和不同的带权路径长度，那么如何找到带权路径长度最小的二叉树（即哈夫曼树）呢？
根据哈夫曼树的定义，一棵二叉树要使其WPL值最小，必须使权值越大的叶结点越靠近根结点，而权值越小的叶结点越远离根结点。
哈夫曼（Huffman）依据这一特点提出了一种方法，这种方法的基本思想是：
由给定的\(n\)个权值{\(w_1，w_2，\ldots,w_n\)}
- 构造n棵只有一个叶结点的二叉树，得到一个二叉树的集合 \(F＝{T_1，T_2，\ldots，T_n}\);
- 在F中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树，根结点的权值为其左、右子树根结点权值之和;
- 在集合F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合F中;
- 重复（2）（3）两步，当F中只剩下一棵二叉树时，这棵二叉树便是所要建立的哈夫曼树。
哈夫曼树构造算法图示一
哈夫曼树构造算法图示二
Huffman编码
Huffman编码：数据通信用的二进制编码
思想：根据字符出现频率编码，使电文总长最短
编码：根据字符出现频率构造Huffman树，然后将树中结点引向其左孩子的分支标“0”，引向其右孩子的分支标“1”；每个字符的编码即为从根到每个叶子的路径上得到的0、1序列
哈夫曼树应用举例
例：有一份电文中共使用5个字符：a、b、c、d、e，它们的出现频率依次为4、7、5、2、9，试画出对应的哈夫曼树(请按左子树根结点的权小于等于右子树根结点的权的次序构造)，并求出每个字符的哈夫曼编码。
编码算法的基本思想
从叶子 i 出发，利用双亲地址找到双亲结点 p ，再利用p 的lchild和rchild指针域判断 i 是 p 的左孩子还是右孩子，然后决定分配代码是“0”还是“1”，然后以 p 为出发点继续向上回溯，直到根结点为止。
上机内容
使用二叉树完成表达式的存储和计算，要求
- 能够实现含有（）、+、-、*、/等运算符的实数表达式计算功能
- 能够处理小数和负数
- 能够处理求余运算符（%）
- 能够处理乘方（^）
- 能够处理exp,sin,cos,tan,ctan等常见函数
- 能够打印包含括号的中缀表达式
- 实现变量功能,使表达式树叶节点既可以时数字也可以是变量,在计算前给变量赋值（选做）