纸上谈兵: 树, 二叉树, 二叉搜索树

  • 时间:
  • 浏览:4

作者:Vamei 出处:http://www.cnblogs.com/vamei 欢迎转载,也请保留这段声明。谢谢!

树的形态学 和定义

树(Tree)是元素的集合。我们我们我们 我们我们我们 我们我们我们 我们我们我们 先以比较直观的土法子 介绍树。下面的数据形态学 是有一4个 树:

树有多个节点(node),用以储存元素。其他节点之间占据 一定的关系,用连线表示,连线称为边(edge)。边的底下节点称为父节点,下端称为子节点。树像是有一4个 不断分叉的树根。

每个节点可否 有多个子节点(children),而该节点是相应子节点的父节点(parent)。比如说,3,5是6的子节点,6是3,5的父节点;1,8,7是3的子节点, 3是1,8,7的父节点。树有有一4个 那么父节点的节点,称为根节点(root),如图中的6。那么子节点的节点称为叶节点(leaf),比如图中的1,8,9,5节点。从图中还可否 看了,底下的树总共有有一4个 层次,6占据 第一层,9占据 第四层。树中节点的最大层次被称为深度图。也就说 说,该树的深度图(depth)为4。

意味着着我们我们我们 我们我们我们 我们我们我们 我们我们我们 从节点3过后刚开始向下看,而忽略其它偏离 。那么我们我们我们 我们我们我们 我们我们我们 我们我们我们 看了的是有一4个 以节点3为根节点的树:

三角形代表一棵树

再进一步,意味着着我们我们我们 我们我们我们 我们我们我们 我们我们我们 定义孤立的有一4个 节点是一棵树语录,原来的树就可否 表示为根节点和子树(subtree)的关系:

上述观察实际上给了我们我们我们 我们我们我们 我们我们我们 我们我们我们 你是什么严格的定义树的土法子 :

1. 树是元素的集合。

2. 该集合可否 为空。这时树中那么元素,我们我们我们 我们我们我们 我们我们我们 我们我们我们 称树为空树 (empty tree)

3. 意味着着该集合不为空,那么该集合有有一4个 根节点,以及0个意味着着多个子树。根节点与它的子树的根节点用有一4个 边(edge)相连。

底下的第三点是以递归的土法子 来定义树,也就说 在定义树的过程中使用了树自身(子树)。意味着着树的递归形态学 ,其他树相关的操作也可否 方便的使用递归实现。我们我们我们 我们我们我们 我们我们我们 我们我们我们 将在底下看了。

(上述定义来自"Data Structures and Algorithm Analysis in C, by Mark Allen Weiss"。 我确实有其他不太严格的地方。意味着着说空树属于树,第三点应该是 “...以及0个和多个非空子树...” )

树的实现

树的示意图意味着着给出了树的你是什么内存实现土法子 : 每个节点储存元素和多个指向子节点的指针。然而,子节点数目是不选着的。有一4个 父节点意味着着有少许的子节点,而原来父节点意味着着不可否 有一4个 子节点,而树的增删节点操作会让子节点的数目占据 进一步的变化。你是什么不选着性就说 意味着着带来少许的内存相关操作,其他容易造成内存的浪费。

你是什么经典的实现土法子 如下:

树的内存实现

拥有同一父节点的有一4个 节点互为兄弟节点(sibling)。上图的实现土法子 中,每个节点包中有 有一4个 指针指向第有一4个 子节点,并有原来指针指向它的下有一4个 兄弟节点。原来,我们我们我们 我们我们我们 我们我们我们 我们我们我们 就可否 用统一的、选着的形态学 来表示每个节点。

计算机的文件系统是树的形态学 ,比如Linux文件管理背景知识中所介绍的。在UNIX的文件系统中,每个文件(文件夹同样是你是什么文件),都可否 看做是有一4个 节点。非文件夹的文件被储占据 叶节点。文件夹中有 指向父节点和子节点的指针(在UNIX中,文件夹还包中有 一4个 指向自身的指针,这与我们我们我们 我们我们我们 我们我们我们 我们我们我们 底下见到的树有所区别)。在git中,有的是类似于的树状形态学 ,用以表达整个文件系统的版本变化 (参考版本管理三国志)。

