歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

二叉樹代碼實現筆記

二叉樹
定義節點

class Node {
public:
    int key;
    struct Node *l;
    struct Node *r;
    Node(int _key): l(NULL), r(NULL), key(_key) {}
};

二叉樹上一個節點,最少需要三個屬性,一個用於表示節點編號的key值,一個指向左子節點的指針、一個指向右子節點的指針。

定義一棵樹

class BTree {
public:
    BTree() : root(NULL) {}
    void insert(int key);
    void insertRoot(int key);
    void deleteNode(int key);
    void print();

private:
    Node *root;
private:
    // 向h樹指向的樹中添加元素key,返回更新後的樹
    static Node *insertR(Node *h, int key);
    // 右旋操作,可以令左子樹深度減一,返回旋轉後的樹
    static Node *rotateR(Node *h);
    // 左旋操作,可以令右子樹深度減一,返回旋轉後的樹
    static Node *rotateL(Node *h);
    // 將h樹最小的元素上浮到樹根部,返回最後上浮後的樹
    static Node *minToRoot(Node *h);
    // 將兩棵樹合並成一棵樹,返回合並後的樹
    static Node *join(Node *l, Node *r);
    // 向h樹中插入元素,並且插入的元素會存在樹根部,返回插入後的樹
    static Node *insertT(Node *h, int key);
    // 中序遍歷h樹
    static void inOrder(Node *h);
    // 從h樹中刪除key,返回刪除後的樹
    static Node *deleteR(Node *h, int key);
};

樹的操作很多,以上只是列舉其中的一些操作,對於代碼實現,難點反而在於正確理解遞歸調用,二叉樹的性質反而很簡單。只要能夠理解這些遞歸調用的特點,添加新的操作方法反而不是太難。

封裝

void BTree::insert(int key) {
    this->root = insertR(this->root, key);
}

void BTree::insertRoot(int key) {
    this->root = insertT(this->root, key);
}

void BTree::print() {
    inOrder(this->root);
}

void BTree::deleteNode(int key) {
    this->root = deleteR(this->root, key);
}

 樹的很多操作通過遞歸可以很容易的實現,所以需要對這些遞歸操作進行封裝,可以簡化外部操作。

插入元素

Node *BTree::insertR(Node *h, int key) {
    if (h == NULL) return new Node(key);
    if (h->key < key) {
        h->r = insertR(h->r, key);
    } else {
        h->l = insertR(h->l, key);
    }
    return h;
}

插入元素必須遞歸地向樹根部游走,直到遇到樹根部,然後插入元素,再依次退回。遞歸調用的過程就是向下游走的過程,遇到NULL,表明已經走到樹根部。

這裡比較繞的就是返回值的語義,它表示插入元素後新生成的樹。

旋轉

Node *BTree::rotateR(Node *h) {
    if (h->l == NULL) return h;
    Node *x = h->l;
    h->l = x->r;
    x->r = h;
    return x;
}

Node *BTree::rotateL(Node *h) {
    if (h->r == NULL) return h;
    Node *x = h->r;
    h->r = x->l;
    x->l = h;
    return x;
}

樹的旋轉操作很有意思,它可以在不更改樹的性質的情況下,改變左右子樹的高度

  • 左旋操作:可以讓右子樹高度減一,左子樹高度加一,讓原有的右子樹的根節點稱為旋轉後子樹的根節點,讓原有子樹的根節點變成其左子樹的根節點
  • 右旋操作:與左旋操作相反。

合並子樹

Node *BTree::minToRoot(Node *h) {
    if (h->l != NULL)  {
        h->l = minToRoot(h->l); // 將最小元素提升到左子樹的根部
        h = rotateR(h); // 將左子樹中最小元素提升到根部
    }
    return h;
}

Node *BTree::join(Node *l, Node *r) {
    if (r == NULL) return l;
    r = minToRoot(r); // 將r樹的最小元素提升到根節點
    r->l = l;
    return r;
}

合並子樹的操作也很有趣(這裡的合並不是任意兩個子樹合並,而是左子樹中任意元素必須小於右子樹中最小的元素):

  1. 首先是如何將一顆樹的最小元素提升到根:一顆樹的最小元素永遠在樹最左邊的節點處,所以不斷向左游走就可以到達最小元素點處,然後依靠之前的右旋操作可知,右旋可以將左子節點提升,所以在遞歸返回的時候最小的元素就會不斷上浮到達整棵樹的根部。
  2. 然後是如何連接兩棵樹:首先將需要作為連接後右子樹利用minToRoot操作將其最小元素上浮到根部,根據樹的性質,上浮後這個樹根的左子節點必然為NULL,所以這時候就可以直接指向左子樹了。

如果希望將任意兩棵樹進行合並,則要麻煩許多。

 

Copyright © Linux教程網 All Rights Reserved