[数据结构]——二叉树(Binary Tree)、二叉搜索树(Binary Search Tree)及其衍生算法

时间:2022-11-13 19:47:38

二叉树(Binary Tree)是最简单的树形数据结构,然而却十分精妙。其衍生出各种算法,以致于占据了数据结构的半壁*。STL中大名顶顶的关联容器——集合(set)、映射(map)便是使用二叉树实现。由于篇幅有限,此处仅作一般介绍(如果想要完全了解二叉树以及其衍生出的各种算法,恐怕要写8~10篇)。

1)二叉树(Binary Tree)

顾名思义,就是一个节点分出两个节点,称其为左右子节点;每个子节点又可以分出两个子节点,这样递归分叉,其形状很像一颗倒着的树。二叉树限制了每个节点最多有两个子节点,没有子节点的节点称为叶子。二叉树引导出很多名词概念,这里先不做系统介绍,遇到时再结合例子一一说明。如下一个二叉树:

/*   A simple binary tree
* A ---------> A is root node
* / \
* / \
* B C
* / / \
* / / \
* D E F ---> leaves: D, E, F
*
* (1) ---> Height: 3
* */

其中节点B只有一个子节点D;D, E, F没有子节点,被称为叶子。对于节点C来说,其分出两子节点,所以C的出度为2;同理,C有且只有一个父节点,所以其入度为1。出度、入度的概念来源于图(Graph,一种更加高级复杂的数据结构),当然,也可以应用于二叉树(二叉树或者说树形数据结构也是一类特殊的图)。显然,二叉树的根节点入度为0,叶子节点出度为0。

如何衡量一颗二叉树?比如大小、节点稠密等。与楼房一样,一般会对二叉树分层,并且通常将根节点视为第一层。接下来B与C同属第二层,D, E, F同属第三层。注意,并不是所有的叶子都在同一层。通常将二叉树节点的最高层数作为其树的高度,上例中二叉树高度为3。显然,一个二叉树的节点总数必然小于2的树高幂,转化成公式表示为:N<2^H,其中N为节点总数,H为二叉树高度;对于第k层,最多有2^(k-1)个节点。更加细化的分类,如下:

完全二叉树:除了最高层以外,其余层节点个数都达到最大值,并且最高层节点都优先集中在最左边

满二叉树:除了最高层有叶子节点,其余层无叶子,并且非叶子节点都有2个子节点。

如下例:

/*  Complete Binary Tree (CBT) and Full Binary Tree (FBT)
* A A A
* / \ / \ / \
* / \ / \ / \
* B C B C B C
* / \ / \ / \ / \
* / \ / \ / \ / \
* D E D E F G D E
*
* (2) (3) (4)
* CBT FBT not CBT
* */

其中(2)就是一个完全二叉树;(3)是一个满二叉树;而(1)和(4)不属于这两者,(虽然(4)是(2)的一种镜像二叉树)。易知,满二叉树必然是一个完全二叉树,反之则不然。从节点数量上看,满二叉树的第k层有2^(k-1)个节点,所以其总节点数为2^H - 1;完全二叉树除了最后一层外,第k层节点有2^(k-1)个节点,最后一层最多有2^(H-1)个节点。

其实,关于完全二叉树的定义有多种,然而不管怎样定义,其实质是一样的,关键在于怎样理解。如果完全二叉树除去最后一层,则成为一个满二叉树。所谓的“最后一层节点优先集中在左边”,用语言很难解释,但是结合上例的(2)和(4)可以很好理解。为什么要这样定义呢?这是因为这种完全二叉树的效率非常高,并且完全二叉树绝大多数情况使用数组存储,即无序堆(Heap)!可以参见关于堆的博文http://www.cnblogs.com/eudiwffe/p/6202111.html为了充分利用数组的存储空间,优先将叶子安排在最左边,以保证该数组每个存储单元都被利用(如果是(4)的情况,则该数组会有部分空间浪费)。这就是为什么要要求“最后一层优先集中在最左边”。

 2)二叉树的构建和遍历

数据结构和算法,最终要落实在代码上,首先给出一般C风格的二叉树节点定义,其中val在同一颗树中唯一

// A simple binary tree node define
typedef struct __TreeNode
{
int val;
struct __TreeNode *left, *right;
}TreeNode;

