数据布局进修（C++）之二叉树
副标题#e#
树
因为现实世界中存在这“树”这种布局——族谱、品级制度、目次分类等等，而为了研究这类问题，必需可以或许将树储存，而如何储存将取决于所需要的操纵。这里有个问题，是否答允存在空树。有些书认为树都长短空的，因为树暗示的是一种现实布局，而0不是自然数；我用过的教科书都是说可以有空树，虽然是为了和二叉树统一。这个没有什么原则上的不同，横竖就是一种习惯。
二叉树
二叉树可以说是人们假想的一个模子，因此，答允有空的二叉树是无争议的。二叉树是有序的，左边有一个孩子和右边有一个的二叉树是差异的两棵树。做这个划定，是因为人们赋予了左孩子和右孩子差异的意义，在二叉树的各类应用中，你将会清楚的看到。下面只讲授链式布局。看各类讲数据布局的书，你会发明一个有趣的现象：在二叉树这里，根基操纵有计较树高、各类遍历，就是没有插入、删除——那树是怎么成立起来的？其实这很好领略，对付非线性的树布局，插入删除操纵不在必然的法例划定下，是毫无意义的。因此，只有在详细的应用中，才会有插入删除操纵。
节点布局
数据域、左指针、右指针必定是必需的。除非很罕用到节点的双亲，可能是资源告急，发起附加一个双亲指针，这将会给许多算法带来利便，尤其是在这个“空间换时间”的时代。
template <class T>
struct BTNode
{
BTNode(T data = T(), BTNode<T>* left = NULL, BTNode<T>* right = NULL, BTNode<T>* parent = NULL)
: data(data), left(left), right(right), parent(parent) {}
BTNode<T> *left, *right, *parent;
T data;
};
根基的二叉树类
#p#副标题#e#
template <class T>
class BTree
{
public:
BTree(BTNode<T> *root = NULL) : root(root) {}
~BTree() { MakeEmpty(); }
void MakeEmpty() { destroy(root); root = NULL; }
protected:
BTNode<T> *root；
private:
void destroy(BTNode<T>* p)
{
if (p)
{
destroy(p->left);
destroy(p->right);
delete p;
}
}
}
二叉树的遍历
根基上有4种遍历要领，先、中、后根，逐层。当初我对这个很疑惑，搞这么多干什么？到了后头才大白，这是差异的应用需要的。譬喻，判定两个二叉树是否相等，只要子树根节点差异，那么就不等，显然这时要用先序遍历；而删除二叉树，必需先删除阁下子树，然后才气删除根节点，这时就要用后序遍历。
实际上，搞这么多遍历要领，基础原因是在内存中储存的树长短线性布局。对付用数组储存的二叉树，这些款式繁多的要领都是没有须要的。操作C++的封装和重载特性，这些遍历要领能很清晰的表达。
1. 前序遍历
public:
void PreOrder(void (*visit)(T &data) = print) { PreOrder(root, visit); }
private:
void PreOrder(BTNode<T>* p, void (*visit)(T &data))
{
if (p){ visit(p->data); PreOrder(p->left, visit); PreOrder(p->right, visit); }
}
2. 中序遍历
public:
void InOrder(void (*visit)(T &data) = print) { InOrder(root, visit); }
private:
void InOrder(BTNode<T>* p, void (*visit)(T &data))
{
if (p){ InOrder(p->left, visit); visit(p->data); InOrder(p->right, visit); }
}
3. 后序遍历
public:
void PostOrder(void (*visit)(T &data) = print) { PostOrder(root, visit); }
private:
void PostOrder(BTNode<T>* p, void (*visit)(T &data))
{
if (p){ PostOrder(p->left, visit); PostOrder(p->right, visit); visit(p->data); }
}
4. 条理遍历
void LevelOrder(void (*visit)(T &data) = print)
{
queue< BTNode<T>* > a; BTNode<T>* p = root;//记得#include<queue>
while (p)
{
visit(p->data);
if (p->left) a.push(p->left); if (p->right) a.push(p->right);
if (a.empty()) break; p = a.front(); a.pop();
}
}
附注：缺省的visit函数print如下
private:
static void print(T &data) { cout << data << ' ';｝
5. 不消栈的非递归中序遍历
当有parent指针时，可以不消栈实现非递归的中序遍历，书上提到了有这种要领，但没给出例程。
public:
BTNode<T>* next()
{
if(!current) return NULL;
if (current->right) { current = current->right; while (current->left) current = current->left; }
else
{
BTNode<T>* y = current->parent;
while (y && current == y->right) {current = y; y = y->parent; }
current = y;
}
return current;
}
private:
BTNode<T>* current;
上面的函数能使current指针向前移动一个位置，假如要遍历整棵二叉树，需要使current指向中序序列的第一个节点，譬喻下面的成员函数：
public:
void first() { current = root; while (current->left) current = current->left; }
线索化二叉树
#p#分页标题#e#
这是数据布局课程里第一个遇到的难点，不知道你是不是这样看，横竖我当初是费了不少脑细胞——虽然，恼人的矩阵压缩和相关的加法乘法运算不在思量之列。我费了不少脑细胞是因为思考：他们干什么呢？很欣喜的看到在这本黄皮书上，这章被打了*号，固然我不确定作者是不是跟我一个想法——线索化二叉树在此刻的PC上是毫无用处的！——不知我做了这个结论是不是会被人骂死。
为了证明这个结论，我们来看看线索化二叉树提出的缘由：第一，我们想用较量少的时间，寻找二叉树某一个遍历线性序列的前驱可能后继。虽然，这样的操纵很频繁的时候，做这方面的改进才是有意义的。第二，二叉树的叶子节点尚有两个指针域没有用，可以节减内存。说真的，提出线索化二叉树这样的构想真的很精良，完全做到了“废料操作”——这小我私家真应该投身环保事业。但在计较机这个古板的对象身上，人们的精良构想往往都是不能实现的——为了速度，计较机的各个部件都是整齐划一的，而构想的精良往往都是成立在构成的巨大上的。
我们来看看线索化二叉树毕竟能不能到达上面的两个方针。
求遍历后的线性序列的前驱和后继。前序线索化能依次找到后继，可是前驱需要求双亲；中序线索化前驱和后继都不需要求双亲，可是都不很直接；后序线索化能依次找到前驱，可是后继需要求双亲。可以看出，线索化成中序是最佳的选择，根基上算是到达了要求。
节减内存。添加了两个符号位，问题是这两个位怎么储存？纵然是在支持位存储的CPU上，也是不能拿位存储器来存的，第一是因为布局体成员的地点是在一起的，第二是位存储器的数目是有限的。因此，最少需要1个字节来储存这两个符号位。而为了速度和移植，一般来说，内存是要对齐的，实际上基础就没节减内存！然而，当这个空间用来储存双亲指针时，带来的利便绝对不是线索化所能相比的，前面已经给出了无栈的非递归遍历。而且，在线索化二叉树上插入删除操纵附加的价钱太大。
综上，线索化最好是中序线索化（前序后序线索化后还得用栈，何必要线索化呢），附加的符号域空间至少1个字节，在32位的CPU会要求对齐到4字节，还不如存储一个双亲指针，同样能到达中序线索化的目标，而且能带来其他的长处。所以，线索化二叉树在此刻的PC上是毫无用处的！
由于对其他体系不太相识，以下概念姑妄听之。在内存空间很是丰裕的此刻，一个节点省2～3个字节实在是没什么意思（实际上由于对齐还省不出来）；而在内存很是名贵的处所（好比单片机），会只管制止利用树布局——操作其他的要领。所以，此刻看来，线索化二叉树真的是毫无用处了。
二叉搜索树
这恐怕是二叉树最重要的一个应用了。它的构思实际是个很自然的工作——查找值比当前节点小转左，大转右，等则查到，到头了就是没找着。越自然的对象越好领略，也就越不需要我空话。在给出BST的实现之前，我们要在二叉树的类中添加一个打印树状布局的成员函数，这样，就能清楚的看出插入和删除进程。
public:
void print()
{
queue< BTNode<T>* > a; queue<bool> flag; ofstream outfile("out.txt");
BTNode<T>* p = root; BTNode<T> zero; bool v = true;
int i = 1, level = 0, h = height();
while (i < 2<<h)
{
if (i == 1<<level)
{
cout << endl << setw(2 <<(h - level)); level++;
if (v) cout << p->data;
else cout << ' ';
}
else
{
cout << setw(4 <<(h - level + 1));
if (v) cout << p->data;
else cout << " ";
}
if (p->left) { a.push(p->left); flag.push(true); }
else { a.push(&zero); flag.push(false); }
if (p->right) { a.push(p->right); flag.push(true); }
else { a.push(&zero); flag.push(false); }
p = a.front(); a.pop(); v = flag.front(); flag.pop(); i++;
}
cout << endl;
}
#p#分页标题#e#
打印树状布局的焦点是按条理遍历二叉树，可是，二叉树有很多节点缺左或右子树，连带的越到下面旷地越大。为了凭据树的布局打印，必需把二叉树补成完全二叉树，这样下面的节点就知道放在什么位置了——a.push(&zero);可是这样的节点不能让它打印出来，所以对应每个节点，有一个是否打印的符号，按理说pair布局很符合，为了简朴我用了并列的两个行列，一个放节点指针——a，一个放打印符号——flag。这样一来，轮回竣事的符号就不能是行列空——永远都不行能空，遇到NULL就补一个节点——而是酿成了到了满二叉树的最后一个节点2^(height+1)-1。——黄皮书对付树高的界说是，空树为的高度为－1。
对付输格外式，留意的是到了第1、2、4、8号节点要换行，而且在同一行中，第一个节点的域宽是后序节点的一半。上面的函数在树的条理少于便是5（height<=4）的时候能正常显示，再多的话就必需输出到文件中去ofstream outfile("out.txt");——假如条理再多的话，打印出来也没什么意义了。
二叉搜索树的实现
实际上就是在二叉树的基本上增加了插入、删除、查找。
#include "BaseTree.h"
template <class T>
class BSTree : public BTree<T>
{
public:
BTNode<T>* &find(const T &data)
{
BTNode<T>** p = &root; current = NULL;
while(*p)
{
if ((*p)->data == data) break;
if ((*p)->data < data) { current = *p; p = &((*p)->right); }
else { current = *p; p = &((*p)->left); }
}
return *p;
}
bool insert(const T &data)
{
BTNode<T>* &p = find(data); if (p) return false;
p = new BTNode<T>(data, NULL, NULL, current); return true;
}
bool remove(const T &data)
{
return remove(find(data));
}
private:
bool remove(BTNode<T>* &p)
{
if (!p) return false; BTNode<T>* t = p;
if (!p->left || !p->right)
{
if (!p->left) p = p->right; else p = p->left;
if (p) p->parent = current;
delete t; return true;
}
t=p->right;while(t->left) t=t->left;p->data=t->data;current=t->parent;
return remove(current->left==t?current->left:current->right);
}
};
以上代码有点费解，有须要说明一下——非线性链式布局操纵的实现都是很让人费心。insert和remove都是以find为基本的，因此必需让find能最大限度的被这两个操纵操作。
1、对付insert，需要修改查找失败时的指针内容，显然这是个内部指针（在双亲节点的内部，而不是象root和current那样在节点外面指向节点），这就要求find返回一个内部指针的引用。可是C++的引用绑定到一个工具之后，就不能再改变了，因此在find内部的实现是一个二重指针。insert操纵还需要修改插入的新节点的parent指针域，因此在find中要发生一个能被insert会见的指向find返回值地址节点的指针，这里用的是current。实际上find返回的指针引用不是current->left就是current->right。这样一来，insert的实现就很是简朴了。
2、对付remove，需要修改查找乐成时的指针内容，同样是个内部指针。在find的基本上，很容易就能获得这个内部指针的引用(BTNode<T>* &p = find(data)。
在p->left和p->right中至少有一个为NULL的环境下，假如p->left ==NULL，那么就重连右子树p = p->right，反之，重连左子树p = p->left。留意，阁下子树全空的环境也包括在这两个操纵中了——在p->left ==NULL的时候重连右子树，而这时p->right也是NULL——因此不必列出来。假如重连后p不为空，需要修改p->parent = current。
若p->left和p->right都不为空，可以转化为有一个为空。譬喻一其中序有序序列[1,2,3,4,5]，假设3既有左子树又有右子树，那么它的前驱2必然缺右子树，后继4必然缺少左子树。【注1】这样一来删除节点3就等效成从[1,2,3(4),4,5]删除节点4。这样就可以操作上面的在p->left和p->right中至少有一个为NULL的环境下的要领了。照旧由于C++的引用不能改变绑定工具，这里是用操作递回来办理的，还好最多只递归一次。假如用二重指针又是满天星星了，这就是显着是尾递归却没有消去的原因。
#p#分页标题#e#
【注1】这是因为，假如3既有左子树又有右子树，那么2必然在3的左子树上，4必然在3的右子树上；假如2有右子树，那么在2和3之间还应该有一个节点；假如4有左子树，那么3和4之间也应该尚有一个节点。
【闲话】上面关于remove操纵p->left和p->right都不为空的处理惩罚要领的讲授，源于严蔚敏老师的课件，看完后我豁然开朗，真不知道为什么她本身那本《数据布局（C语言版）》这里写的那么难解，我是死活没看大白。
递归遍历与非递归遍历
在没有树的慨念，对递归的领略老是很坚苦，因为不能提出有说服力的例子，只是叙述了“递归是一种思想”。但只要能能让你成立“递归是一种思想”这个见识，我的尽力就没有白搭。此刻，讲完了二叉搜索树，终于有了能说明问题的例子了。凭据前面提供的代码，应该能调试通过下面的措施。
#include <iostream>
using namespace std;
#include <stdlib.h>
#include <time.h>
#include "BSTree.h"
#include "Timer.h"
#define random(num) (rand() % (num))
#define randomize() srand((unsigned)time(NULL))
#define NODENUM 200000//node number
int data[NODENUM];
void zero(int &t) { t = 0; }
int main()
{
BSTree<int> a; Timer t; randomize(); int i;
for (i = 0; i < NODENUM; i++) data[i] = i;
for (i = 0; i < NODENUM; i++) swap(data[i], data[random(NODENUM)]);//random swap
t.start(); for (i = 0; i < NODENUM; i++) a.insert(data[i]);
cout << "Insert time: " << t.GetTime() << "\tNode number: " << NODENUM << endl;
t.start(); for (a.first(); a.get() != NULL; a.next()) a.get()->data = 0;
cout << "Non-Stack time: " << t.GetTime() << endl;
t.start(); a.LevelOrder(zero); cout << "LevlOrder time: " << t.GetTime() << endl;
t.start(); a.PreOrder(zero); cout << " PreOrder time: " << t.GetTime() << endl;
t.start(); a.InOrder(zero); cout << " InOrder time: " << t.GetTime() << endl;
t.start(); a.PostOrder(zero); cout << "PostOrder time: " << t.GetTime() << endl;
return 0;
}
以下是timer.h的内容
#ifndef Timer_H
#define Timer_H
#include <windows.h>
class Timer
{
public:
Timer() { QueryPerformanceFrequency(&Frequency); }
inline void start() { QueryPerformanceCounter(&timerB); }
inline double GetTime()
{
QueryPerformanceCounter(&timerE);
return (double)(timerE.QuadPart - timerB.QuadPart) / (double)Frequency.QuadPart * 1000.0;
}
private:
LARGE_INTEGER timerB, timerE, Frequency;
};
#endif
上面的措施中，条理遍历用到的是行列，这应该可以代表用栈消解递归的环境，在我的呆板C500上运行的功效是：
Insert time: 868.818 Node number: 200000
Non-Stack time: 130.811
LevlOrder time: 148.438
PreOrder time: 125.47
InOrder time: 129.125
PostOrder time: 130.914
以上是VC6的release版的功效，时间单元是ms，不说明会有人认为是死机了，^_^。可以看出，递归遍历实际上并不慢，相反，更快一些，而debug版的功效是这样的：
Insert time: 1355.69 Node number: 200000
Non-Stack time: 207.086
LevlOrder time: 766.023
PreOrder time: 183.287
InOrder time: 179.835
PostOrder time: 190.674
递归遍历的速度是最快的
这恐怕是上面功效得出的最直接的结论。不知从哪听来的概念“递归的速度慢，为了提高速度，应该用栈消解递归”，证据就是斐波那契数列的计较，遗憾的是斐波那契数列的非递归算法是轮回迭代，不是栈消解；假如他真的拿栈来模仿，他就会发明，其实用栈的更慢。
我们来看看为什么。递归的实现是将参数压栈，然后call自身，最后按层返回，一系列的行动是在仓库上操纵的，用的是push、pop、call、ret之类的指令。而用ADT栈来模仿递归挪用，实现的照旧上述指令的成果，差异的是那些指令比较的ADT实现可就不可是一条指令了。谁都大白模仿的执行效率必定比真实的差，怎么会在这个问题上就犯糊涂了呢？
虽然，你非要在visit函数中插手雷同这样的istream file1(“input.txt”)，然后在用栈模仿的把这个放在轮回的外面，最后你说，栈模仿的比递归的快，我也无话可说——曾经就见过一小我私家，http://www.csdn.net/Develop/Read_Article.asp?Id=18342将数据库毗连放在visit函数内里，然后说递归的速度慢。
#p#分页标题#e#
假如一个递归进程用非递归的要领实现后，速度提高了，那只是因为递归做了一些无用功。好比用轮回消解的尾递归，是多了无用的压栈和出栈才使速度受损的；斐波那契数列计较的递归改轮回迭代所带来的速度大幅晋升，是因为改掉了反复计较的短处。倘使一个递归进程必需要用栈才气消解，那么，完全模仿后的功效基础就不会对速度有任何晋升，只会减慢；假如你改完后速度晋升了，那只证明你的递归函数写的有问题，譬喻多了很多反复操纵——打开封锁文件、毗连断开数据库，而这些完全可以放到递归外面。递归要领自己是简捷高效的，只是利用的人不留意利用要领。
这么看来，研究递归的栈消解仿佛是无用的，其实否则，用栈模仿递偿照旧有点意义的，只是并不大，下面将给出示例来说明。
栈模仿递归的长处是节减了仓库
将上面的措施//node number那行的数值改为15000——不改没回响了别找我，将//random swap那行注释掉，运行debug版，耐性的等30秒，就会抛异常了，最后的输出功效是这样的：
Insert time: 27555.5 Node number: 15000
Non-Stack time: 16.858
LevlOrder time: 251.036
这只能说明仓库溢出了。你可以看到条理遍历还能事情（由此类推，栈模仿的也能事情），可是递归的不能事情了。这是因为和总的内存空间比起来，仓库空间是很少的，假如递归的条理过深，仓库就溢出了。所以，假如你预先感想递归的条理大概过深，你就要思量用栈来消解了。
然而，假如你必需用递归，而递归的条理深到连仓库都溢出了，那必定是你的算法有问题，可能是谁人措施基础不适合在PC上运行——运行起来就象死机了，这样的措施谁敢用？所以说用栈模仿递归是有意义的，可是不大，因为很罕用到。
对付树布局来说，假如没有双亲指针，那么遍历时的递归是必需的，与其搞什么栈消解不如添加一个双亲指针，这实际上也是用堆空间调换仓库空间的一个要领，只是比ADT栈来得直接、高效而已。
综上，递归的栈消解，实际上只能节减仓库空间，不只不会提高速度，相反却会低落——天下哪有白吃的午餐，既省了仓库空间还能提高速度。那些“栈消解递归能提高速度”的讹传只是对“消除尾递归能提高速度”的不认真任的引申，然而一群人以谣传讹，真就像是那么回事了，这就叫三人成虎。等我这时候再回过甚看教科书，竟然没瞥见一本书上写着“栈消解递归能提高速度”。真的，以前一直被误导了，还不知道是被谁误导的——书上基础就没有写。
别的的结论
比拟上面两组功效，可以看到插入15000个节点比200000个节点耗损的时间还多，其原因就是插入数据的顺序差异，从而导致了find的效率差异。随机的顺序大抵能担保树的阁下子树漫衍匀称，而有序的序列将使树退化成单支的链表，从而使得O(logN)的时间巨大度酿成了O(N)。同时，这也是为什么200000个节点的树递归遍历还能事情，而递归遍历15000个节点的树仓库就溢出了——递归的每一层对应的节点太少了。
为了提高find的效率，同时也是使树的递归遍历要领的利用更为宽泛，有须要研究如何能使树的高度低落，这就是下面将要讲到的均衡树的理由。
