樹的概念與基本術(shù)語

樹是若干結(jié)點(diǎn)的集合，是由唯一的根和若干棵互不相交的子樹組成的。樹的概念是遞歸的，即在樹的定義中又用到了樹的定義。

結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的子樹個(gè)數(shù)或者分支的個(gè)數(shù)。
樹的度：樹中各結(jié)點(diǎn)度的最大值。
層次：從根開始，根為第一層，根的孩子為第二層。
樹的高度（或者深度）：樹中結(jié)點(diǎn)的最大層次。
結(jié)點(diǎn)的深度：從根結(jié)點(diǎn)到該結(jié)點(diǎn)路徑上的結(jié)點(diǎn)個(gè)數(shù)
結(jié)點(diǎn)的高度：從某結(jié)點(diǎn)往下走可能到達(dá)多個(gè)葉子結(jié)點(diǎn)，對應(yīng)了多條通往這些葉子結(jié)點(diǎn)的路徑，其中最長的那條路徑的長度即為該結(jié)點(diǎn)在樹中的高度。根結(jié)點(diǎn)的高度為樹的高度。
兄弟：同一個(gè)雙親的孩子之間互為兄弟。
堂兄弟：雙親在同一層的結(jié)點(diǎn)互為堂兄弟。
有序樹與無序樹：樹中的結(jié)點(diǎn)的子樹從左到右是有次序的，不能交換，這樣的樹叫做有序樹?？梢噪S便交換的叫做無序樹。
豐滿樹：豐滿樹即理想平衡樹，要求除最底層外，其他層都是滿的。
森林：若干棵互不相交的樹的集合。

樹的存儲結(jié)構(gòu)：

1.順序存儲結(jié)構(gòu)：
樹的順序存儲結(jié)構(gòu)中最簡單直觀的是雙親存儲結(jié)構(gòu)。用一個(gè)整數(shù)數(shù)組來存儲，下標(biāo)就是該結(jié)點(diǎn)，數(shù)組元素的內(nèi)容表示該結(jié)點(diǎn)的雙親結(jié)點(diǎn)。例如3的雙親是1，則tree[3]=1.
樹的雙親存儲結(jié)構(gòu)在克魯斯卡爾算法中有重要應(yīng)用。

2.鏈?zhǔn)酱鎯Y(jié)構(gòu)：
1）孩子存儲結(jié)構(gòu)：孩子存儲結(jié)構(gòu)實(shí)質(zhì)上就是圖的鄰接表存儲結(jié)構(gòu)。樹就是一種特殊的圖。
2）孩子兄弟存儲結(jié)構(gòu)：孩子兄弟存儲結(jié)構(gòu)與樹和森林與二叉樹的相互轉(zhuǎn)換關(guān)系密切。

二叉樹

二叉樹滿足以下定義：

每個(gè)結(jié)點(diǎn)最多只有兩棵子樹，即二叉樹中結(jié)點(diǎn)的度只能為0、1、2
子樹有左右順序之分，不能顛倒

滿二叉樹：如果所有的分支結(jié)點(diǎn)都有左孩子和右孩子結(jié)點(diǎn)，并且葉子結(jié)點(diǎn)都集中在二叉樹的最下一層，則這樣的二叉樹成為滿二叉樹。
完全二叉樹：如果對一棵深度為k，有n個(gè)結(jié)點(diǎn)的二叉樹進(jìn)行編號后，各結(jié)點(diǎn)的編號與深度為k的滿二叉樹中相對位置上的結(jié)點(diǎn)的編號均相同，那么這棵樹就是一棵完全二叉樹。
一棵完全二叉樹一定是由一棵滿二叉樹從右到左，從下到上，挨個(gè)刪除結(jié)點(diǎn)所得到的。如果跳著刪除，則得到的不是完全二叉樹。

二叉樹的主要性質(zhì)：