文件树

二叉搜索树的C实现

二叉树(binary)是你是什么特殊的树。二叉树的每个节点最多不可否 有有一4个 子节点

二叉树

意味着着二叉树的子节点数目选着,其他可否 直接采用上图土法子 在内存中实现。每个节点有有一4个 左子节点(left children)右子节点(right children)。左子节点是左子树的根节点,右子节点是右子树的根节点。

意味着着我们我们我们 我们我们我们 我们我们我们 我们我们我们 给二叉树加有一4个 额外的条件,就可否 得到你是什么被称作二叉搜索树(binary search tree)的特殊二叉树。二叉搜索树要求:每个节点有的是比它左子树的任意元素小,其他不比它的右子树的任意元素大。

(意味着着我们我们我们 我们我们我们 我们我们我们 我们我们我们 假设树中那么重复的元素,那么上述要求可否 写成:每个节点比它左子树的任意节点大,其他比它右子树的任意节点小)

二叉搜索树,注意树中元素的大小

二叉搜索树可否 方便的实现搜索算法。在搜索元素x的过后 ,我们我们我们 我们我们我们 我们我们我们 我们我们我们 可否 将x和根节点比较:

1. 意味着着x等于根节点,那么找到x,停止搜索 (终止条件)

2. 意味着着x小于根节点,那么搜索左子树

3. 意味着着x大于根节点,那么搜索右子树

二叉搜索树所时要进行的操作次数最多与树的深度图相等。n个节点的二叉搜索树的深度图最多为n,为宜为log(n)。

下面是用C语言实现的二叉搜索树,并有搜索插入删除寻找最大最小节点的操作。每个节点中存有有一4个 指针,有一4个 指向父节点,有一4个 指向左子节点,有一4个 指向右子节点。

(原来的实现是为了方便。节点可否 只保存有指向左右子节点的有一4个 指针,并实现上述操作。)

删除节点相对比较简化。删除节点后,有时时要进行一定的调整,以恢复二叉搜索树的性质(每个节点有的是比它左子树的任意元素小,其他不比它的右子树的任意元素大)。

  • 叶节点可否 直接删除。
  • 删除非叶节点时,比如下图中的节点8,我们我们我们 我们我们我们 我们我们我们 我们我们我们 可否 删除左子树中最大的元素(意味着着右树中最大的元素),用删除的节点来补充元素8产生的空缺。但该元素意味着着有的是的是叶节点,其他它所产生的空缺时要其他元素补充…… 直到最后删除有一4个 叶节点。上述过程可否 递归实现。

删除节点

删除节点后的二叉搜索树

/* By Vamei */
/* binary search tree */
#include <stdio.h>
#include <stdlib.h>

typedef struct node *position;
typedef int ElementTP;

struct node {
    position parent;
    ElementTP element;
    position lchild;
    position rchild;
};

/* pointer => root node of the tree */
typedef struct node *TREE;

void print_sorted_tree(TREE);
position find_min(TREE);
position find_max(TREE);
position find_value(TREE, ElementTP);
position insert_value(TREE, ElementTP);
ElementTP delete_node(position);

static int is_root(position);
static int is_leaf(position);
static ElementTP delete_leaf(position);
static void insert_node_to_nonempty_tree(TREE, position);

void main(void) 
{
    TREE tr;
    position np;
    ElementTP element;
    tr = NULL;
    tr = insert_value(tr, 18);
    tr = insert_value(tr, 5);
    tr = insert_value(tr, 2); 
    tr = insert_value(tr, 8);
    tr = insert_value(tr, 81);
    tr = insert_value(tr, 101);
    printf("Original:\n");
    print_sorted_tree(tr);

    np = find_value(tr, 8);
    if(np != NULL) {
        delete_node(np);
        printf("After deletion:\n");
        print_sorted_tree(tr);
    }
}


/* 
 * print values of the tree in sorted order
 */
void print_sorted_tree(TREE tr)
{
    if (tr == NULL) return;
    print_sorted_tree(tr->lchild);
    printf("%d \n", tr->element);
    print_sorted_tree(tr->rchild);
}

