【正文】 data。 算法：用中序遍歷即可 ， 但遞歸慢 ， 下面為迭代查找算法 。這步就是插入算法。 2. 若 a1a0，令 a1為 a0左子樹的根結(jié)點，否則 a1為 a0右子樹的根結(jié)點。} 在 VC++平臺上演示例 二叉排序樹的 結(jié)點插入（可生成排序二叉樹） 生成算法 ：對任意一組數(shù)據(jù)元素序列 {a0， a1， a2， … ， an1}。in。 //小于 ,去左子樹查 else Insert(data,brchild)。exit(1)。b){ if(b==NULL){ //已到空樹 ,插入 b=new NodeT(data)。 10 18 26 8 12 22 29 11 24 16 15 圖 二叉排序樹例 templatetypename T void BinaryTreeT::Insert(const T amp。 二叉排序樹的定義 ：二叉排序樹或者是空樹或者是具有下述性質(zhì)的二叉數(shù) ， 其左子樹上所有結(jié)點的數(shù)據(jù)值均小于根結(jié)點的數(shù)據(jù)值；右子樹上所有結(jié)點的數(shù)據(jù)值均大于等于根結(jié)點的數(shù)據(jù)值 ，左子樹和右子樹又各是一棵二叉排序樹 。 A B C D E F G H I J K 圖 例 排序二叉樹 二叉排序樹 （ Binary Sorting Tree） 又稱二叉搜索樹 （ Binary Search Tree） ， 是一種特殊結(jié)構(gòu)的二叉數(shù) ， 作為一種排序和查找的手段 ，對應(yīng)有序表的對半查找 ， 通常亦被稱為數(shù)表 。結(jié)果如圖 。再由先序 D G知， D為 B的右子樹根結(jié)點，由中序 D G知 G為 D的右子樹。 由先序中的 B C E F D G知 B為左子樹根結(jié)點 ， 由中序中的 E C F B D G知 E C F為其左子樹 ， 而 DG為右子樹 。 } } //后序訪問根結(jié)點 在 VC++平臺上演示例 二叉樹的遍歷 【 例 】 某二叉樹先序遍歷為ABCEFDGHIJK，中序遍歷為ECFBDGAIHJK繪出該二叉樹。 coutCurrentinfo39。} } templatetypename T void BinaryTreeT::PostOrder(NodeT *Current){ if(Current!=NULL){ PostOrder(Currentlchild)。 //注意前序訪問語句所放位置 PreOrder(Currentlchild)。 } } //中序遍歷右子樹 templatetypename T void BinaryTreeT::PreOrder(NodeT *Current){ if(Current!=NULL){ coutCurrentinfo39。\t39。 二叉樹的遍歷 下面為 3種遍歷算法： templatetypename T void BinaryTreeT::InOrder(NodeT *Current){ if(Current!=NULL){ //遞歸終止條件 InOrder(Currentlchild)。} //前序遍歷，公有函數(shù)為接口 void PostOrder(){PostOrder(root)。 //建立（排序）二叉樹 void InOrder(){InOrder(root)。} //空樹構(gòu)造函數(shù) ~BinaryTree(){Destory(root)。 //插入結(jié)點，參數(shù)為引！ void Destory(NodeT * Current)。data,NodeT * amp。 //前序遍歷 void PostOrder(NodeT *Current)。 //二叉樹的根指針 void InOrder(NodeT *Current)。 本例采用簡單的接口函數(shù) ， 而把較復(fù)雜的算法作為私有函數(shù) 。特別注意插入結(jié)點時 ， 第二參數(shù)為指針的引用 ！ 否則不能建立樹 。 后序遍歷結(jié)果為 D G E B H F C A。 遍歷二叉樹有不同次序，規(guī)定先左后右，令L， R， V分別代表遍歷一個結(jié)點的左右子樹和訪問該結(jié)點的操作，有三種方式： 前序遍歷（ VLR） 中序遍歷（ LVR） 后序遍歷（ LRV） 二叉樹的遍歷 例如：前序遍歷訪問次序為 ABDEGCFH。 //二叉樹類說明為友元類 二叉樹的遍歷 所 謂 二 叉 樹 的 遍 歷 （ binary tree traversal） ， 就是遵從某種次序 ， 查巡二叉樹的所有結(jié)點 ， 每個結(jié)點都被訪問一次 ， 而且僅訪問一次 。} //設(shè)置左指針 void setrightNodeT *right){rchild=right。} //取得左子樹 NodeT *Getright(){return rchild。data){info=data。 } T Getinfo(){return info。 lchild=left。rchild=NULL。 T info。 lchild rchild info 圖 二叉樹結(jié)點 二叉樹的概念 二叉樹類結(jié)點類模板定義如下： templatetypename Tclass BinaryTree。 1 2 3 4 5 6 7 9 8 10 11 14 13 12 15 圖 滿二叉樹 1 2 3 4 5 6 7 9 8 10 圖 完全二叉樹 二叉樹的概念 下面給出鏈式儲存方式的二叉樹。 解：結(jié)果見圖 ， 共 5種 。 二叉樹的基本性質(zhì)： 1． 二叉樹的第 i層上最多有 2i1(i=1)個結(jié)點； 2． 深度為 h的二叉樹中最多有 2h1個結(jié)點； 3． 在任一棵二叉樹中 ， 有 n0葉子結(jié)點 ， 有 n2個度為 2的 結(jié)點 ， 則有 n0=n2+1。 這也是一個遞歸的定義 。 二叉樹的概念 二叉樹 （ Binary Tree） 是另一種獨立的樹形結(jié)構(gòu) 。 樹的深度 ,樹中結(jié)點的層次數(shù) 。 兄弟結(jié)點 ， 同一雙親的結(jié)點互稱為兄弟 。 孩子結(jié)點 ， 若結(jié)點 x有子樹 ， 則子樹根結(jié)點即為 x的孩子結(jié)點 。 葉結(jié)點 ， 度為 0的結(jié)點 ， 如 G， I， J，K， L， M， N， O結(jié)點 。 二叉樹的概念 A B C D E F G I H J L K O N M ………… 0層 …… 1層 2層 3層 深度 圖 樹的示意圖 結(jié)點 ， 包括數(shù)據(jù)項和多個指針項 ，指針項數(shù)目并不固定 ， 且無次序 。每棵子樹的根結(jié)點有且僅有一個直接前驅(qū)，但可以有 0個或多個直接后繼。非空樹有一個特定的結(jié)點，它只有直接后繼，沒有直接前驅(qū)，稱之為根（ root）。 二叉樹的遍歷 二叉樹的概念 排序二叉樹 二叉樹的概念 樹（ Tree） 是由 n（ n≥0）個結(jié)點組成的有限集合。 return frontinfo。 //釋放內(nèi)存空間 return data。 //取隊頭結(jié)點中的數(shù)據(jù) front=frontlink。 NodeT *temp=front。 else rear=rearlink=new NodeT(data,NULL)。} templatetypename Tvoid QueueT::EnQue(const T amp。delete temp。 while(front!=NULL){ temp=front。 }。 //出隊 T GetFront()。data)。 bool IsEmpty(){ return front==NULL。 public: Queue(){rear=front=NULL。}。 templatetypename T NodeT::Node(T data,Node *l){ info=data。 friend class QueueT。 NodeT *link。 templatetypename Tclass Queue。鏈首出隊，鏈尾入隊。 return elements[(front+1)%maxSize]。 //隊頭指針加 1 return elements[front]。} templatetypename TT QueueT::DeQue(){ assert(!IsEmpty())。 //斷言：隊列不滿，不滿才能進隊 rear=(rear+1)%maxSize。 }//斷言：分配成功 templatetypename Tvoid QueueT::EnQue(const Tamp。 rear=front=0。 隊列 templatetypename T QueueT::Queue(int ms){ maxSize=ms。 //取隊頭數(shù)據(jù) void MakeEmpty(){front=rear=0。 //進隊 T DeQue()。} //求隊中元素數(shù)，注意求余算法 void EnQue(const T amp。} //判隊空 bool IsFull() const {return (rear+1)%maxSize==front。 ~Queue(){delete[] elements。 //存放隊列元素的容器 int maxSize。 templatetypename Tclass Queue{ int rear,front。若想利用這個空間，必然加一個標志來表示隊空 /隊滿，進隊出隊都要判斷，使用上更不方便。 隊列 隊列總是做成一個邏輯上的循環(huán)隊列 注意，空隊時 rear=front，滿隊時必須空一個位置 隊列 循環(huán)隊列 浪費一個位置好像太可惜，特別在該位置中存放一個很大的對象時。 a0 a1 a2 … an1 … front 元素移動 方向 rear 圖 圖 ，隊尾 (rear)不斷向后移；而隨隊頭元素的出隊，則隊頭 (front)也不斷后移，即 位置在變（如要位置不變， 移動元素 工作量也太大）。每次在隊尾加入新元素，加入稱為 進隊 ，刪除稱為 出隊 。它 只允許在表的一端插入，而在另一端刪除 。) b2=false。 } if(ch1==39。} Compute(ch1)。: while(!()){ ch2=()。 case 39。 //再把新的運算符壓棧 b1=true。 //先把原棧中的運算符壓回去 b1=false。) //比較優(yōu)先級 Compute(ch2)。||ch2==39。 //把棧頂運算符彈出 if(ch2==39。amp。/39。*39。break。優(yōu)先級低的 Compute(ch2)。 39。 //不會有比 39。39。+39。break。c39。 //數(shù)字串轉(zhuǎn)換為整數(shù)后壓棧 k=1。\039。 str[k]=ch1。939。amp。039。 while(b2){ cinch1。 char ch1,ch2,str[50]。:cout()endl。 case 39。:(Num2/Num1)。 case 39。:(Num2*Num1)。 case 39。:(Num2Num1)。 //結(jié)果壓棧 case 39。:(Num2+Num1)。 switch(Opr){ case 39。=39。} 棧與應(yīng)用 void Calculator::Compute(char Opr){ int Num1,Num2。Num2){ Num1=()。} void Calculator::GetTwoNum(int amp。 void Calculator::Clear(){ ()。 void Clear(void)。Num2)。 //計算器運算程序 void GetTwoNum(int amp。 public: Calculator(void){}。 簡易計算器類定義： class Calculator{ Stackint Nstack。 表達式結(jié)束符使用＝號 ， 清空棧用 ‘ c’字符 。棧中數(shù)據(jù)繼續(xù)按前面規(guī)則出棧。否則將棧頂運算符出棧，與數(shù)字棧出棧的兩個數(shù)據(jù)進行運算，結(jié)果壓入數(shù)棧，再將新運