性質(zhì)1. 非空二叉樹上葉子結(jié)點(diǎn)數(shù)等于雙分支結(jié)點(diǎn)數(shù)加1.
證明：假設(shè)葉子結(jié)點(diǎn)數(shù)為n0，單分支結(jié)點(diǎn)數(shù)為n1，雙分支結(jié)點(diǎn)數(shù)為n2，則總結(jié)點(diǎn)數(shù)為n0+n1+n2。總分支數(shù)為n1+2n2。由于除了根結(jié)點(diǎn)外，其它結(jié)點(diǎn)都有一個(gè)分支指向它，所以總分支數(shù)=總結(jié)點(diǎn)數(shù)-1。得到n1+2n2 = n0 + n1 + n2 - 1。得到：n2 = n0 - 1。

一個(gè)變形：問二叉樹中總的結(jié)點(diǎn)數(shù)為n，則樹中空指針數(shù)為多少？可以將空指針數(shù)看成是葉子結(jié)點(diǎn)，則每個(gè)結(jié)點(diǎn)都是雙分支結(jié)點(diǎn)。根據(jù)性質(zhì)1，葉子結(jié)點(diǎn)數(shù)等于雙分支結(jié)點(diǎn)數(shù)加1，則空指針數(shù)=n+1.

性質(zhì)2. 二叉樹的第i層最多有2^(i-1)個(gè)結(jié)點(diǎn)（i>=1）.
結(jié)點(diǎn)最多的情況即為滿二叉樹的情況，此時(shí)二叉樹每層上的結(jié)點(diǎn)數(shù)構(gòu)成了一個(gè)首項(xiàng)為1，公比為2的等比數(shù)列。通向?yàn)?^(i-1)，i為層號。

性質(zhì)3. 高度（或深度）為k的二叉樹最多有2^k - 1個(gè)結(jié)點(diǎn).
最多的情況還是滿二叉樹，則根據(jù)等比公式求和可得(1-2^k)/(1-2)=2k - 1.
在這里復(fù)習(xí)一下等比數(shù)列求和公式和等差數(shù)列求和公式：

等比數(shù)列求和公式.png

等差數(shù)列求和公式.png

性質(zhì)4. 有n個(gè)結(jié)點(diǎn)的完全二叉樹，對各結(jié)點(diǎn)從上到下，從左到右依次編號，則結(jié)點(diǎn)之間有如下關(guān)系：（i為某結(jié)點(diǎn)a的編號）

如果i不等于1，則a的雙親結(jié)點(diǎn)的編號為i/2向下取整
如果2i<=n，則a的左孩子的編號為2i；如果2i > n，則a無左孩子
如果2i+1 <= n，則a的右孩子編號為2i+1；如果2i+1 > n，則a無右孩子

性質(zhì)5. 函數(shù)catalan( )：給定n個(gè)結(jié)點(diǎn)，能構(gòu)成h(n)種不同的二叉樹，h(n)=C(2n,n)/(n+1)

性質(zhì)6. 具有n個(gè)結(jié)點(diǎn)的完全二叉樹的高度或深度為 (log2n向下取整+1)，或者(log2(n+1)向上取整)

二叉樹的存儲結(jié)構(gòu)

1. 順序存儲結(jié)構(gòu)：
順序存儲結(jié)構(gòu)即用一個(gè)數(shù)組來存儲一棵二叉樹，這種存儲方式最適合于完全二叉樹，用于存儲一般的二叉樹會浪費(fèi)大量存儲空間。
將完全二叉樹中的結(jié)點(diǎn)值按編號依次存入一個(gè)一維數(shù)組中，即完成了一棵二叉樹的順序存儲。如果知道了一個(gè)結(jié)點(diǎn)的下標(biāo)為i，則該結(jié)點(diǎn)的左孩子的下標(biāo)為2i，右孩子為2i+1（當(dāng)其存在時(shí)）。

2. 鏈?zhǔn)酱鎯Y(jié)構(gòu)（二叉鏈表存儲結(jié)構(gòu)）：

