二叉樹

每個結點最多有兩個孩子，其余結構和樹的結構一樣，

1. 二叉樹特點

二叉樹的特點有：

每個結點最多有兩棵子樹，所以二叉樹中不存在度大于2的結點，
左子樹和右子樹是有順序的，次序不能任意顛倒，
即使樹中某結點只有一棵子樹，也要區分它是左子樹還是右子樹，

二叉樹有五種基本形態：

空二叉樹；
只有一個根節點；
根節點只有左子樹；
根節點只有右子樹；
根節點既有左子樹又有右子樹，

2. 特殊二叉樹

斜樹，所有結點只有左子樹（或右子樹）的二叉樹稱為左斜樹（右斜樹），
滿二叉樹，所有結點（除了葉子結點）都存在左子樹和右子樹，且所有葉子結點均在同一層上，

滿二叉樹的特點有：
- 葉子只能出現在最下一層；
- 非葉子結點的度一定為2；
- 在同樣深度的二叉樹中，滿二叉樹的結點個數最多，葉子數最多，
完全二叉樹，對一棵具有n個結點的二叉樹按層序編號，如果編號為i(1≤i≤n)的結點與同樣深度的滿二叉樹中編號為i的結點在二叉樹中位置完全相同，這個二叉樹為完全二叉樹，

圖

完全二叉樹的特點：
- 葉子結點只能出現最下兩層；
- 最下層的葉子一定集中在左部連續位置；
- 倒數二層，若有葉子結點，一定都在右部連續位置；
- 如果結點度為1，則該結點只有左孩子，即不存在只有右子樹的情況；
- 同樣結點數的二叉樹，完全二叉樹的深度最小，

2. 二叉樹的性質

在二叉樹的第i層上至多有\(2^{i-1} (i≥1)\)?個結點，
深度為k的二叉樹至多有\(2^k-1 (k≥1)\)個結點，
對任何一棵二叉樹T，如果其終端結點數為\(n_0\)，度為2的結點數為\(n_2\)，則\(n_0=n_2+1\)，
具有n個結點的完全二叉樹的深度為\([log_2n]+1\)([x]表示不大于x的最大整數)，
對于具有n個結點的完全二叉樹，其結點按照層序編號，對任意結點\(i (1≤i≤n)\)有：
- 如果\(i=1\)，則結點i是二叉樹的根，無雙親；如果\(i≥1\)，則其雙親結點為\([i/2]\)，
- 如果\(2i>n\)，則結點i無左孩子（結點i為葉子結點）；否則其左孩子是結點2i，
- 如果\(2i+1>n\)，則結點i無右孩子；否則其右孩子是結點\(2i+1\)，

3.二叉樹遍歷

遍歷二叉樹的方法：

先序遍歷
- 首先對根節點進行訪問
- 然后訪問左子樹
- 最后訪問右子樹 DLR模式
2.中序遍歷
- 首先訪問左子樹
- 后訪問根節點
- 最后訪問右子樹 LDR模式
后序遍歷
- 首先訪問左子樹
- 然后訪問右子樹
- 最后訪問根節點 LRD模式

    //先序遍歷DLR
    void PreorderTraverse(BTNode<T> *p) //p為二叉樹的根節點,以下同是
    {
        if (p != NULL)
        {
            this->Visit(p);
            this->PreorderTraverse(p->lchild);
            this->PreorderTraverse(p->rchild);
        }
    }
    //中序遍歷LDR
    void InorderTraverse(BTNode<T> *p)
    {
        if (p != NULL)
        {
            this->InorderTraverse(p->lchild);
            this->Visit(p);
            this->InorderTraverse(p->rchild);
        }
    }
    //后序遍歷LRD
    void Postordertraverse(BTNode<T> *p)
    {
        if (p != NULL)
        {
            this->Postordertraverse(p->lchild);
            this->Postordertraverse(p->rchild);
            this->Visit();
        }
    }

4. 二叉樹遍歷的應用

    //統計葉子結點的數目
    int GetNumOfLeaf(BTNode<T> *p)
    {
        int number = 0;
        if (p == NULL)
            number = 0;
        else if (p->lchild == NULL && p->rchild == NULL)
            number = 1;
        else
            number = this->GetNumOfLeaf(p->lchild) + this->GetNumOfLeaf(p->rchild);
        return number;
    }
    //計算二叉樹的高度
    int GetHeight(BTNode<T> *p)
    {
        int height = 0;
        if (p == NULL)
            height = 0;
        else if (p->lchild == NULL && p->rchild == NULL)
            height = 1;
        else
        {
            int lheight = this->GetHeight(p->lchild) + 1;
            int rheight = this->GetHeight(p->rchild) + 1;
            height = lheight > rheight ? lheight : rheight;
        }
        return height;
    }

5. 中序線索化二叉樹

? 原理：

