二叉树代码实现笔记
二叉树代码实现笔记
二叉树
定义节点
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;
}
合并子树的操作也很有趣(这里的合并不是任意两个子树合并,而是左子树中任意元素必须小于右子树中最小的元素):
- 首先是如何将一颗树的最小元素提升到根:一颗树的最小元素永远在树最左边的节点处,所以不断向左游走就可以到达最小元素点处,然后依靠之前的右旋操作可知,右旋可以将左子节点提升,所以在递归返回的时候最小的元素就会不断上浮到达整棵树的根部。
- 然后是如何连接两棵树:首先将需要作为连接后右子树利用minToRoot操作将其最小元素上浮到根部,根据树的性质,上浮后这个树根的左子节点必然为NULL,所以这时候就可以直接指向左子树了。
如果希望将任意两棵树进行合并,则要麻烦许多。
二叉树的常见问题及其解决程序
【递归】二叉树的先序建立及遍历
在JAVA中实现的二叉树结构
【非递归】二叉树的建立及遍历
二叉树递归实现与二重指针
|
评论暂时关闭