【1】
這些天參與了CSDN論壇的討論，改變了我以前的一些看法。回頭看我以前的東西，我雖對(duì)這本書(shū)很不滿，但我還是按照它的安排在一點(diǎn)點(diǎn)的寫；這樣就導(dǎo)致了，我過(guò)多的在意書(shū)中的偏漏，我寫的更多是說(shuō)“這本書(shū)怎樣”，而偏離了我寫這些的初衷——給正在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的人一些幫助。正像我在前面所說(shuō)的，雖然現(xiàn)有的教科書(shū)都不是很合理，但如果僅僅是抱怨這點(diǎn)，那無(wú)異于潑婦罵街。雖然本人的水平連初級(jí)都?jí)虿簧希辽傧葟奈易鲆稽c(diǎn)嘗試，以后這門課的教授方法必將一點(diǎn)點(diǎn)趨于合理。<?xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" />
因此，后面不在按照書(shū)上的次序，將本著“實(shí)際應(yīng)用（算法）決定數(shù)據(jù)結(jié)構(gòu)”的思想來(lái)講解，常見(jiàn)教科書(shū)上有的，基本不再重點(diǎn)敘述（除了重點(diǎn)，例如AVL樹(shù)的平衡旋轉(zhuǎn)），——因此，在看本文的同時(shí)，一定要有一本教科書(shū)。這只是一個(gè)嘗試，希望大家多提寶貴意見(jiàn)。
樹(shù)
因?yàn)楝F(xiàn)實(shí)世界中存在這“樹(shù)”這種結(jié)構(gòu)——族譜、等級(jí)制度、目錄分類等等，而為了研究這類問(wèn)題，必須能夠?qū)?shù)儲(chǔ)存，而如何儲(chǔ)存將取決于所需要的操作。這里有個(gè)問(wèn)題，是否允許存在空樹(shù)。有些書(shū)認(rèn)為樹(shù)都是非空的，因?yàn)闃?shù)表示的是一種現(xiàn)實(shí)結(jié)構(gòu)，而0不是自然數(shù)；我用過(guò)的教科書(shū)都是說(shuō)可以有空樹(shù)，當(dāng)然是為了和二叉樹(shù)統(tǒng)一。這個(gè)沒(méi)有什么原則上的差別，反正就是一種習(xí)慣。
二叉樹(shù)
二叉樹(shù)可以說(shuō)是人們假想的一個(gè)模型，因此，允許有空的二叉樹(shù)是無(wú)爭(zhēng)議的。二叉樹(shù)是有序的，左邊有一個(gè)孩子和右邊有一個(gè)的二叉樹(shù)是不同的兩棵樹(shù)。做這個(gè)規(guī)定，是因?yàn)槿藗冑x予了左孩子和右孩子不同的意義，在二叉樹(shù)的各種應(yīng)用中，你將會(huì)清楚的看到。下面只講解鏈?zhǔn)浇Y(jié)構(gòu)。看各種講數(shù)據(jù)結(jié)構(gòu)的書(shū)，你會(huì)發(fā)現(xiàn)一個(gè)有趣的現(xiàn)象：在二叉樹(shù)這里，基本操作有計(jì)算樹(shù)高、各種遍歷，就是沒(méi)有插入、刪除——那樹(shù)是怎么建立起來(lái)的？其實(shí)這很好理解，對(duì)于非線性的樹(shù)結(jié)構(gòu)，插入刪除操作不在一定的法則規(guī)定下，是毫無(wú)意義的。因此，只有在具體的應(yīng)用中，才會(huì)有插入刪除操作。
節(jié)點(diǎn)結(jié)構(gòu)
數(shù)據(jù)域、左指針、右指針肯定是必須的。除非很少用到節(jié)點(diǎn)的雙親，或者是資源緊張，建議附加一個(gè)雙親指針，這將會(huì)給很多算法帶來(lái)方便，尤其是在這個(gè)“空間換時(shí)間”的時(shí)代。
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;
};
基本的二叉樹(shù)類
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;
}
}
}
二叉樹(shù)的遍歷
基本上有4種遍歷方法，先、中、后根，逐層。當(dāng)初我對(duì)這個(gè)很迷惑，搞這么多干什么？到了后面才明白，這是不同的應(yīng)用需要的。例如，判斷兩個(gè)二叉樹(shù)是否相等，只要子樹(shù)根節(jié)點(diǎn)不同，那么就不等，顯然這時(shí)要用先序遍歷；而刪除二叉樹(shù)，必須先刪除左右子樹(shù)，然后才能刪除根節(jié)點(diǎn)，這時(shí)就要用后序遍歷。
實(shí)際上，搞這么多遍歷方法，根本原因是在內(nèi)存中儲(chǔ)存的樹(shù)是非線性結(jié)構(gòu)。對(duì)于用數(shù)組儲(chǔ)存的二叉樹(shù)，這些名目繁多的方法都是沒(méi)有必要的。利用C++的封裝和重載特性，這些遍歷方法能很清晰的表達(dá)。
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函數(shù)print如下
private:
static void print(T &data) { cout << data << ' '; }
5. 不用棧的非遞歸中序遍歷
當(dāng)有parent指針時(shí)，可以不用棧實(shí)現(xiàn)非遞歸的中序遍歷，書(shū)上提到了有這種方法，但沒(méi)給出例程。
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;
上面的函數(shù)能使current指針向前移動(dòng)一個(gè)位置，如果要遍歷整棵二叉樹(shù)，需要使current指向中序序列的第一個(gè)節(jié)點(diǎn)，例如下面的成員函數(shù)：
public:
void first() { current = root; while (current->left) current = current->left; }
【2】
線索化二叉樹(shù)
這是數(shù)據(jù)結(jié)構(gòu)課程里第一個(gè)碰到的難點(diǎn)，不知道你是不是這樣看，反正我當(dāng)初是費(fèi)了不少腦細(xì)胞——當(dāng)然，惱人的矩陣壓縮和相關(guān)的加法乘法運(yùn)算不在考慮之列。我費(fèi)了不少腦細(xì)胞是因?yàn)樗伎迹核麄兏墒裁茨兀亢苄老驳目吹皆谶@本黃皮書(shū)上，這章被打了*號(hào)，雖然我不確定作者是不是跟我一個(gè)想法——線索化二叉樹(shù)在現(xiàn)在的PC上是毫無(wú)用處的！——不知我做了這個(gè)結(jié)論是不是會(huì)被人罵死，^_^。
為了證明這個(gè)結(jié)論，我們來(lái)看看線索化二叉樹(shù)提出的緣由：第一，我們想用比較少的時(shí)間，尋找二叉樹(shù)某一個(gè)遍歷線性序列的前驅(qū)或者后繼。當(dāng)然，這樣的操作很頻繁的時(shí)候，做這方面的改善才是有意義的。第二，二叉樹(shù)的葉子節(jié)點(diǎn)還有兩個(gè)指針域沒(méi)有用，可以節(jié)省內(nèi)存。說(shuō)真的，提出線索化二叉樹(shù)這樣的構(gòu)思真的很精巧，完全做到了“廢物利用”——這個(gè)人真應(yīng)該投身環(huán)保事業(yè)。但在計(jì)算機(jī)這個(gè)死板的東西身上，人們的精巧構(gòu)思往往都是不能實(shí)現(xiàn)的——為了速度，計(jì)算機(jī)的各個(gè)部件都是整齊劃一的，而構(gòu)思的精巧往往都是建立在組成的復(fù)雜上的。
我們來(lái)看看線索化二叉樹(shù)究竟能不能達(dá)到上面的兩個(gè)目標(biāo)。
求遍歷后的線性序列的前驅(qū)和后繼。前序線索化能依次找到后繼，但是前驅(qū)需要求雙親；中序線索化前驅(qū)和后繼都不需要求雙親，但是都不很直接；后序線索化能依次找到前驅(qū)，但是后繼需要求雙親。可以看出，線索化成中序是最佳的選擇，基本上算是達(dá)到了要求。
節(jié)省內(nèi)存。添加了兩個(gè)標(biāo)志位，問(wèn)題是這兩個(gè)位怎么儲(chǔ)存？即使是在支持位存儲(chǔ)的CPU上，也是不能拿位存儲(chǔ)器來(lái)存的，第一是因?yàn)榻Y(jié)構(gòu)體成員的地址是在一起的，第二是位存儲(chǔ)器的數(shù)目是有限的。因此，最少需要1個(gè)字節(jié)來(lái)儲(chǔ)存這兩個(gè)標(biāo)志位。而為了速度和移植，一般來(lái)說(shuō)，內(nèi)存是要對(duì)齊的，實(shí)際上根本就沒(méi)節(jié)省內(nèi)存！然而，當(dāng)這個(gè)空間用來(lái)儲(chǔ)存雙親指針時(shí)，帶來(lái)的方便絕對(duì)不是線索化所能比擬的，前面已經(jīng)給出了無(wú)棧的非遞歸遍歷。并且，在線索化二叉樹(shù)上插入刪除操作附加的代價(jià)太大。
綜上，線索化最好是中序線索化（前序后序線索化后還得用棧，何必要線索化呢），附加的標(biāo)志域空間至少1個(gè)字節(jié)，在32位的CPU會(huì)要求對(duì)齊到4字節(jié)，還不如存儲(chǔ)一個(gè)雙親指針，同樣能達(dá)到中序線索化的目的，并且能帶來(lái)其他的好處。所以，線索化二叉樹(shù)在現(xiàn)在的PC上是毫無(wú)用處的！
由于對(duì)其他體系不太了解，以下觀點(diǎn)姑妄聽(tīng)之。在內(nèi)存空間非常充裕的現(xiàn)在，一個(gè)節(jié)點(diǎn)省2～3個(gè)字節(jié)實(shí)在是沒(méi)什么意思（實(shí)際上由于對(duì)齊還省不出來(lái)）；而在內(nèi)存非常寶貴的地方（比如單片機(jī)），會(huì)盡量避免使用樹(shù)結(jié)構(gòu)——利用其他的方法。所以，現(xiàn)在看來(lái)，線索化二叉樹(shù)真的是毫無(wú)用處了。
二叉搜索樹(shù)
這恐怕是二叉樹(shù)最重要的一個(gè)應(yīng)用了。它的構(gòu)想實(shí)際是個(gè)很自然的事情——查找值比當(dāng)前節(jié)點(diǎn)小轉(zhuǎn)左，大轉(zhuǎn)右，等則查到，到頭了就是沒(méi)找著。越自然的東西越好理解，也就越不需要我廢話。在給出BST的實(shí)現(xiàn)之前，我們要在二叉樹(shù)的類中添加一個(gè)打印樹(shù)狀結(jié)構(gòu)的成員函數(shù)，這樣，就能清楚的看出插入和刪除過(guò)程。
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;
}
打印樹(shù)狀結(jié)構(gòu)的核心是按層次遍歷二叉樹(shù)，但是，二叉樹(shù)有許多節(jié)點(diǎn)缺左或右子樹(shù)，連帶的越到下面空隙越大。為了按照樹(shù)的結(jié)構(gòu)打印，必須把二叉樹(shù)補(bǔ)成完全二叉樹(shù)，這樣下面的節(jié)點(diǎn)就知道放在什么位置了——a.push(&zero);但是這樣的節(jié)點(diǎn)不能讓它打印出來(lái)，所以對(duì)應(yīng)每個(gè)節(jié)點(diǎn)，有一個(gè)是否打印的標(biāo)志，按理說(shuō)pair結(jié)構(gòu)很合適，為了簡(jiǎn)單我用了并列的兩個(gè)隊(duì)列，一個(gè)放節(jié)點(diǎn)指針——a，一個(gè)放打印標(biāo)志——flag。這樣一來(lái)，循環(huán)結(jié)束的標(biāo)志就不能是隊(duì)列空——永遠(yuǎn)都不可能空，碰到NULL就補(bǔ)一個(gè)節(jié)點(diǎn)——而是變成了到了滿二叉樹(shù)的最后一個(gè)節(jié)點(diǎn)2^(height+1)-1。——黃皮書(shū)對(duì)于樹(shù)高的定義是，空樹(shù)為的高度為－1。
對(duì)于輸出格式，注意的是到了第1、2、4、8號(hào)節(jié)點(diǎn)要換行，并且在同一行中，第一個(gè)節(jié)點(diǎn)的域?qū)捠呛笮蚬?jié)點(diǎn)的一半。上面的函數(shù)在樹(shù)的層次少于等于5（height<=4）的時(shí)候能正常顯示，再多的話就必須輸出到文件中去ofstream outfile("out.txt");——如果層次再多的話，打印出來(lái)也沒(méi)什么意義了。
二叉搜索樹(shù)的實(shí)現(xiàn)
實(shí)際上就是在二叉樹(shù)的基礎(chǔ)上增加了插入、刪除、查找。
#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);
}
};
以上代碼有點(diǎn)費(fèi)解，有必要說(shuō)明一下——非線性鏈?zhǔn)浇Y(jié)構(gòu)操作的實(shí)現(xiàn)都是很讓人費(fèi)神。insert和remove都是以find為基礎(chǔ)的，因此必須讓find能最大限度的被這兩個(gè)操作利用。
l 對(duì)于insert，需要修改查找失敗時(shí)的指針內(nèi)容，顯然這是個(gè)內(nèi)部指針（在雙親節(jié)點(diǎn)的內(nèi)部，而不是象root和current那樣在節(jié)點(diǎn)外面指向節(jié)點(diǎn)），這就要求find返回一個(gè)內(nèi)部指針的引用。但是C++的引用綁定到一個(gè)對(duì)象之后，就不能再改變了，因此在find內(nèi)部的實(shí)現(xiàn)是一個(gè)二重指針。insert操作還需要修改插入的新節(jié)點(diǎn)的parent指針域，因此在find中要產(chǎn)生一個(gè)能被insert訪問(wèn)的指向find返回值所在節(jié)點(diǎn)的指針，這里用的是current。實(shí)際上find返回的指針引用不是current->left就是current->right。這樣一來(lái)，insert的實(shí)現(xiàn)就非常簡(jiǎn)單了。
l 對(duì)于remove，需要修改查找成功時(shí)的指針內(nèi)容，同樣是個(gè)內(nèi)部指針。在find的基礎(chǔ)上，很容易就能得到這個(gè)內(nèi)部指針的引用(BTNode<T>* &p = find(data)。
? 在p->left和p->right中至少有一個(gè)為NULL
數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)（C++）二叉樹(shù)