typedef struct BTNode {
    char data; //數(shù)據(jù)域，可更改為其他類型
    struct BTNode *lchild;
    struct BTNode *rchild;
};

二叉樹的遍歷算法

二叉樹的遍歷方式有先序遍歷、中序遍歷、后序遍歷和層次遍歷。

1.先序遍歷preorder

根、左、右

void preorder(BTNode *p) {
    if (p != NULL) {
        visit(p); //對該結(jié)點(diǎn)的訪問操作，例如打印該結(jié)點(diǎn)的數(shù)值等信息
        preorder(p->lchild);
        preorder(p->rchild);
    }
}

2.中序遍歷inorder

左、根、右

void inorder(BTNode *p) {
    if (p != NULL) {
        inorder(p->lchild);
        visit(p);
        inorder(p->rchild);
    }
}

3.后序遍歷postorder

左、右、根

void postorder(BTNode *p) {
    if (p != NULL) {
        postorder(p->lchild);
        postorder(p->rchild);
        visit(p);
    }
}

典型例題：寫一個(gè)算法求一棵二叉樹的深度，二叉樹以二叉鏈表為存儲方式。

int getDepth(BTNode *p) {
  int LD, RD;
  if (p == NULL)
    return 0;
   else {
        LD =  getDepth(p->lchild);
        RD = getDepth(p->rchild);
        return (LD>RD?LD:RD)+1;//返回左右子樹深度的最大值加1
  }
}

一個(gè)結(jié)論：根據(jù)二叉樹的前、中、后3種遍歷序列中的前和中、中和后兩對遍歷序列都可以唯一確定這棵二叉樹，而根據(jù)前和后這對遍歷序列不能確定這棵二叉樹。

例題：假設(shè)二叉樹采用二叉鏈表存儲結(jié)構(gòu)存儲，輸出先序遍歷序列中的第k個(gè)結(jié)點(diǎn)的值，假設(shè)k不大于總的結(jié)點(diǎn)數(shù)。

int n;
void print_k_of_preorder(BTNode *p, int k) {
    if (p != NULL) {
        ++n;
        if (k == n) {
            cout<<p->data<<endl;
            return;
        }
        print_k_of_preorder(p->lchild, k);
        print_k_of_preorder(p->rchild, k);
    }
}

4.層次遍歷level

對二叉樹的層次遍歷即從上到下，從左到右的遍歷結(jié)點(diǎn)。
對二叉樹的層次遍歷，需要建立一個(gè)循環(huán)隊(duì)列，先將二叉樹頭結(jié)點(diǎn)入隊(duì)列，然后出隊(duì)列，訪問該結(jié)點(diǎn)，如果它有左子樹，則將左子樹的根結(jié)點(diǎn)入隊(duì)；如果它有右子樹，則將右子樹的根結(jié)點(diǎn)入隊(duì)。然后出隊(duì)列，對出隊(duì)結(jié)點(diǎn)訪問，如此反復(fù)，直到隊(duì)列為空為止。

void level(BTNode *p) {
    queue<BTNode *> queue;
    BTNode *q;
    if (p != NULL)
        queue.push(p);

    while (!queue.empty( )) {
        q = queue.front( );
        queue.pop( );
        cout<<q->data<<endl;
        if (q->lchild != NULL)  
            queue.push(q->lchild);
        if (q->rchild != NULL)
            queue.push(q->rchild);
    }
}

二叉樹遍歷算法的改進(jìn)

之前的幾個(gè)二叉樹的深度優(yōu)先（DFS）遍歷算法，都是用遞歸實(shí)現(xiàn)的，這是很低效的。因?yàn)檫f歸調(diào)用了系統(tǒng)本身的棧，會有很大開銷。用戶自己實(shí)現(xiàn)非遞歸的算法比較高效。

1. 先序遍歷的非遞歸實(shí)現(xiàn)preorder