很简单,看着很像双链表节点的定义,如果抛开字段名称,其实质完全跟双链表节点结构一样。事实上,有很多情况下需要将二叉树就地转换成一个双链表,甚至是单链表。如何构建一个二叉树?很抱歉,这个占据数据结构与算法半壁*的二叉树,竟然没有一个标准的构建方法!因为二叉树使用太过广泛,针对不同应用有不同的构建方法,如果仅仅将一个节点插入(或删除)到二叉树中,这又太过简单,简单的与链表插入(或删除)一样。故本文不提供构建方法。

对于给定的一颗二叉树,如何遍历呢?有四种常见方法。

中序遍历:即左-根-右遍历,对于给定的二叉树根,寻找其左子树;对于其左子树的根,再去寻找其左子树;递归遍历,直到寻找最左边的节点i,其必然为叶子,然后遍历i的父节点,再遍历i的兄弟节点。随着递归的逐渐出栈,最终完成遍历。例如(1)中的遍历结果为:D->B->A->E->C->F

先序遍历:即根-左-右遍历,不再详述。例如(1)中的遍历结果:A->B->D->C->E->F

后序遍历:即左-右-根遍历,不再详述。例如(1)中的遍历结果:D->B->E->F->C->A

层序遍历:即从第一层开始,逐层遍历,每层遍历按照从左到右遍历。例如(1)中的遍历结果:A->B->C->D->E->F

很明显,先序遍历的第一个节点必然是树的根节点;后序遍历的最后一个节点也必然是树的根节点。层序遍历更加符合人对二叉树的树形结构的遍历顺序。

下面给出一般的实现代码供参考:

// root is in middle order travel, (1):D->B->A->E->C->F
void inorder(TreeNode *root)
{
if (root == NULL) return;
inorder(root->left);
printf("%d ",root->val); // visit
inorder(root->right);
}
// previous visit root order travel, (1):A->B->D->C->E->F
void preorder(TreeNode *root)
{
if (root == NULL) return;
printf("%d ",root->val); // visit
preorder(root->left);
preorder(root)
}
// post vist root order travel, (1):D->B->E->F->C->A
void postorder(TreeNode *root)
{
if (root == NULL) return;
postorder(root->left);
postorder(root->right);
printf("%d ",root->val); // visit
}

看着很简单感觉不太对,毋庸置疑,事实上就是这么简单。此处仅给出递归版本,虽然递归间接用到了栈,但是即便使用循环版本实现,其仍然需要辅助空间存储。为什么在实现堆的代码中,用的是循环而不是递归?这就是因为堆的形象化是一个完全二叉树,并且用数组存储,可见完全二叉树的效率如此之高。对于层序遍历,就需要使用辅助的存储空间,一般使用队列(queue),因为其要求每层的顺序要从左到右。下面使用STL中queue进行实现,关于队列的介绍,请自行补充。

// level order travel, (1):A->B->C->D->E->F
void levelorder(TreeNode *root)
{
if(root==NULL) return;
queue<TreeNode*> q;
for(q.push(root); q.size(); q.pop()){
TreeNode *r = q.front();
printf("%d ",r->val); // visit
if (r->left) q.push(r->left);
if (r->right) q.push(r->right);
}
}

上面是一种层序遍历,但并没有对每层进行分割,换言之,并不知道当前遍历的节点属于哪一层。如需实现,只需要两个队列交替遍历,每个队列遍历完就是一层的结束,感兴趣的可以自行写出。

其中,前面三种遍历最为常见,先序遍历是二叉树的深度优先遍历(Depth First Search,DFS),使用最广泛。层序遍历是二叉树的广度优先遍历(Breadth First Search,BFS)。

3)二叉树的序列化(serialize)和反序列化(deserialize)

简单讲,序列化就是将结构化数据转化成可顺序传输的数据流;反序列化就是将顺序数据流还原成原来的数据结构。

前面几种遍历方法,虽然都可以将二叉树转换成顺序的数据流,但还不能称作序列化,因为没有办法还原二叉树结构。以(1)为例,其常见四种遍历方法得到的数据流为:

/*  A simple binary tree four typical traversals
* A
* / \ in order : D->B->A->E->C->F
* / \ pre order : A->B->D->C->E->F
* B C post order : D->B->E->F->C->A
* / / \ level order: A->B->C->D->E->F
* / / \
* D E F
*
* (1)
* */

单独使用无法将其还原成二叉树。但是,仔细观察发现,先序遍历的第一个节点A为根节点;后序遍历的最后一个节点A也是根节点。如果同时知道一个二叉树的先序和后序遍历顺序,是否可以还原树呢?很抱歉,虽然两种遍历的方法不一样,但其只能确定根节点的位置,其他节点无法确定。那么,如果使用中序+先序遍历结果,是否可行呢?让我们试试。

