二叉樹代碼實現筆記

二叉樹
定義節點

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，所以這時候就可以直接指向左子樹了。

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