根結(jié)點(diǎn)入棧。當(dāng)棧不為空時(shí)，出棧棧頂元素，將其右結(jié)點(diǎn)入棧，左結(jié)點(diǎn)入棧...

void PreOrderNonRecursion(BTNode *root) {
  stack<BTNode *> node;
  BTNode *p = root;
  if (p != NULL) {
    node.push(p);

    BTNode *q;
    while (!node.empty()) {
      q = node.top();
      node.pop();
      cout<<q->val<<endl;
      if (q->rchild)
        node.push(q->rchild);
      if (q->lchild)
        node.push(q->lchild);
    }
  }
}

2. 中序遍歷的非遞歸實(shí)現(xiàn)inorder

void InOrderNonRecursion(BTNode *root) {
  stack<BTNode *> node;
  BTNode *p, *q;
  p = root;

  while (!node.empty() || p != NULL) {
    while(p != NULL) {
      node.push(p);
      p = p->lchild;
    }

    if (!node.empty()) {
      p = node.top();
      node.pop();
      cout<<p->val<<endl;
      p = p->rchild;
    }
  }
}

3. 后序遍歷的非遞歸實(shí)現(xiàn)postorder

vector<int> PostOrderNonCursivion(BTNode *root) {
  vector<int> postSeq;
  stack<BTNode *> s;

  if (root == NULL)
    return postSeq;

  BTNode *cur;
  s.push(root);
  BTNode *pre = NULL;

  while (!s.empty()) {
    cur = s.top();
    if ((cur->left == NULL && cur->right == NULL) || (pre != NULL) && (pre == cur->left || pre->cur->right)){
      /* 如果這個(gè)結(jié)點(diǎn)是葉子結(jié)點(diǎn)，或該結(jié)點(diǎn)的左右孩子被訪問過了，則可訪問它 */
      postSeq.push_back(cur->val);
      pre = cur;
      s.pop();
    }
    else {
      if (cur->right != NULL) {
        s.push(cur->right);
      }
      if (cur->left != NULL) {
        s.push(cur->left);
      }
    }
  }
}

線索二叉樹

二叉樹非遞歸遍歷算法避免了系統(tǒng)棧的調(diào)用，提高了一定的執(zhí)行效率。線索二叉樹可以將用戶棧也省掉，把二叉樹的遍歷過程線性化，進(jìn)一步提高效率。
n個(gè)結(jié)點(diǎn)的二叉樹有n+1個(gè)空鏈域，線索二叉樹將這些空鏈域利用起來。
二叉樹被線索化后近似于一個(gè)線性結(jié)構(gòu)，分支結(jié)構(gòu)的遍歷操作就轉(zhuǎn)化為了近似于線性結(jié)構(gòu)的遍歷操作，通過線索的輔助使得尋找當(dāng)前結(jié)點(diǎn)前驅(qū)或者后繼的平均效率大大提高。
線索二叉樹的結(jié)點(diǎn)定義如下：

typedef struct TBTNode {
    char data;
    int ltag, rtag; //線索標(biāo)記
    struct TBTNode *lchild;
    struct TBTNode *rchild;
};

其中的兩個(gè)線索標(biāo)記，如果ltag=0，則表示lchild為指針，指向結(jié)點(diǎn)的左孩子；如果ltag=1，則表示lchild為線索，指向結(jié)點(diǎn)的直接前驅(qū)。
如果rtag=1，則表示rchild為線索，指向結(jié)點(diǎn)的直接后繼。

線索二叉樹可以分為前序線索二叉樹、中序線索二叉樹、后序線索二叉樹。對一棵二叉樹中所有結(jié)點(diǎn)的空指針域按照某種遍歷方式加線索的過程叫做線索化，被線索化了的二叉樹稱為線索二叉樹。
中序線索二叉樹的考察最頻繁。中序線索化的規(guī)則是，左線索指針指向當(dāng)前結(jié)點(diǎn)在中序遍歷序列中的前驅(qū)結(jié)點(diǎn)，右線索指針指向后繼結(jié)點(diǎn)。