根据先序遍历知道第一个节点A为根节点,接下来“B->D->C->E->F”是左右节点的顺序,虽然目前还无法判断到底哪个是左,哪个是右;

前面已知,中序遍历以根节点为分隔,左边是左子树,右边是右子树,于是在中序中找到A的位置,以此分隔,左部分“D->B”是左子树,右部分“E->C->F”是右子树;

请注意,对于任意一个节点来说,都是某个子树的根节点,即便是叶子节点,它也是一个空二叉树的根节点!由此引出,先序遍历的每个节点都曾充当父节点(某子树的根节点)。

于是,对于剩下的先序遍历数据流“B->D->C->E->F”来说,B也是剩下的某子树的根节点,究竟是哪个子树呢?显然是左子树,因为先序遍历的顺序就是“根-左-右”。因此,在左子树“D->B”中找到B,其为左子树的根;于是将“D->B”分成左子树“D”和右子树“”(空)。根据递归的出栈,接下来处理先序遍历中的“D->C->E->F”,紧接着是“C->E->F”...最终,完成二叉树的还原。部分步骤示意图:

// Using In order and Pre order to deserialize
/*
* A* A A A
* / \ ====> / \ / \ / \
* / \ / \ / \ / \
* D-B E-C-F B* E-C-F B E-C-F B C*
* / \ / / / \
* / \ / / / \
* D NULL D* D E F
* root root root root
* | | | |
* IN: D-B-A-E-C-F D-B D E-C-F
* PRE:A-B-D-C-E-F B-D-C-E-F D-C-E-F C-E-F
* | | | |
* root root root root
* */

每次根据先序遍历结果确定当前的根节点(用*标记),然后在中序遍历结果中寻找该节点,并以此为分割点,分成左右子树;反复执行,直到先序遍历结束,二叉树还原完毕。下面给出C风格的代码,仅供参考:

// Using In order and Pre order to deserialize
TreeNode *deserialize(int pre[], int in[], int n, int begin, int end)
{
static int id = 0; // current position in PRE order
if (begin==0 && end==n) id=0; // reset id
TreeNode *r = (TreeNode*)malloc(sizeof(TreeNode));
int pos; // current root position in IN order
for (pos=begin; pos<end && in[pos]!=pre[id]; ++pos);
if (in[pos]!=pre[id]) exit(-1); // preorder or inorder is error
r->val = pre[id++];
r->left = deserialize(pre,in,n,begin,pos);
r->right= deserialize(pre,in,n,pos+1,end);
return r;
}

其中pre[]为先序遍历结果,in[]为中序遍历结果,此处假设节点的值(val)为唯一(对于不唯一的,可以增加关键字字段)。n为节点总数,也即为数组的长度;start和end表示寻找中序遍历的区间范围[start,end)。如果给定的pre[]和in[]绝对正确,那么第9行的错误处理将不会执行。对于一棵N节点的二叉树,直接调用deserialize(pre,in,n,0,n)则可还原该二叉树。整个逆序列化的过程,实际上是“先序遍历”的过程,不妨看看10~12行代码。

同理,使用中序+后序也可还原二叉树,这里不再详述。

不妨算法其时间复杂度,对于先序数据流,其使用了静态的id作为遍历下标,故为O(n);但是对于中序遍历数据流,其根据[start,end)区间进行遍历寻找,为O(nlogn)。感兴趣的不妨尝试改进层序遍历,使其达到序列化和反序列化的要求(注意分层和空节点)。

 4)二叉搜索树(Binary Search Tree)

之所以称为二叉搜索树,是因为这种二叉树能大幅度提高搜索效率。如果一个二叉树满足:对于任意一个节点,其值不小于左子树的任何节点,且不大于右子树的任何节点(反之亦可),则为二叉搜索树。如果按照中序遍历,其遍历结果是一个有序序列。因此,二叉搜索树又称为二叉排序树。不同于最大堆(或最小堆),其只要求当前节点与当前节点的左右子节点满足一定关系。下面以非降序二叉搜索树为例。

// Asuming each node value is not equal
/* A simple binary search tree
* 6 6
* / \ / \
* / \ / \
* 3 8 3 8
* / / \ / / \
* / / \ / / \
* 2 7 9 2 4* 9
*
* (A) BST (B) Not BST
* */

其中(A)为二叉搜索树,(B)不是。因为根节点6小于右子树中的节点4。

