首页 » 开发 » 二叉树

二叉搜索树

遍历二叉树

树的遍历通常分为:前序遍历、后序遍历、中序遍历。根据实现算法,又分为递归和非递归遍历。

递归遍历的实现算法:

void tree::_per_order(node* n) const
{
    if(n) {
        std::cout << n->_data << " ";
        _per_order(n->_left);
        _per_order(n->_right);
    }
}

void tree::_post_order(node* n) const
{
    if(n) {
        _post_order(n->_left);
        _post_order(n->_right);
        std::cout << n->_data << " ";
    }
}

void tree::_in_order(node* n) const
{
    if(n) {
        _in_order(n->_left);
        std::cout << n->_data << " ";
        _in_order(n->_right);
    }
}

前序遍历的非递归实现:

void tree::npre_order() const
{
    std::stack<node*> s;
    s.push(_root);

    node* p;
    while(!s.empty()) {
        p = s.top();
        s.pop();
        std::cout << p->_data << " ";

        if(p->_right) s.push(p->_right);
        if(p->_left) s.push(p->_left);
    }
}

后序遍历的非递归实现:

void tree::npost_order() const
{
    std::stack<node*> s;
    s.push(_root);

    node* pre = NULL;
    node* cur;
    while(!s.empty()) {
        cur = s.top();

        // leaf or children have accessed, print
        if(cur->is_leaf() or (pre and pre->child_of(cur))) {
            std::cout << cur->_data << " ";
            s.pop();
            pre = cur;
        } else {
            if(cur->_right) s.push(cur->_right);
            if(cur->_left) s.push(cur->_left);
        }
    }
}

中序遍历的非递归实现:

void tree::nin_order() const
{
    std::stack<node*> s;

    node* p = _root;
    while(p or !s.empty()) {
        while(p) {
            s.push(p);
            p = p->_left;
        }

        p = s.top();
        std::cout << p->_data << " ";
        s.pop();

        p = p->_right;
    }
}

添加节点

从二叉树删除节点

从二叉树删除node节点。node节点可分为三类

  • node没有子节点。直接删除node,将node父节点指向node的指针设置为NULL。
  • node有1个子节点。直接删除node,将node父节点指向node的子节点。
  • node有2个子节点。搜索node的前驱节点,将前驱节点的父节点设置为node的父节点,将node父节点指向node的指针设置为前驱节点的地址。

算法

remove(node):
    /* found node to remove */
    if(node has 0 child or 1 child):
        rm = node
    else:
        rm = node->successor

    /* get node's child */
    c = (node's left or right child)
    
    /* set c's parent */
    c->parent = rm->parent

    /* set rm's parent's child */
    if(rm is root):
        root = c
    else:
        if(rm is left):
            rm->parent->left = c
        else:
            rm->parent->right = c

    /* swap node and rm */ 
    if(node != rm):
        node->data = rm->data
    
    return rm

代码

node* tree::remove(node* n)
{
    /* found the remove node, it will be node or node's succssor */
    node* rm; 

    if(n->_left == NULL or n->_right == NULL) {
        rm = n;   // node has 0 or 1 child, just rm node directly
    } else {
        rm = _succssor(n);      // rm node's succssor
    }   

    /* found the remove node's child */
    node* c = (rm->_left ? rm->_left : rm->_right); 

    /* set child's parent */
    if(c) {
        c->_parent = rm->_parent;
    }   

    /* set parent's child */
    if(rm == _root) {
        _root = c;  // rm root
    } else {
        if(rm == rm->_parent->_left) {  // rm node is it's parent's left node
            rm->_parent->_left = c;
        } else {
            rm->_parent->_right = c;    // rm node is it's parent's right node
        }   
    }   

    if(rm != n) {
        n->_data = rm->_data;
    }   

    return rm; 
}

平衡二叉树

平衡二叉树中每个节点的左右子树高度相差至多为1。左子树的高度减去右子树的高度称为平衡因子,平衡因子的取值若为-1、0、1,则满足平衡二叉树的定义。

当插入新节点后,需要重新计算平衡因子的值,若|HL - HR| > 1,则需要调整二叉树。常见调整策略有:LL型调整、RR型调整、LR型调整和RL型调整。

B树

B树是一棵平衡多叉排序树。B树的几个特性:

1 树中每个节点至多有m个子节点。此时我们称此B树为m阶的B树。通常m≥3。

2 除子节点外,其他节点至少有⌈m⌉个子节点。

3 所有叶节点都在同一层上。

B树中每个节点的结构为:

n P0K1 P1K2 ...... KnPn

其中,n表示有n个数据区(K)以及n+1个指向子节点的指针(P)。Pi指向一个子节点,Ki表示一个关键字。这里有几个约束:

  • Ki < Ki+1
  • Pi指向节点的所有关键字均在区间[Ki, Ki+1)中。

B树查找算法

1 若key == Ki,查找成功。

2 若key < K1,则沿P0指向的子节点搜索。

3 若Ki < key < Ki+1,则沿Pi指向的子节点搜索。

4 若key > Kn,则沿Pn指向的子节点搜索。

分享

0