void InThread(TBTNode *p, TBTNode *&pre) {
  if (p != NULL) {
    InThread(p->lchild, pre);
    if (p->lchild == NULL) {
      p->lchild = pre;
      p->ltag = 1;
    }
    if (pre != NULL && pre->rchild == NULL) {
      pre->rchild = p;
      pre->rtag = 1;
    }
    pre = p;
    InThread(p->rchild, pre);
  }
}

通過中序遍歷建立中序線索二叉樹的主程序如下：

void createInThread(TBTNode *root) {
  TBTNode *pre = NULL;
  if (root != NULL) {
    InThread(root, pre);
    pre->rchild = NULL;
    pre->rtag = 1;
  }  
}

二叉樹的應(yīng)用

1. 二叉排序樹和平衡二叉樹
2. 赫夫曼樹和赫夫曼編碼

赫夫曼樹

赫夫曼樹又叫做最優(yōu)二叉樹，它的特點(diǎn)是帶權(quán)路徑最短。
樹的帶權(quán)路徑長度WPL：所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度(從該結(jié)點(diǎn)到根之間的路徑長度乘以結(jié)點(diǎn)的權(quán)值)之和。

赫夫曼樹的構(gòu)造方法

1）將這n個(gè)權(quán)值分別看作只有根結(jié)點(diǎn)的n棵二叉樹，這些二叉樹構(gòu)成的集合記為F
2）從F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹作為左右子樹，構(gòu)造一棵新的二叉樹，新的二叉樹的根結(jié)點(diǎn)的權(quán)值為左右子樹根結(jié)點(diǎn)權(quán)值之和。
3）重復(fù)進(jìn)行，直到構(gòu)造成一棵二叉樹。

赫夫曼編碼

在存儲文件的時(shí)候，對于包含同一內(nèi)容的文件有多種存儲方式，可以找出一種最節(jié)省空間的存儲技術(shù)。這就是赫夫曼編碼的用途。常見的.zip壓縮文件和.jpeg圖片文件的底層技術(shù)都用到了赫夫曼編碼。
按字符出現(xiàn)的次數(shù)為權(quán)值，構(gòu)造赫夫曼樹，再進(jìn)行前綴編碼。

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)-樹與二叉樹(1)

數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)-樹與二叉樹(1)

樹的概念與基本術(shù)語

樹的存儲結(jié)構(gòu)：

二叉樹

二叉樹的主要性質(zhì)：

二叉樹的存儲結(jié)構(gòu)

二叉樹的遍歷算法

1.先序遍歷preorder

2.中序遍歷inorder

3.后序遍歷postorder

4.層次遍歷level

二叉樹遍歷算法的改進(jìn)

1. 先序遍歷的非遞歸實(shí)現(xiàn)preorder

2. 中序遍歷的非遞歸實(shí)現(xiàn)inorder

3. 后序遍歷的非遞歸實(shí)現(xiàn)postorder

線索二叉樹

二叉樹的應(yīng)用

赫夫曼樹

赫夫曼樹的構(gòu)造方法

赫夫曼編碼

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)-樹與二叉樹(1)

樹的概念與基本術(shù)語

樹的存儲結(jié)構(gòu)：

二叉樹

二叉樹的主要性質(zhì)：

二叉樹的存儲結(jié)構(gòu)

二叉樹的遍歷算法

1.先序遍歷preorder

2.中序遍歷inorder

3.后序遍歷postorder

4.層次遍歷level

二叉樹遍歷算法的改進(jìn)

1. 先序遍歷的非遞歸實(shí)現(xiàn)preorder

2. 中序遍歷的非遞歸實(shí)現(xiàn)inorder

3. 后序遍歷的非遞歸實(shí)現(xiàn)postorder

線索二叉樹

二叉樹的應(yīng)用

赫夫曼樹

赫夫曼樹的構(gòu)造方法

赫夫曼編碼

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av