构建二叉搜索树的过程,与堆的构建类似,即逐渐向二叉搜索树种添加一个节点。每次新添加一个节点,直接寻找到对应的插入点,使其满足二叉搜索树的性质。下面是一种简易的构建过程:

// Initialize a bst
TreeNode *bst_init(int arr[], int n)
{
if (n<1) return NULL;
TreeNode *r = (TreeNode*)malloc(sizeof(TreeNode));
r->val = arr[0]; // ensure bst_append will not update root address
r->left = r->right = NULL;
for (; --n; bst_append(r,arr[n]));
return r;
}

对于给定的数组数据,如果仅有一个元素,则直接构造一个节点,将其返回;否则,逐渐遍历该数组,将其元素插入到二叉树中(不要忘记将无子节点的指针置为空),其中bst_append将元素插入的二叉查找树中。为什么对于单独一个元素要特殊处理,而不是所有节点都通过bst_append插入呢?显然,当插入第一个元素时,此时二叉树根节点为空,直接插入必然修改根节点的地址。当然可以通过返回值获取插入后二叉树的根节点指针,但这样仅仅针对1/n的情况,却每次(共N次)都重新对根节点赋值,牺牲太多性能。当然也可以将bst_append传参列表声明为二级指针,这里为了追求简洁,故不使用。

当给出插入节点的代码时,你会发现二叉搜索树的构建跟堆的构建思路有异曲同工之妙,并且插入方法与先序遍历十分相似:

// Append a node to bst, return add count
int bst_append(TreeNode *r, int val)
{
// find insertion position
for (; r && r->val!=val;){
if (r->val < val && r->right) r=r->right;
else if (r->val > val && r->left) r=r->left;
else break;
}
if (r==NULL || r->val==val) return 0;
TreeNode *tn = (TreeNode*)malloc(sizeof(TreeNode));
tn->left = tn->right = NULLL;
tn->val = val;
if (r->val < val) r->right = tn;
else r->left = tn;
return 1;
}

通常情况,认为二叉树的节点值为唯一,即不存在新插入的值与已有节点值相同的情况,正如一个集合中不存在相同的两个元素。虽然STL也提供multiset与multimap以便允许重复元素,但其增加了新的字段count用于存储每个值val所包含的节点个数。易知,对于set而言,其每个节点的count值均为1。注意,对于同一个元素集合,其数组中的顺序不同,生成的二叉查找树也不同。其中,二叉搜索树的插入时间复杂度为O(logn),构建二叉搜索树的总时间复杂度为O(nlogn)。寻找插入位置的过程,实际上类似于二分查找。

既然叫二叉搜索树,那么如何高效的查找一个元素是否在该二叉搜索树呢?与插入类似,同样使用先序遍历的结构:

// Find value in bst, return node address
TreeNode *bst_find(TreeNode *r, int val)
{
for (; r && r->val!=val;){
if (r->val < val) r=r->right;
else if (r->val > val) r=r->left;
}
return r;
}

如果找到了,直接返回该节点指针,否则返回空指针。二叉搜索树对于元素的查找效率与二分查找一样,都为O(logn),只不过前者使用二叉树链式存储,而二分查找使用顺序的数组存储,两者各有优劣。

很多时候,常常需要删除其中的某些元素,对于二分查找来说,其使用的是有序数组存储,对于数据的插入和删除效率较低,均为O(n);而二叉搜索树却有着O(logn)的快速,那么如何删除节点?与堆不同,二叉搜索树使用链式存储,需要注意内存释放,避免其父节点、左右子节点意外分离于原二叉搜索树。因此需要根据待删除节点所处位置,进行分类处理。

在这之前,首先引入一个概念——前驱节点(Precursor Node)。所谓前驱,即按照某种遍历方法,节点前的一个节点为该节点的前驱节点。以(1)为例,其中序遍历为“D->B->A->E->C->F”,那么对于节点A来说,其前驱节点为B;对于节点E来说,A是其前驱节点(下面不作特殊说明,均以中序遍历顺序情况)。与之相反,后继节点则为按照某种遍历方法该节点的下一个节点。即,A是B的后继节点。对于二叉搜索树来讲,如果使用中序遍历,其遍历结果是有序的,即:任意一个节点的前驱节点是满足不大于该节点的最大节点;任意一个节点的后继节点是满足不小于该节点的最小节点。以(A)为例,其中序遍历为“2-3-6-7-8-9”。