? 為了節省資源空間，將空閑的指標域給利用起來，將此指標域設為該結點的前驅或后繼指標

如果該結點的左指標域為空，則將此指標域指向該結點的前驅；
如果該結點的右指標域為空，則將此指標域指向該結點的后繼；
為了辨別該結點的左右指標域的指向，需要在結點中加入兩個布爾變數Ltag和Rtag，如果Ltag=0或Rtag=0則表明該結點的左或右孩子存在；否則，指向前驅或后繼指標，

? 實作：

首先遍歷整個二叉樹BinTree，先序，中序，后序都可

if(BinTree!=NULL)
{
    Inordertraverse(BinTree->lchild);
    dosomething;
    Inordertraverse(BinTree->rchild);
}

判斷當前結點的左孩子是否存在，若存在則讓BinTree->Ltag=0；

? 否則BinTree->Ltag=1;BinTree->lchild=pre;(pre為當前結點的前驅結點，就是遍歷的上一個結點)

? 3. 判斷前驅結點pre的右孩子是否存在，若存在則讓BinTree->Rtag=0;

? 否則pre->Rtag=1;pre->rchild=BinTree;

? 4. 令前驅結點pre始終保持在當前結點的上一個結點，即:pre=BinTree;

? 代碼實作：

if(BinTree->lchild==NULL)
{
    BinTree->Ltag=1;
    BinTree->lchild=pre;
}
if(pre!=NULL&&pre->rchild==NULL)
{
    pre->Rtag=1;
    pre->rchild=BinTree;
}
pre=BinTree;

中序線索二叉樹查找某個結點p的前驅結點pre

根據中序遍歷方法LDR可知，結點p的前驅結點應是p的左子樹；
如果該結點的左孩子標志點p->Ltag=1;則該結點的前驅為pre=p->lchild;
如果該結點的左孩子存在即p->Ltag=0;

? 根據中序遍歷的定義可知，結點p的前驅結點應是p的左子樹的“最下右孩子”;

? 用代碼可表示為：

q=p->lchild;
while(q->Rtag==0)
{
    q=q->rchild;
}
pre=q;

? 中序線索二叉樹查找某個結點p的后繼結點next，方法原理同上，

中序線索二叉樹的插入和洗掉操作

? 插入操作：

? 向二叉樹中結點p的右孩子插入結點r，即p->rchild=r;

? 1. 首先遍歷二叉樹，找到結點p

- 如果結點p的右孩子不存在，即p->Rtag=1;
- 則p的后繼變為r，r的后繼變為p原來的后繼p->rchild，r的前驅為p
- 即：r->Ltag=1;r->lchild=p;r->Rtag=1;r->rchild=p->rchild;p->rchild=r;注意順序不能變
- 如果結點p的右孩子存在，即p->Rtag=0;
- 則將結點r變為p結點的右孩子，原來p的右孩子變為r的右孩子
- 則p的后繼將變為r，p為r的前驅
- r的后繼變為右子樹“最下端左孩子”

? 代碼實作：

if(p->Rtag==1)
{
    BTNode<T> *r=new BTNode<T>(Data:data,Ltag:1,Rtag:1,lchild:p,rchild:p->rchild);
    p->rchild=r;
    p->Rtag=0;
}
else
{
    BTNode<T> *r=new BTNode<T>(Data:data,Ltag:1,Rtag:0,lchild:p,rchild:p->rchild);
    p->rchild=r;
    BTNode<T> *q=r->rchild;
    while(q->Ltag==0)
    {
        q=q->lchild;
    }
    q->lchild=r;
}

? 洗掉操作和插入操作類似相同，方法和原理同上，

6. 哈夫曼樹

? 哈夫曼樹是指帶權路徑最小的二叉樹，

? 給定一定的帶權葉子結點，構造哈夫曼樹：

? 1. 在這些結點中尋找兩個權最小的葉子結點，這兩個結點與\(N_1\)結點組成一棵樹，\(N_1\)結點的權變為兩個結點的和；

? 2. 將\(N_1\)結點和其它葉子結點放在一起，在其中找到兩個權最小的樹，組成一棵新樹；

? 3. 注意在組成新樹時，將權相對較小的值作為左孩子；

? 4. 以此類推，重復上述的步驟，最終將得到哈夫曼樹，

? 根據以上的構造可以得到，哈夫曼樹只有度為2的結點和葉子結點，故當哈夫曼樹有n個葉子結點時，其總結點數為2n-1，

? 哈夫曼樹存盤結構：

? 權重雙親左孩子右孩子

? 葉子結點的左孩子和右孩子均為空，

? 哈夫曼樹的應用：

? 哈夫曼編碼：前綴編碼，前綴編碼容易區分，不易相重；縮短編碼長度，便于傳輸常用于壓縮檔案編碼

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/30647.html

標籤：C++

上一篇：圖

下一篇：opencv-11-中值濾波及自適應中值濾波