這些天參與了CSDN論壇的討論,改變了我以前的一些看法。回頭看我以前的東西,我雖對這本書很不滿,但我還是按照它的安排在一點點的寫;這樣就導致了,我過多的在意書中的偏漏,我寫的更多是說“這本書怎樣”,而偏離了我寫這些的初衷——給正在學習數據結構的人一些幫助。
<!-- frame contents -->
<!-- /frame contents -->
正像我在前面所說的,雖然現有的教科書都不是很合理,但假如僅僅是抱怨這點,那無異於潑婦罵街。雖然本人的水平連初級都夠不上,但至少先從我做一點嘗試,以後這門課的教授方法必將一點點趨於合理。
因此,後面不在按照書上的次序,將本著“實際應用(算法)決定數據結構”的思想來講解,常見教科書上有的,基本不再重點敘述(除了重點,例如AVL樹的平衡旋轉),——因此,在看本文的同時,一定要有一本教科書。這只是一個嘗試,希望大家多提寶貴意見。
樹
因為現實世界中存在這“樹”這種結構——族譜、等級制度、目錄分類等等,而為了研究這類問題,必須能夠將樹儲存,而如何儲存將取決於所需要的操作。這裡有個問題,是否答應存在空樹。有些書認為樹都是非空的,因為樹表示的是一種現實結構,而0不是自然數;我用過的教科書都是說可以有空樹,當然是為了和二叉樹統一。這個沒有什麼原則上的差別,反正就是一種習慣。
二叉樹
二叉樹可以說是人們假想的一個模型,因此,答應有空的二叉樹是無爭議的。二叉樹是有序的,左邊有一個孩子和右邊有一個的二叉樹是不同的兩棵樹。做這個規定,是因為人們賦予了左孩子和右孩子不同的意義,在二叉樹的各種應用中,你將會清楚的看到。下面只講解鏈式結構。看各種講數據結構的書,你會發現一個有趣的現象:在二叉樹這裡,基本操作有計算樹高、各種遍歷,就是沒有插入、刪除——那樹是怎麼建立起來的?其實這很好理解,對於非線性的樹結構,插入刪除操作不在一定的法則規定下,是毫無意義的。因此,只有在具體的應用中,才會有插入刪除操作。
更多內容請看C/C++技術專題 數據結構 數據結構教程專題,或
節點結構
數據域、左指針、右指針肯定是必須的。除非很少用到節點的雙親,或者是資源緊張,建議附加一個雙親指針,這將會給很多算法帶來方便,尤其是在這個“空間換時間”的時代。
template
strUCtBTNode
{
<!-- frame contents -->
<!-- /frame contents -->
BTNode(Tdata=T(),BTNode*left=NULL,BTNode*right=NULL,BTNode*parent=NULL)
:data(data),left(left),right(right),parent(parent){}
BTNode*left,*right,*parent;
Tdata;
};
基本的二叉樹類
template
classBTree
{
public:
BTree(BTNode*root=NULL):root(root){}
~BTree(){MakeEmpty();}
voidMakeEmpty(){destroy(root);root=NULL;}
protected:
BTNode*root;
private:
voiddestroy(BTNode*p)
{
if(p)
{
destroy(p->left);
destroy(p->right);
deletep;
}
}
}
二叉樹的遍歷
基本上有4種遍歷方法,先、中、後根,逐層。當初我對這個很迷惑,搞這麼多干什麼?到了後面才明白,這是不同的應用需要的。例如,判定兩個二叉樹是否相等,只要子樹根節點不同,那麼就不等,顯然這時要用先序遍歷;而刪除二叉樹,必須先刪除左右子樹,然後才能刪除根節點,這時就要用後序遍歷。
實際上,搞這麼多遍歷方法,根本原因是在內存中儲存的樹是非線性結構。對於用數組儲存的二叉樹,這些名目繁多的方法都是沒有必要的。利用C++的封裝和重載特性,這些遍歷方法能很清楚的表達。
更多內容請看C/C++技術專題 數據結構 數據結構教程專題,或
1.前序遍歷
public:
voidPreOrder(void(*visit)(T&data)=print){PreOrder(root,visit);}
private:
voidPreOrder(BTNode*p,void(*visit)(T&data))
{
<!-- frame contents -->
<!-- /frame contents -->
if(p){visit(p->data);PreOrder(p->left,visit);PreOrder(p->right,visit);}
}
2.中序遍歷
public:
voidInOrder(void(*visit)(T&data)=print){InOrder(root,visit);}
private:
voidInOrder(BTNode*p,void(*visit)(T&data))
{
if(p){InOrder(p->left,visit);visit(p->data);InOrder(p->right,visit);}
}
3.後序遍歷
public:
voidPostOrder(void(*visit)(T&data)=print){PostOrder(root,visit);}
private:
voidPostOrder(BTNode*p,void(*visit)(T&data))
{
if(p){PostOrder(p->left,visit);PostOrder(p->right,visit);visit(p->data);}
}
4.層次遍歷
voidLevelOrder(void(*visit)(T&data)=print)
{
queue*>a;BTNode*p=root;//記得#include
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:
staticvoidprint(T&data){cout<
5.不用棧的非遞歸中序遍歷
更多內容請看C/C++技術專題 數據結構 數據結構教程專題,或
當有parent指針時,可以不用棧實現非遞歸的中序遍歷,書上提到了有這種方法,但沒給出例程。
public:
BTNode*next()
{
if(!current)returnNULL;
<!-- frame contents -->
<!-- /frame contents -->
if(current->right){current=current->right;while(current->left)current=current->left;}
else
{
BTNode*y=current->parent;
while(y&¤t==y->right){current=y;y=y->parent;}
current=y;
}
returncurrent;
}
private:
BTNode*current;
上面的函數能使current指針向前移動一個位置,假如要遍歷整棵二叉樹,需要使current指向中序序列的第一個節點,例如下面的成員函數:
public:
voidfirst(){current=root;while(current->left)current=current->left;}
更多內容請看C/C++技術專題 數據結構 數據結構教程專題,或