对于二叉搜索树的节点删除,一般可分为三种情况:待删除的节点有两个子节点,待删除的节点有一个子节点,待删除的节点无子节点:

/* Erase node from a bst - sketch, i' is special for erase 6 (i)
* 6 d=6,(3) f=6 6 d=6,(5)
* / \ / \ / \ / \ / \
* / \ / \ / \ / \ / \
* 3 8 p=3 8 d=3 8 3 f=8 f=3 8
* / / \ / / \ / / \ / / \ / \ / \
* / / \ / / \ / / \ / / \ / \ / \
* 2 7 9 2 7 9 2 7 9 2 d=7 9 2 p=5 7 9
* /
* BST (i) (ii) (iii) / (i')
* erase 6 erase 3 erase 7 4
* */

(i) 待删除的节点有两个子节点:以删除6为例,为了便于说明,这里将待删除节点称为d=6,其前驱节点为p=3。按照(i)图示方法,可以将其前驱节点p的值替换待删除节点d,并删除前驱节点。注意,如果前驱节点p仍有子节点(子树),则其必然是左节点(左子树),为什么?请自行思考。这里将前驱节点p的父节点称为f,此时的f正好是d,但不是所有情况都是。对于(i')图示,前驱节点p=5的父节点为f=3,当删除d=6时,可以将f的右子节点指向p的左子节点;对于(i),由于f与d相同,所以可以直接将d的左子节点指向p的左子节点。

(ii)待删除的节点有一个子节点:以删除3为例,由于只有一个子节点,所以可将d节点的子节点继承d,此时需要将d的父节点f=6的子节点指向继承节点。并且需要区分当前删除节点d是父节点f的左子节点还是右子节点,以及d节点的子节点是左子还是右子。图示d为f的左子节点,d有左子节点,所以将f的左子节点指向d的左子节点。

(iii)待删除的节点无子节点:以删除7为例,很简单,将其直接删除,并且将其父节点f的子节点指向空。同样需要判断d是f的左子还是右子。

请注意,对于单根二叉树,即一个二叉搜索树有且只有一个节点,此时需要删除该根节点,那么删除根节点后,二叉树为空。与bst_append类似,如果为空,需要通过返回值回传根节点为空,或者通过传参列表声明二级节点指针。为了简化代码,此处不对其进行处理,由调用删除节点处自行处理。

下面是一种实现代码,其中返回值表示删除的节点个数,对于单根二叉树返回-1,告诉调用者,并由调用者自行处理:

int bst_erase(TreeNode *r, int val)
{
TreeNode *f, *p, *d;
// f is father node
// p is precursor node
// d is to be deleted node
for (f=NULL,d=r; d && d->val!=val;){
f = d;
if (d->val < val) d=d->right;
else d=d->left;
}
if (d==NULL) return 0; // cannot find erase node if (d->left && d->right){ // deletion has two children
// find deletion node d's precursor
for (f=d,p=d->left; p->right; f=p, p=p->right);
d->val = p->val; // replace deletion val by precursor
if (f==d) d->left = p->left;// case (i)
else f->right = p->left; // case (i')
}
else if (d->left==NULL && d->right==NULL){
if (d==r) return -1; // deletion is single root, this will
// replace root address to NULL, please
// deal this at calling procedure.
// deletion is leaf
if (f->left == d) f->left=NULL;
else if (f->right == d) f->right=NULL;
free(d);
}
else { // deletion has single child node or branch
p = (d->left ? d->left : d->right);
d->val = p->val;
d->left = p->left;
d->right = p->right;
free(p);
}
return 1; // return erase node count
}

到此为止,二叉搜索树介绍完毕。显然,二叉搜索树的删除要复杂的多。实际上,二叉搜索树才仅仅是二叉树的一个衍生树,后续的平衡二叉搜索树、AVL树以及红黑树等,才是实际使用最为广泛的。由于篇幅限制,二叉树及其衍生算法介绍完毕。

注:本文涉及的源码:binary tree : https://git.oschina.net/eudiwffe/codingstudy/blob/master/src/binarytree/binarytree.c

binary tree deserialize : https://git.oschina.net/eudiwffe/codingstudy/blob/master/src/binarytree/btdeserialize.c

binary search tree : https://git.oschina.net/eudiwffe/codingstudy/blob/master/src/binarytree/bst.c

删除二叉搜索树中的节点:LintCodehttps://git.oschina.net/eudiwffe/lintcode/blob/master/C++/remove-node-in-binary-search-tree.cpp