/*
 * search for minimum value
 * traverse lchild
 */
position find_min(TREE tr)
{
    position np;
    np = tr;
    if (np == NULL) return NULL;
    while(np->lchild != NULL) {
        np = np->lchild;
    }
    return np;
}

/*
 * search for maximum value
 * traverse rchild
 */
position find_max(TREE tr)
{
    position np;
    np = tr;
    if (np == NULL) return NULL;
    while(np->rchild != NULL) {
        np = np->rchild;
    }
    return np;
}

/*
 * search for value
 *
 */
position find_value(TREE tr, ElementTP value) 
{
    if (tr == NULL) return NULL; 

    if (tr->element == value) {
        return tr;
    }
    else if (value < tr->element) {
        return find_value(tr->lchild, value);
    }
    else {
        return find_value(tr->rchild, value);
    }
}

/* 
 * delete node np 
 */
ElementTP delete_node(position np) 
{
    position replace;
    ElementTP element;
    if (is_leaf(np)) {
        return delete_leaf(np);
    }   
    else {
        /* if a node is not a leaf, then we need to find a replacement */
        replace = (np->lchild != NULL) ? find_max(np->lchild) : find_min(np->rchild);
        element = np->element;
        np->element = delete_node(replace);
        return element;
    }
}

/* 
 * insert a value into the tree
 * return root address of the tree
 */
position insert_value(TREE tr, ElementTP value) {
    position np;
    /* prepare the node */
    np = (position) malloc(sizeof(struct node));
    np->element = value;
    np->parent  = NULL;
    np->lchild  = NULL;
    np->rchild  = NULL;
 
    if (tr == NULL) tr = np;
    else {
        insert_node_to_nonempty_tree(tr, np);
    }
    return tr;
}


//=============================================

/*
 * np is root?
 */
static int is_root(position np)
{
    return (np->parent == NULL);
}

/*
 * np is leaf?
 */
static int is_leaf(position np)
{
    return (np->lchild == NULL && np->rchild == NULL);
}

/* 
 * if an element is a leaf, 
 * then it could be removed with no side effect.
 */
static ElementTP delete_leaf(position np)
{
    ElementTP element;
    position parent;
    element = np->element;
    parent  = np->parent;
    if(!is_root(np)) {
        if (parent->lchild == np) {
            parent->lchild = NULL;
        }
        else {
            parent->rchild = NULL;
        }
    }
    free(np);
    return element;
}

/*
 * insert a node to a non-empty tree
 * called by insert_value()
 */
static void insert_node_to_nonempty_tree(TREE tr, position np)
{
    /* insert the node */
    if(np->element <= tr->element) {
        if (tr->lchild == NULL) {
            /* then tr->lchild is the proper place */
            tr->lchild = np;
            np->parent = tr;
            return;
        }
        else {
            insert_node_to_nonempty_tree(tr->lchild, np);
        }
    }
    else if(np->element > tr->element) {
        if (tr->rchild == NULL) {
            tr->rchild = np;
            np->parent = tr;
            return;
        }
        else {
            insert_node_to_nonempty_tree(tr->rchild, np);
        }
    }
}

运行结果:

Original:

2

5

8

18

81

101

After deletion:

2

5

18

81

101

上述实现中的删除比较简化。有你是什么简单的替代操作,称为懒惰删除(lazy deletion)。在懒惰删除时,我们我们我们 我们我们我们 我们我们我们 我们我们我们 不必真正从二叉搜索树中删除该节点,就说 将该节点标记为“已删除”。原来,我们我们我们 我们我们我们 我们我们我们 我们我们我们 只用找到元素并标记,就可否 完成删除元素了。意味着着有相同的元素重新插入,我们我们我们 我们我们我们 我们我们我们 我们我们我们 可否 将该节点找到,并归还删除标记。

懒惰删除的实现比较简单,可否 尝试一下。树所占据 的内存空间不必意味着着删除节点而减小。懒惰节点实际上是用内存空间换取操作的简便性。

总结

树, 二叉树, 二叉搜索树

二叉搜索树的删除

懒惰删除

欢迎继续阅读“纸上谈兵: 算法与数据形态学 ”系列。