?? p236.cpp
字號:
#include <iostream.h>#include "P170.cpp"#include "Stack.h"const MaxN=30;template <class Type> class BST; //二叉搜索樹的前視聲明template <class Type> class BstNode : public BinTreeNode<Type> { //二叉搜索樹結點類friend class BST;public: BstNode ( const Type d=0, BstNode *L=NULL, BstNode *R =NULL) //構造函數 : data (d), leftChild (L), rightChild (R) { }; ~BstNode ( ) { } friend class BST<Type>;protected: Type data; //數據域(用作關鍵碼) BstNode<Type> *leftChild, *rightChild; //左子女和右子女鏈域};template <class Type> class BST : BinaryTree <Type> { //二叉搜索樹類定義public: BST ( ) :root(NULL){}; //構造函數 BST ( Type value ) ; BST (const BST<Type> & T) ;//構造函數 ~BST ( ) { MakeEmpty ( ); } //析構函數 const BST & operator = ( const BST & Value ); void MakeEmpty( ) { destroy (root); root=NULL; } void PrintTree ( ) const { PrintTree ( root ); } int Find ( const Type & x ) const { return (Find ( x, root )!=NULL) ; } //搜索元素 Type Min() { return Min(root)->data;}; //求最小 Type Max() { return Max(root)->data;}; //求最大 int Insert ( const Type & x ) { return Insert ( x, root ); } //插入新元素 int Remove (const Type & x ) { return Remove ( x, root ); } //刪除含x的結點 BstNode<Type> *Split ( Type i, BST<Type> &B, Type &x, BST<Type> &C ); void OpticBST ( int p[ ], int q[ ], Type a[ ], int n ); friend class BSTIterator ;//中序游標類 private: //在關鍵碼i處分解二叉搜索樹 BstNode<Type> *root; //二叉搜索樹的根指針 Type RefValue; //數據輸入停止的標志, 用于輸入 BstNode<Type> *lastfound; //最近搜索到的結點的指針// void MakeEmpty ( BstNode<Type> * ptr ); //置空 int Insert ( const Type & x, BstNode<Type> * & ptr ); //插入 int Remove ( const Type & x, BstNode<Type> * & ptr ); //刪除 void PrintTree ( BstNode<Type> * ptr ) const; //打印 BstNode<Type> *Copy (const BstNode<Type> * ptr ); //復制 BstNode<Type> *Find (const Type & x, BstNode<Type> * ptr ) const; //搜索 BstNode<Type> *Min ( BstNode<Type> * ptr ) const; //求最小 BstNode<Type> *Max ( BstNode<Type> * ptr ) const; //求最大 };/*template <class Type> BstNode<Type> * BST<Type>::Find (const Type & x, BstNode<Type> * ptr ) const {//私有函數：在以ptr為根的二叉搜索樹中搜索含x的結點。若找到，則函數返回該結點的地址，否則函數返回//NULL值。 if ( ptr == NULL ) return NULL; else if ( x < ptr->data ) return Find ( x, ptr->leftChild ); //到左子樹中繼續搜索 else if ( x > ptr->data ) return Find( x, ptr->rightChild ); //到右子樹中繼續搜索 else return ptr; //搜索成功}*/template <class Type> BstNode<Type> *BST<Type>::Find (const Type & x, BstNode<Type> * ptr ) const {//私有函數: 說明與程序7.14相同 if ( ptr != NULL ) { //樹空返回 BstNode<Type> * temp = ptr; //從根開始搜索 while ( temp != NULL ) { //==NULL表示搜索失敗 if ( temp->data == x ) return temp; //搜索成功 if ( temp->data < x ) temp = temp->rightChild; //否則，繼續搜索右子樹 else temp = temp->leftChild; //否則，繼續搜索左子樹 } } return NULL;};template <class Type> int BST<Type>::Insert (const Type & x, BstNode<Type> * & ptr) {//私有函數：在以ptr為根的二叉搜索樹中插入所含值為x的結點。若在樹中已經有含x的結點，則不插入。 if ( ptr == NULL ) { //新結點作為葉結點插入 ptr = new BstNode<Type> (x); //創建新結點 if ( ptr == NULL ) return 0; else return 1; } else if ( x < ptr->data ) return Insert ( x, ptr->leftChild ); //小于根的關鍵碼, 向左子樹插入 else if ( x > ptr->data ) return Insert ( x, ptr->rightChild ); //大于, 向右子樹插入 return 1; //除上述情況外, 就是x已在樹中的情形, 不再插入}template <class Type>BST<Type>::BST ( Type value ) {//輸入一個元素序列, 建立一棵二叉搜索樹 Type x; root = NULL; RefValue = value; //置空樹 cin >> x; //輸入數據 while ( x != RefValue ) { //RefValue是一個輸入結束標志 Insert ( x, root ); cin >> x; //插入，再輸入數據 }}template <class Type>void BST<Type>::PrintTree ( BstNode<Type> * ptr ) const //打印{ if (ptr!=NULL) { cout<<ptr->data; cout<<"("; PrintTree(ptr->leftChild); cout<<","; PrintTree(ptr->rightChild); cout<<")"; }}template <class Type> int BST<Type>::Remove (const Type &x, BstNode<Type> * &ptr) {//私有函數：在以ptr為根的二叉搜索樹中刪除含x的結點。若刪除成功則新根通過ptr返回。 BstNode<Type> * temp; if ( ptr != NULL ) if ( x < ptr->data ) return Remove ( x, ptr->leftChild ); //在左子樹中執行刪除 else if ( x > ptr->data ) return Remove ( x, ptr->rightChild ); //在右子樹中執行刪除 else if ( ptr->leftChild != NULL && ptr->rightChild != NULL ) { // ptr指示關鍵碼為x的結點，它有兩個子女 temp = Min ( ptr->rightChild ); //在ptr的右子樹中搜尋最小結點 ptr->data = temp->data; //用該結點數據代替根結點數據 return Remove ( ptr->data, ptr->rightChild ); //在右子樹中刪除該結點 } else { // ptr指示關鍵碼為x的結點，它只有一個或零個子女 temp = ptr; if ( ptr->leftChild == NULL ) ptr = ptr->rightChild; //只有右子女 else if ( ptr->rightChild == NULL ) ptr = ptr->leftChild; //只有左子女 delete temp; return 1; } else return 0;}template <class Type> class InorderIterator { //中序游標類定義public: InorderIterator ( BST<Type> & Tree ) : ref (Tree) { Init ( ); } int Init ( ); //初始化 int operator ! ( ); //求反 Type operator ( ) ( ); //取棧頂元素值 int operator ++ ( ); // BST按前序進行遍歷private: BST<Type> & ref; //二叉搜索樹對象 Stack < BstNode<Type> * > itrStack; //迭代工作棧};template <class Type> int InorderIterator<Type>::Init ( ) { //初始化操作 itrStack.MakeEmpty ( ); //置迭代工作棧為空 if ( ref.root != NULL ) itrStack.Push ( ref.root ); //若二叉搜索樹不空則根指針進棧 return ! itrStack.IsEmpty ( ); //若棧空則返回0，否則返回1}template <class Type> int InorderIterator<Type>::operator ! ( ) { return ! itrStack.IsEmpty ( ); //若棧空則返回0，否則返回1}template <class Type> Type InorderIterator<Type>::operator ( ) ( ) { //返回當前結點的數據值 Node<Type> * current = itrStack.GetTop ( ); //取棧頂結點為當前結點 return current->data; //返回當前結點的關鍵碼}template <class Type> int InorderIterator<Type>::operator ++ ( ) {//按二叉搜索樹結點的前序序列進棧。還可以向前走則函數返回1, 否則返回0。 BstNode<Type> * current = itrStack.GetTop ( ); //取存在棧頂上的結點 BstNode<Type> * next = current->leftChild; //左子女 if ( next != NULL ) { itrStack.Push ( next ); return 1; } //左子女非空, 進棧(向左子樹遍歷) while ( ! itrStack.IsEmpty ( ) ) { //否則, 若棧非空 current = itrStack.Pop ( ); next = current->rightChild; //退棧, 取其右子女 if ( next != NULL ) { itrStack.Push ( next ); return 1; } //右子女非空, 進棧 } return 0;}/*template <class Type>BST<Type>::BST (const BST<Type> & T) : root (NULL) {//構造函數：根據參數初始化樹T InorderIterator<Type> itr ( Type ); //聲明中序游標類對象 for ( itr.init ( ); ! itr; itr++) Insert ( itr ( ) ); //按前序順序插入}*/template <class Type>BstNode<Type> * BST<Type>::Min ( BstNode<Type> * ptr ) const //求最小{ BstNode<Type> * temp1,*temp2; temp1=ptr; if (ptr!=NULL) { if (ptr->leftChild!=NULL) { temp2=Min(ptr->leftChild); if (temp1->data>temp2->data) temp1=temp2; } if (ptr->rightChild!=NULL) { temp2=Min(ptr->rightChild); if (temp1->data>temp2->data) temp1=temp2; } } return temp1;}template <class Type>BstNode<Type> * BST<Type>::Max ( BstNode<Type> * ptr ) const //求最小{ BstNode<Type> * temp1,*temp2; temp1=ptr; if (ptr!=NULL) { if (ptr->leftChild!=NULL) { temp2=Max(ptr->leftChild); if (temp1->data<temp2->data) temp1=temp2; } if (ptr->rightChild!=NULL) { temp2=Max(ptr->rightChild); if (temp1->data<temp2->data) temp1=temp2; } } return temp1;}template <class Type> void BST<Type>::OpticBST ( int p[ ], int q[ ], Type a[ ], int n ) {//給定n個不同的數據 a[1] < a[2] < … < a[n], 以及它們具有的權值p[j], 1 ( j ( n, 另外落在它們之間外部//結點上的權值分別為 q[i], 0 ( i ( n。本算法計算a[i+1], ……, a[j]的最優二叉搜索樹T[i][j]的代價C[i][j],//T[i][j]的根R[i][j]和權W[i][j]。 int R[MaxN+1][MaxN+1]; int C[MaxN+1][MaxN+1]; int W[MaxN+1][MaxN+1]; for ( int i=0; i<n; i++) { W[i][i] = q[i]; C[i][i] = R[i][i] = 0; //初始化 W[i][i+1] = W[i][i] + p[i+1] + q[i+1]; //構造只有一個內部結點, 兩個外部結點的最優二叉搜索樹 R[i][i+1] = i+1; //這些樹的根在i+1 C[i][i+1] = W[i][i+1]; //這些樹的總帶權路徑長度(代價) } W[n][n] = q[n]; R[n][n] = C[n][n] = 0; for ( int m=2; m<=n; m++ ) //構造具有m個內部結點的最優二叉搜索樹 for ( i=0; i<=n-m; i++ ) { int j = i + m; W[i][j] = W[i][j-1] + p[j] + q[j]; //在前一棵樹基礎上再加一內部結點和一外部結點 int min = C[i+1][j], u = i+1; //假定i+1為根, 計算代價 for ( int k=i+2; k<=j; k++ ) if ( C[i][k-1] + C[k][j] < min ) { min = C[i][k-1] + C[k][j]; u = k; } //輪流以i+2,…,j為根, 選代價最小的送min, 其根為u C[i][j] = W[i][j] + min; R[i][j] = u; } Stack < int > nodeStack; MakeEmpty(); nodeStack.Push(0); nodeStack.Push(n); while (!nodeStack.IsEmpty()) { int j=nodeStack.Pop(); int i=nodeStack.Pop(); Insert(a[R[i][j]]); if ((i+1)<R[i][j]) { nodeStack.Push(i); nodeStack.Push(R[i][j]-1); }; if ((R[i][j])<j) { nodeStack.Push(R[i][j]); nodeStack.Push(j); }; }}?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -