1、二叉搜索樹是二叉樹的一種，樹的每個結點含有一個數據項，每個數據項有一個鍵值。結點的存儲位置是由鍵值的大小決定的，所以二叉搜索樹是關聯式容器。
(1)、 若它的左子樹不空，則左子樹上所有結點的鍵值均小于它的根結點的鍵值；
(2)、若它的右子樹不空，則右子樹上所有結點的鍵值均大于它的根結點的鍵值；
(3)、它的左、右子樹也分別為二叉排序樹。
注意：：：二叉排序樹是一種動態樹表，樹的結構通常不是一次生成的。而是在查找的過程中，當樹中不存在關鍵字等于給定值的節點時再進行插入。新插入的結點一定是一個新添加的葉子結點，并且是查找不成功時查找路徑上訪問的最后一個結點的左孩子或右孩子結點。

2、插入與查找算法：
查找：
（1）、若二叉排序樹非空，將給定值與根節點的關鍵字值比較，若相等，則查找成功；
（2）、若不等，則當根節點的關鍵字值大于給定值時，到根的左子樹中進行查找；
（3）、否則到根的右子樹中進行查找。若找到，則查找過程是走了一條從樹根到所找到節點的路徑；
（4）、否則，查找過程終止于一棵空樹。
//① 、普通查找，查找不成功返回NULL
遞歸思想：
 BiTree SearchBST (BiTree *T，KeyType key)
{
    //在根指針T所指二叉排序樹中遞歸地查找某關鍵字等于key的數據元素
    //若查找成功，則返回指向該數據元素結點的指針，否則返回空指針
        if( (!T)||(key==T—>data.key))
            return (T)； //查找結束,此時T為NULL，或者為該結點
        else if (key< T—>data.key)
                return(SearchBST(T—>lchild，key))； //在左子樹中繼續查找
                else
                return(SearchBST(T —>rchild，key))；// 在右子樹中繼續查找
    }//SearchBST

非遞歸思想：
BiTree SearchBST (BiTree *root，KeyType key)
{ 
   BiTree *p；
   if( root ＝＝ NULL)return NULL；//查找結束,此時根為NULL，
   p ＝ root；
   while(p!=NULL)
   { 
        if(p －>key==Key)breat；
       if( Key < p ->key) p ＝p －>lchild；//在左子樹中繼續查找
         else p ＝ p －>rchild；//在右子樹中繼續查找
    }
   return p；
}
//② 、查找不成功，返回插入位置
    //在根指針T所指二叉排序樹中遞歸地查找其關鍵字等于key的數據元素，
    //若查找成功，則指針p指向該數據元素結點，并返回TRUE，
    //否則指針p指向查找路徑上訪問的最后一個結點并返回FALSE，
    //指針f指向T的雙親，其初始調用值為NULL
 BOOL SearchBST(BiTree *T，KeyType key，BiTree *f，BiTree &p)
{
        if(!T) {p=f；return FALSE；} //查找不成功
        else if (key==T—>data.key) 
            {p=T；return TRUE；} //查找成功
           else if (key<T—>data.key) SearchBST(T—>lchild，key，T，p)； //在左子樹中繼續查找
                        else SearchBST(T—>rchild，key，T，p)；//在右子樹中繼續查找
    }//SearchBST

插入：
（1）、首先執行查找算法，找出被插結點的父親結點。沒找到則新建子結點

（2）、判斷被插結點是其父親結點的左、右兒子。將被插結點作為葉子結點插入。

（3）、若二叉樹為空。則首先單獨生成根結點

基于BOOL SearchBST(BiTree *T，KeyType key，BiTree *f，BiTree &p)的插入算法
相當于新建子樹。
 //當二叉排序樹T中不存在關鍵字等于e.key的數據元素時,插入e并返回TRUE，否則返回FALSE
Status Insert BST(BiTree &T，ElemType e)
{
            if(!SearchBST(T，e.key，NULL，p) ) //返回P為插入的結點點
        { //先查找，不成功新建結點
            s=(BiTree)malloc(sizeof(BiTNode))；
            s->data=e； s->lchild= s->rchild=NULL；
            if (!p) T = s； //被插結點*s為新的根結點 ，原樹為空
            else if (e.key<p->data.key) p->lchild=s； //被插結點*s為左孩子
                    else p—>rchild=s //被插結點*s為右孩子
            return TRUE；
          }
        else 
      return FALSE; //樹中已有關鍵字相同的結點，不再插入
    }// Insert BST

  void InsertBST(BSTree *Tptr，KeyType key)
      {
//若二叉排序樹 *Tptr中沒有關鍵字為key，則插入，否則直接返回
        BSTNode *f，*p=*TPtr； //p的初值指向根結點
        while(p){ //查找插入位置
          if(p->key==key) return；//樹中已有key，無須插入
          f=p； //f保存當前查找的結點
          p=(key<p->key)?p->lchild：p->rchild；
            //若key<p->key，則在左子樹中查找，否則在右子樹中查找
         } //endwhile
         //f為插入的結點
        p=(BSTNode *)malloc(sizeof(BSTNode))；
        p->key=key； p->lchild=p->rchild=NULL； //生成新結點
        if(*TPtr==NULL) //原樹為空
           *Tptr=p； //新插入的結點為新的根
        else //原樹非空時將新結點關p作為關f的左孩子或右孩子插入
          if(key<f->key)
            f->lchild=p；
          else f->rchild=p；
       } //InsertBST

4、刪除算法
①刪除操作的一般步驟
(1) 進行查找
    　查找時，令p指向當前訪問到的結點，parent指向其雙親(其初值為NULL)。若樹中找不到被刪結點則返回，否則被刪結點是*p。
(2) 刪去*p。
    　刪*p時，應將*p的子樹(若有)仍連接在樹上且保持BST性質不變。按*p的孩子數目分三種情況進行處理。

②刪除*p結點的三種情況
(1)*p是葉子(即它的孩子數為0)
    　無須連接*p的子樹，只需將*p的雙親*parent中指向*p的指針域置空即可。

(2)*p只有一個孩子*child
    　只需將*child和*p的雙親直接連接后，即可刪去*p。
  注意：
    　*p既可能是*parent的左孩子也可能是其右孩子，而*child可能是*p的左孩子或右孩子，故共有4種狀態。
(3)*p有兩個孩子
    　先令q=p，將被刪結點的地址保存在q中；然后找*q的中序后繼*p，并在查找過程中仍用parent記住*p的雙親位置。*q的中序后繼*p一定是*q的右子樹中最左下的結點，它無左子樹。因此，可以將刪去*q的操作轉換為刪去的*p的操作，即在釋放結點*p之前將其數據復制到*q中，就相當于刪去了*q。
③二叉排序樹刪除算法
分析：
    　上述三種情況都能統一到情況(2)，算法中只需針對情況(2)處理即可。
    　注意邊界條件：若parent為空，被刪結點*p是根，故刪去*p后，應將child置為根。


算法：刪除關鍵字為key的結點
void DelBSTNode(BSTree *Tptr，KeyType key)
 {
//在二叉排序樹*Tptr中刪去關鍵字為key的結點
  BSTNode *parent=NUll，*p=*Tptr，*q，*child；
  while(p)
{ 
     //從根開始查找關鍵字為key的待刪結點
    if(p->key==key) break；//已找到，跳出查找循環
    parent=p； //parent指向*p的雙親
    p=(key<p->key)?p->lchild：p->rchild； //在關p的左或右子樹中繼續找
 } 
//注意：也可以使用基于BOOL SearchBST(BiTree *T，KeyType key，BiTree *f，BiTree &p)的查找算法
//結果是  parent 記錄了要刪除結點的父結點，p指向要刪除的結點

      if(!p) return； //找不到被刪結點則返回
     q=p； //q記住被刪結點*p
     if(q->lchild && q->rchild) //*q的兩個孩子均非空，故找*q的中序后繼*p
    for(parent=q，p=q->rchild； p->lchild； parent=p，p=p=->lchild)；
  //現在情況(3)已被轉換為情況(2)，而情況(1)相當于是情況(2)中child=NULL的狀況
    child=(p->lchild)?p->lchild：p->rchild；//若是情況(2)，則child非空；否則child為空
    if(!parent) //*p的雙親為空，說明*p為根，刪*p后應修改根指針
      *Tptr=child； //若是情況(1)，則刪去*p后，樹為空；否則child變為根
    else{ //*p不是根，將*p的孩子和*p的雙親進行連接，*p從樹上被摘下
      if(p==parent->lchild) //*p是雙親的左孩子
        parent->lchild=child； //*child作為*parent的左孩子
      else parent->rchild=child； //*child作為 parent的右孩子
      if(p!=q) //是情況(3)，需將*p的數據復制到*q
        q->key=p->key； //若還有其它數據域亦需復制
     } //endif
    free(p)； /釋放*p占用的空間
  } //DelBSTNode
給出三種情況的不同算法
第一種：
btree * DelNode(btree *p)
{
      if (p->lchild)
      {
            btree *r = p->lchild;   //r指向其左子樹;
        while(r->rchild != NULL)//搜索左子樹的最右邊的葉子結點r
        {
            r = r->rchild;
        }
            r->rchild = p->rchild;
            btree *q = p->lchild;   //q指向其左子樹;
            free(p);
            return q;
      }
      else
      {
            btree *q = p->rchild;   //q指向其右子樹;
            free(p);
            return q;
      }
}
第二種：
btree * DelNode(btree *p)
{
      if (p->lchild)
      {
            btree *r = p->lchild;   //r指向其左子樹;
            btree *prer = p->lchild;   //prer指向其左子樹;
        while(r->rchild != NULL)//搜索左子樹的最右邊的葉子結點r
        {
                  prer = r;
            r = r->rchild;
        }

        if(prer != r)//若r不是p的左孩子，把r的左孩子作為r的父親的右孩子
        {
                  prer->rchild = r->lchild;
                  r->lchild = p->lchild; //被刪結點p的左子樹作為r的左子樹
            }
        r->rchild = p->rchild; //被刪結點p的右子樹作為r的右子樹

            free(p);
            return r;
      }
      else
      {
            btree *q = p->rchild;   //q指向其右子樹;
            free(p);
            return q;
      }
}

哈夫曼樹定義為：給定n個權值作為n個葉子結點，構造一棵二叉樹，若帶權路徑長度達到最小，稱這樣的二叉樹為最優二叉樹，也稱為哈夫曼樹(Huffman tree)。
1、那么什么是權值？什么是路徑長度？什么是帶權路徑長度呢？
權值：哈夫曼樹的權值是自己定義的，他的物理意義表示數據出現的次數、頻率。可以用樹的每個結點數據域data存放一個特定的數表示它的值。

路徑長度：在一棵樹中，從一個結點往下可以達到的孩子或子孫結點之間的通路，稱為路徑。通路中分支的數目稱為路徑長度。若規定根結點的層數為1，則從根結點到第L層結點的路徑長度為L-1。

結點的帶權路徑長度為：從根結點到該結點之間的路徑長度與該結點的權的乘積。  樹中所有葉子節點的帶權路徑長度之和，WPL=sigma(w*l)

2、哈夫曼樹的構造過程。（結合圖例）
假設有n個權值，則構造出的哈夫曼樹有n個葉子結點。 n個權值分別設為 w1、w2、…、wn，則哈夫曼樹的構造規則為：

　　(1) 將w1、w2、…，wn看成是有n 棵樹的森林(每棵樹僅有一個結點)；

　　(2) 在森林中選出兩個根結點的權值最小的樹合并，作為一棵新樹的左、右子樹，且新樹的根結點權值為其左、右子樹根結點權值之和；

　　(3)從森林中刪除選取的兩棵樹，并將新樹加入森林；

　　(4)重復(2)、(3)步，直到森林中只剩一棵樹為止，該樹即為所求得的哈夫曼樹

3、哈夫曼樹的應用：哈夫曼編碼（前綴編碼）
哈夫曼編碼

在數據通信中，通常需要把要傳送的文字轉換為由二進制字符0和1組成的二進制串，這個過程被稱之為編碼(Encoding)。例如，假設要傳送的電文為DCBBADD，電文中只有A、B、C、D四種字符，若這四個字符采用表(a)所示的編碼方案，則電文的代碼為11100101001111，代碼總長度為14。若采用表(b) 所示的編碼方案，則電文的代碼為0110101011100，代碼總長度為13。

字符集的不同編碼方案

哈夫曼樹可用于構造總長度最短的編碼方案。具體構造方法如下：
設需要編碼的字符集為{d1,d2,…,dn}，各個字符在電文中出現的次數或頻率集合為{w1,w2,…,wn}。以d1,d2,…,dn作為葉子結點，以w1,w2,…,wn作為相應葉子結點的權值來構造一棵哈夫曼樹。規定哈夫曼樹中的左分支代表0，右分支代表1，則從根結點到葉子結點所經過的路徑分支組成的0和1的序列便為該結點對應字符的編碼就是哈夫曼編碼(Huffman Encoding)。

在建立不等長編碼中，必須使任何一個字符的編碼都不是另一個編碼的前綴，這樣才能保證譯碼的唯一性。例如，若字符A的編碼是00，字符B的編碼是001，那么字符A的編碼就成了字符B的編碼的后綴。這樣，對于代碼串001001，在譯碼時就無法判定是將前兩位碼00譯成字符A還是將前三位碼001譯成B。這樣的編碼被稱之為具有二義性的編碼，二義性編碼是不唯一的。而在哈夫曼樹中，每個字符結點都是葉子結點，它們不可能在根結點到其它字符結點的路徑上，所以一個字符的哈夫曼編碼不可能是另一個字符的哈夫曼編碼的前綴，從而保證了譯碼的非二義性。

下圖就是電文DCBBADD的哈夫曼樹：

4、哈夫曼樹的實現

由哈夫曼樹的構造算法可知，用一個數組存放原來的n個葉子結點和構造過程中臨時生成的結點，數組的大小為2n-1。所以，哈夫曼樹類HuffmanTree中有兩個成員字段：data數組用于存放結點，leafNum表示哈夫曼樹葉子結點的數目。結點有四個域，一個域weight，用于存放該結點的權值；一個域lChild，用于存放該結點的左孩子結點在數組中的序號；一個域rChild，用于存放該結點的右孩子結點在數組中的序號；一個域parent，用于判定該結點是否已加入哈夫曼樹中。

哈夫曼樹結點的結構為：| 數據 | weight | lChild | rChild | parent |

     public class Node
    {
        char c; //存儲的數據，為一個字符
        private double weight; //結點權值
        private int lChild; //左孩子結點
        private int rChild; //右孩子結點
        private int parent; //父結點
        //結點權值屬性
        public double Weight
        {
            get
            {
                return weight;
            }
            set
            {
                weight = value;
            }
        }
        //左孩子結點屬性
        public int LChild
        {
            get
            {
                return lChild;
            }
            set
            {
                lChild = value;
            }
        }
        //右孩子結點屬性
        public int RChild
        {
            get
            {
                return rChild;
            }
            set
            {
                rChild = value;
            }
        }
        //父結點屬性
        public int Parent
        {
            get
            {
                return parent;
            }
            set
            {
                parent = value;
            }
        }
        //構造器
        public Node()
        {
            weight = 0;
            lChild = -1;
            rChild = -1;
            parent = -1;
        }
        //構造器
        public Node(double weitht)
        {
            this.weight = weitht;
            lChild = -1;
            rChild = -1;
            parent = -1;
        }

        //構造器
        public Node(int w, int lc, int rc, int p)
        {
            weight = w;
            lChild = lc;
            rChild = rc;
            parent = p;
        }
    }

    public class HuffmanTree
    {
        private Node[] data; //結點數組
        private int leafNum; //葉子結點數目
        //索引器
        public Node this[int index]
        {
            get
            {
                return data[index];
            }
            set
            {
                data[index] = value;
            }
        }
        //葉子結點數目屬性
        public int LeafNum
        {
            get
            {
                return leafNum;
            }
            set
            {
                leafNum = value;
            }
        }
        //構造器
        public HuffmanTree(int n)
        {
            data = new Node[2 * n - 1];
            leafNum = n;
        }
        //創建哈夫曼樹
        public void Create(Node[] datain)
        {
            double minL, minR;
            minL = minR = double.MaxValue;
            int lchild, rchild;
            lchild = rchild = -1;

            int length = data.Length;
            //初始化哈夫曼樹
            for (int i = 0; i < length; i++)
                data[i] = new Node();
            for (int i = 0; i < datain.Length; i++)
                data[i] = datain[i];

            //處理n個葉子結點，建立哈夫曼樹
            for (int i = leafNum; i < length; i++)
            {
                //在全部結點中找權值最小的兩個結點
                for (int j = 0; j < i; j++)
                {
                    if (data[j].Parent == -1)
                    {
                        if (data[j].Weight < minL)
                        {
                            minR = minL;
                            minL = data[j].Weight;
                            rchild = lchild;
                            lchild = j;
                        }
                        else if (data[j].Weight < minR)
                        {
                            minR = data[j].Weight;
                            rchild = j;
                        }
                    }
                }
                data[lchild].Parent = data[rchild].Parent = i;
                data[i].Weight = minL + minR;
                data[i].LChild = lchild;
                data[i].RChild = rchild;
            }
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            HuffmanTree tree = new HuffmanTree(5);
            Node[] nodes = new Node[] { new Node(1), new Node(2), new Node(2.5d), new Node(3), new Node(2.6d) };
            tree.Create(nodes);

            Console.ReadLine();
        }
    }

/////////////////////////////節選自網絡上的資料、

優先隊列是不同于先進先出隊列的另一種隊列。每次從隊列中取出的是具有最高優先權的元素。每個元素都有一個優先權或值
/////用堆實現優先隊列
1、把優先隊列中的元素按優先級大小組織成堆，堆頂元素具有最大優先級。
2、優先隊列的插入與刪除可以用堆的插入與刪除實現。
3、優先隊列在定義為priority_queue ，在STL中#include<queue> 中實現、
 priority_queue<int, vector<int>, greater<int> >qi2;

其中
第二個參數為容器類型。
第三個參數為比較函數。

估計還要問問：什么是堆，什么是堆排序？堆與計算機分配內存的堆相同嗎？
很多資料給出：堆的定義是
（1）、n個關鍵字序列（Kl，K2，…，Kn）稱為(Heap)，當且僅當該序列滿足如下性質(簡稱為堆性質)：
ki≤K2i且ki≤K2i+1 或  Ki≥K2i且ki≥K2i+1 (1≤i≤ n) //ki相當于二叉樹的非葉結點，K2i則是左孩子，k2i+1是右孩子 

（2）若將此序列所存儲的向量R[1..n]看做是一棵完全二叉樹的存儲結構，則堆實質上是滿足如下性質的完全二叉樹： 　　樹中任一非葉結點的關鍵字均不大于(或不小于)其左右孩子(若存在)結點的關鍵字。

（3）、根結點(亦稱為堆頂)的關鍵字是堆里所有結點關鍵字中最小者的堆稱為小根堆，又稱最小堆。根結點(亦稱為堆頂)的關鍵字是堆里所有結點關鍵字中最大者，稱為大根堆，又稱最大堆。

（4）、堆中任一子樹亦是堆。
（5）、堆可以視為一棵完全的二叉樹，完全二叉樹的一個“優秀”的性質是，除了最底層之外，每一層都是滿的，這使得堆可以利用數組來表示（普通的一般的二叉樹通常用鏈表作為基本容器表示），每一個結點對應數組中的一個元素。

那么堆排序呢？
堆排序其實就是將一組無序的序列變成堆的過程、下面我們一起看看堆排序的算法。
2、堆排序
以最大堆為例，步驟為：
　　① 先將初始文件R[1..n]建成一個大根堆,此堆為初始的無序區 　　② 再將關鍵字最大的記錄R[1](即堆頂)和無序區的最后一個記錄R[n]交換，由此得到新的無序區R[1..n-1]和有序區R[n]，且滿足R[1..n-1].keys≤R[n].key 　　③由于交換后新的根R[1]可能違反堆性質，故應將當前無序區R[1..n-1]調整為堆。然后再次將R[1..n-1]中關鍵字最大的記錄R[1]和該區間的最后一個記錄R[n-1]交換，由此得到新的無序區R[1..n-2]和有序區R[n-1..n]，且仍滿足關系R[1..n-2].keys≤R[n-1..n].keys，同樣要將R[1..n-2]調整為堆。 　　…… 　　直到無序區只有一個元素為止。  
將一個無序的序列建成堆的過程實際上是一個反復篩選的過程。若將此序列看作是一棵完全二叉樹，則最后一個非終端結點是[n/2](不大于n/2的整數），因此篩選過程只需從[n/2]開始。要建成一個大頂堆，即先選擇一個值最大的元素并與序列中的最后一個元素交換，然后對序列前n-1元素進行篩選，從新調整為一個大頂堆，直到結束。 
算法描述如下： 
  
typedef   int[]   Elem;//采用順序存儲表示完全二叉樹 

void   HeapAdjust(Elem   &e,int   s,int   m) 
{//e中s...m的元素除e[s]之外已經滿足堆的定義（e[i] <=e[2*i]&&e[i] <=e[2*i+1] 
  //或e[i]> =e[2*i]&&e[i]> =e[2*i+1]),調整e[s]使的e[s...m]成為一個大頂堆。 
      selem=e[s]; 
      for(i=2*s;i <=m;i*=2)//沿著值較大的元素（結點）向下篩選 
      { 
            if(i <m   &&   e[i] <e[i+1])++i;//i為值較大的元素下標 
            if(selem> =e[i])break; 
            e[s]=e[i]; 
            s=i; 
        } 
      e[s]=selem; 
} 

void   HeapSort(Elem   &e) 
{//對順序表排序 
    for(i=e.length/2;i> 0;--i) 
            HeapAdjust(e,i,e.length); 
    for(i=e.length;i> 1;--i) 
    { 
          temp=e[1];                     //將堆中的最后一個元素與第一個元素交換 
          e[1]=e[i]; 
          e[i]=temp; 
          HeapAdjust(H,1,i-1);//調整1..i-1的元素成為大頂堆 
      }     
}


/////////////////////////////////////////////////////////////
使用堆排序注意的問題：：：
1、序列是從1開始的。，注意定義，R[1..n]，故要空出R[0]。
2、堆排序算法分為兩部分：建立大頂堆和排序。
3、排序的最壞時間復雜度為O(nlogn)。堆序的平均性能較接近于最壞性能。
4、由于建初始堆所需的比較次數較多，所以堆排序不適宜于記錄數較少的文件。 5、　堆排序是就地排序，輔助空間為O(1)， 它是不穩定的排序方法。

問題：當序列空間為R[0,1....n]；時，該怎么去使用堆排序呢？元素后移一位，這明顯不是一個好方法。

數據對齊，是指數據所在的內存地址必須是該數據長度的整數倍。比如DWORD數據的內存其實地址能被4除盡，WORD數據的內存地址能被2除盡。x86 CPU能直接訪問對齊的數據，當它試圖訪問一個未對齊的數據時，會在內部進行一系列的調整，這些調整對于程序來說是透明的，但是會降低運行速度，所以編譯器在編譯程序時會盡量保持數據對齊。

C/C++編譯器在內存分配時也保持了數據對齊，請看下例：

struct{

short a1;

short a2;

short a3;

}A;

struct{

long  a1;

short a2;

}B;

cout<<sizeof(A)<<","<<sizeof(B)<<endl;//其它代碼略去

結構體A和B的大小分別是多少呢？

默認情況下，為了方便對結構體元素的訪問和管理，當結構體內的元素都小于處理器長度的時候，便以結構體里面最長的數據為對齊單位，也就是說，結構體的長度一定是最長數據長度的整數倍。

如果結構體內部存在長度大于處理器位數時就以處理器位數為對齊單位。

結構體內類型相同的連續元素將存在連續的空間內，和數組一樣。

上例中:

A有3個short類型變量，各自占2字節，總和為6，6是2的倍數，所以sizeof(A)=6;

B有一個long類型變量，占4字節，一個short類型的變量，占2字節，總和6不是最大長度4的倍數，所以要補空字節以增至8實現對齊，所以sizeof(8)=8。

 

在C++類的設計中遵循同樣的道理，但需注意，空類需要占1個字節，靜態變量(static)由于在棧中分配，不在sizeof計算范圍內。

多態性，這個面向對象編程領域的核心概念，本身的內容博大精深，要以一文說清楚實在是不太可能。加之作者本人也還在不斷學習中，水平有限。因此本文只能描一下多態的輪廓，使讀者能夠了解個大概。如果有描的不準的地方，歡迎指出，或與作者探討（作者Email：nicrosoft@sunistudio.com） 
        
        首先，什么是多態（Polymorphisn）？按字面的意思就是“多種形狀”。我手頭的書上沒有找到一個多態的理論性的概念的描述。暫且引用一下Charlie   Calverts的對多態的描述吧——多態性是允許你將父對象設置成為和一個或更多的他的子對象相等的技術，賦值之后，父對象就可以根據當前賦值給它的子對象的特性以不同的方式運作（摘自“Delphi4   編程技術內幕”）。簡單的說，就是一句話：允許將子類類型的指針賦值給父類類型的指針。多態性在Object   Pascal和C++中都是通過虛函數（Virtual   Function）實現的。 
        
        好，接著是“虛函數”（或者是“虛方法”）。虛函數就是允許被其子類重新定義的成員函數。而子類重新定義父類虛函數的做法，稱為“覆蓋”（override），或者稱為“重寫”。 

        這里有一個初學者經常混淆的概念。覆蓋（override）和重載（overload）。上面說了，覆蓋是指子類重新定義父類的虛函數的做法。而重載，是指允許存在多個同名函數，而這些函數的參數表不同（或許參數個數不同，或許參數類型不同，或許兩者都不同）。其實，重載的概念并不屬于“面向對象編程”，重載的實現是：編譯器根據函數不同的參數表，對同名函數的名稱做修飾，然后這些同名函數就成了不同的函數（至少對于編譯器來說是這樣的）。如，有兩個同名函數：function   func(p:integer):integer;和function   func(p:string):integer;。那么編譯器做過修飾后的函數名稱可能是這樣的：int_func、str_func。對于這兩個函數的調用，在編譯器間就已經確定了，是靜態的（記住：是靜態）。也就是說，它們的地址在編譯期就綁定了（早綁定），因此，重載和多態無關！真正和多態相關的是“覆蓋”。當子類重新定義了父類的虛函數后，父類指針根據賦給它的不同的子類指針，動態（記住：是動態！）的調用屬于子類的該函數，這樣的函數調用在編譯期間是無法確定的（調用的子類的虛函數的地址無法給出）。因此，這樣的函數地址是在運行期綁定的（晚邦定）。結論就是：重載只是一種語言特性，與多態無關，與面向對象也無關！ 
        
        引用一句Bruce   Eckel的話：“不要犯傻，如果它不是晚邦定，它就不是多態。” 
        
        那么，多態的作用是什么呢？我們知道，封裝可以隱藏實現細節，使得代碼模塊化；繼承可以擴展已存在的代碼模塊（類）；它們的目的都是為了——代碼重用。而多態則是為了實現另一個目的——接口重用！而且現實往往是，要有效重用代碼很難，而真正最具有價值的重用是接口重用，因為“接口是公司最有價值的資源。設計接口比用一堆類來實現這個接口更費時間。而且接口需要耗費更昂貴的人力的時間。” 
        
        其實，繼承的為重用代碼而存在的理由已經越來越薄弱，因為“組合”可以很好的取代繼承的擴展現有代碼的功能，而且“組合”的表現更好（至少可以防止“類爆炸”）。因此筆者個人認為，繼承的存在很大程度上是作為“多態”的基礎而非擴展現有代碼的方式了。 
        
        什么是接口重用？我們舉一個簡單的例子，假設我們有一個描述飛機的基類（Object   Pascal語言描述，下同）： 
        type 
                plane   =   class 
                public 
                        procedure   fly();   virtual;   abstract;   //起飛純虛函數 
                        procedure   land();   virtual;   abstract;   //著陸純虛函數 
                        function   modal()   :   string;   virtual;   abstract;   //查尋型號純虛函數 
                end; 
        
        然后，我們從plane派生出兩個子類，直升機（copter）和噴氣式飛機（jet）： 
                copter   =   class(plane) 
                private 
                        fModal   :   String; 
                public 
                        constructor   Create(); 
                        destructor   Destroy();   override; 
                        procedure   fly();   override; 
                        procedure   land();   override; 
                        function   modal()   :   string;   override; 
                end; 
        
                jet   =   class(plane) 
                private 
                        fModal   :   String; 
                public 
                        constructor   Create(); 
                        destructor   Destroy();   override; 
                        procedure   fly();   override; 
                        procedure   land();   override; 
                        function   modal()   :   string;   override; 
                end; 
        
        現在，我們要完成一個飛機控制系統，有一個全局的函數   plane_fly，它負責讓傳遞給它的飛機起飛，那么，只需要這樣： 
        procedure   plane_fly(const   pplane   :   plane); 
        begin 
                pplane.fly(); 
        end; 
        就可以讓所有傳給它的飛機（plane的子類對象）正常起飛！不管是直升機還是噴氣機，甚至是現在還不存在的，以后會增加的飛碟。因為，每個子類都已經定義了自己的起飛方式。 
        
        可以看到   plane_fly函數接受參數的是   plane類對象引用，而實際傳遞給它的都是   plane的子類對象，現在回想一下開頭所描述的“多態”：多態性是允許你將父對象設置成為和一個或更多的他的子對象相等的技術，賦值之后，父對象就可以根據當前賦值給它的子對象的特性以不同的方式運作。 
        
        很顯然，parent   =   child;   就是多態的實質！因為直升機“是一種”飛機，噴氣機也“是一種”飛機，因此，所有對飛機的操作，都可以對它們操作，此時，飛機類就作為一種接口。 
        
        多態的本質就是將子類類型的指針賦值給父類類型的指針（在OP中是引用），只要這樣的賦值發生了，多態也就產生了，因為實行了“向上映射”。






多態性

　　是允許將父對象設置成為和一個或多個它的子對象相等的技術，比如Parent:=Child； 多態性使得能夠利用同一類(基類)類型的指針來引用不同類的對象,以及根據所引用對象的不同,以不同的方式執行相同的操作.

c++中多態更容易理解的概念為

　　允許父類指針或名稱來引用子類對象，或對象方法，而實際調用的方法為對象的類類型方法。
作用　　
把不同的子類對象都當作父類來看，可以屏蔽不同子類對象之間的差異，寫出通用的代碼，做出通用的編程，以適應需求的不斷變化。

　　賦值之后，父對象就可以根據當前賦值給它的子對象的特性以不同的方式運作。也就是說，父親的行為像兒子，而不是兒子的行為像父親。

　　舉個例子：從一個基類中派生，響應一個虛命令，產生不同的結果。

　　比如從某個基類繼承出多個對象，其基類有一個虛方法Tdoit，然后其子類也有這個方法，但行為不同，然后這些子對象中的任何一個可以賦給其基類的對象，這樣其基類的對象就可以執行不同的操作了。實際上你是在通過其基類來訪問其子對象的，你要做的就是一個賦值操作。

　　使用繼承性的結果就是可以創建一個類的家族，在認識這個類的家族時，就是把導出類的對象當作基類的對象，這種認識又叫作upcasting。這樣認識的重要性在于：我們可以只針對基類寫出一段程序，但它可以適應于這個類的家族，因為編譯器會自動就找出合適的對象來執行操作。這種現象又稱為多態性。而實現多態性的手段又叫稱動態綁定(dynamic binding)。

　　簡單的說，建立一個父類的對象，它的內容可以是這個父類的，也可以是它的子類的,當子類擁有和父類同樣的函數，當使用這個對象調用這個函數的時候，定義這個對象的類（也就是父類）里的同名函數將被調用，當在父類里的這個函數前加virtual關鍵字，那么子類的同名函數將被調用。

//轉自網友博客、
1、 派生類對象與普通類對象的相同之處在于，可以直接訪問該類的所有對象（包括this指針指向的對象和其他對象）的protected和private成員（包括其基類成員）。不同之處在于派生類對象只能訪問其對應基類對象的protected成員（有隱式this指針傳遞），而不能訪問其基類的其他對象的protect成員，而普通類對象則也可以直接訪問該類所有對象的成員。

 

2、 在C++中，基類指針只能訪問在該基類中被聲明（或繼承）的數據成員和成員函數（包括虛擬成員函數），而與它可能指向的實際對象無關，所以如果需要用基類指針來訪問一個沒有在該基類中聲明但是又在其派生類中定義了的成員，則需要執行dynamic_cast來完成從基類指針到派生類指針的安全向下轉換。把一個成員聲明為虛擬的，只推延了“在程序執行期間根據指針指向的實際類類型，對于要調用實例的解析過程”

 

3、 關于基類，派生類的相關補充：

1、 派生表中指定的類必須先被定義好，方可被指定為基類。

2、 派生類的前向聲明不能包括其派生表，而只需要類名即可。

3、 缺省的繼承是private。

4、 繼承而來的派生類的虛擬函數一般加上virtual較好，也可以省略。但基類中一定要聲明為virtual。

5、 對于基類的靜態成員，所有派生類對象都引用基類創建的這個相同，單一，共享的靜態成員，而不是創建該派生類的另一個獨立的靜態成員。

6、 友員關系不會被繼承，派生類沒有成為“向它的基類授權友誼的類”的友員。

 

4、 繼承機制下，派生類對象的構造函數（析構函數）調用順序為：

1、 基類（子對象的）構造函數，若有多個基類，則以類派生表中出現的順序為序。

2、 成員類對象的構造函數，若有多個成員類對象，則以它們在類定義中被聲明的順序為序。

3、派生類自己的構造函數。

4、派生類對象的析構函數的調用順序與它的構造函數相反。繼承機制下，析構函數的行為如下：派生類的析構函數先被調用，再靜態調用基類的析構函數（從直接基類開始）。注意一般基類的析構函數不應該是protected，因為虛擬函數承接了“調用者所屬類類型的訪問級別”。作為一般規則，我們建議將類層次結構的根基類（聲明了一個或多個虛擬函數）的析構函數聲明為虛擬的。

 

5、 關于繼承機制下基類構造函數（析構函數）相關的幾點說明：

1、 作為一般規則，派生類構造函數應不能直接向一個基類的數據成員賦值，而是要把值傳遞給適當的基類構造函數來達到初始化賦值的目的。（一般是通過成員初始化表的方式）

2、 若基類不用于創建對象，則最好將其構造函數放在protect區，只允許其派生類對象調用；若基類只允許創建某一個特定的派生類類型的對象，則應該將基類的構造函數放在private區，并將此特定的派生類聲明為該基類的友元來達到目的。

3、 派生類并不繼承基類的構造函數，每個派生類都必須提供自己的構造函數集，派生類的構造函數只能合法的調用其直接基類的構造函數。（注意這里虛擬繼承提供了一個特例：虛擬基類的初始化變成了最終派生類的責任）。

 

6、 關于虛擬函數的相關

1、 必須使用指針或者引用來支持虛擬函數機制（面向對象程序設計），基類對象由于其靜態編譯，故不會保留派生類的類型身份。

2、 第一次引入虛擬函數的基類時，必須在類體中將虛擬函數聲明為virtual，但若在該基類外部定義該虛擬函數時不能指定virtual。該基類的派生類中該虛擬函數virtual可加可不加，但從多重繼承考慮，最好加上。

3、 派生類改寫的基類虛擬函數，其原型必須與基類虛擬函數完全匹配（包括const和返回值），但返回值有個特例：派生類實例的返回值可以是基類實例返回類型的公有派生類類型。

4、 純虛擬函數（聲明后緊跟=0，函數定義可寫可不寫）只是提供了一個可被其派生類改寫的接口，其本身不能通過虛擬機制被調用，但可以靜態調用（寫了函數定義的虛基類的純虛擬函數）。一般來說，虛擬函數的靜態調用的目的是為了效率（避免動態綁定）。

5、 包含（或繼承）了一個或多個純虛擬函數的類被編譯器識別為抽象基類，抽象基類不能用來創建獨立的類對象，只能作為子對象出現在后續的派生類中。

6、通過基類指針來調用的虛擬函數的真正實例是在運行時刻確定的。但傳給虛擬函數的缺省實參是在編譯時刻根據被調用函數的對象的類型決定的（也即是若通過基類指針或引用調用派生類實例的虛擬函數，則傳遞給它的缺省實參是由基類指定的）。

 

7、 虛擬繼承和多繼承相關：

1、 虛擬繼承主要實為了解決繼承了多個基類實例，但是只需要一份單獨的共享實例的情況。

2、 非虛擬派生中，派生類只能顯式的初始化其直接基類（即派生類只能調用其直接基類的構造函數），而在虛擬派生中，虛擬基類的初始化變成了最終派生類的責任，這個最終派生類是由每個特定的類對象聲明來決定的，其非虛擬基類的初始化同非虛擬派生一樣，只能由其直接派生類完成。（即中間派生類的對于虛擬基類構造函數的調用被抑制）。

3、 虛擬繼承下構造函數的調用順序按直接基類的聲明順序，對每個繼承子樹作深度優先遍歷。第一步按此順序調用所有虛擬基類的構造函數；第二步按此順序調用非虛擬基類的構造函數。析構函數的調用順序與構造函數相反。

4、 虛擬基類成員的可視性，對于虛擬基類成員的繼承比該成員后來重新定義的實例權值（優先級）小，故特化的派生類實例名覆蓋了共享的虛擬基類的實例名。而在非虛擬派生下的解析引用過程，每個繼承得到的實例都有相同的權值（優先級）。

5、 繼承下派生類的類域被嵌套在基類類域中，若一個名字在派生類域中沒有被解析出來，則編譯器在外圍基類域中查找該名字定義。在多繼承下，名字解析查找過程為先是在本類類域中查找，再對繼承子樹中的所有基類同時查找，每個繼承得到的實例都有相同的權值（優先級）。若在兩個或多個基類子樹中都找到了該名字，則對其的使用是二義的。

     摘要: 一、      什么是設計模式。 毫無疑問，設計模式是前人總結下來，一些設計經驗經過被反復使用、并為多數人知曉、經過分類編目。模式是一種問題的解決思路，它已經適用于一個實踐環境，并且可以適用于其他壞境。 最終由GoF總結出23種設計模式。 二、      為什么要使用。 根本原因是為了代碼復...  閱讀全文      摘要: 1、什么是Bridge模式？這個問題我用一言兩語實在無法概括其根本。不過我是這樣分析的：①、對象這個概念可以認為是由“屬性”和“行為”兩個部分組成的。屬性我們可以認為是一種靜止的，是一種抽象；一般情況下，行為是包含在一個對象中，但是，在有的情況下，我們需要將這些行為也進行歸類，形成一個總的行為接口，這就是橋模式的用處。②、Br...  閱讀全文