Day-22 树(Tree), 二元搜寻树(Binary Search Tree)

前言

对於大量的资料处理，使用串列的走访是一种十分没有效率的方法，其效率会根据串列的长度而不断线性成长，也就是，而树(tree)这种资料结构，其大部分的操作时间复杂度平均为

树的定义

树(tree)可以用几种方式定义。一般来说最常见也最自然的定义方法是使用递回的方式。一颗树为一些节点的集合。这个集合也可以是一个空集合，如果不是空集合，则一颗树(tree)是由一个树根(root)的节点以及0个或是多个非空的子树(subtree)T1, T2, Tk所组成，这一些子树(subtree)都被来自树根(root)的一向量(edge)所连接着。

树(tree)有树根(root)，每一个子树(subtree)也有树根(root)，而子树的树根被树的树根所连接。假设树的树根为R，子树的树根为r，则我们会称子树树根r为树根R的儿子,子节点(child)，而树根R为树根r的父亲,父节点(parent)

以下图作为说明:

从递回定义中我们可以观察到树的一个性质，一个树是由N个节点和N - 1条边所构成的集合，也就是一棵树会有N个节点和N - 1条边，我们可以观察下图

我们可以观察到，这棵树从A到Q，共有16个节点，15条边，应证我们上方的结论

而我们来说明一下这一棵树，节点A为树根(root)。

节点F有一个父亲, 父节点A，并且有儿子,子节点K, L, M。在一棵树中，每一个节点可以有任意多个儿子，也有可能有0个儿子。没有儿子的节点我们称为树叶(left)，观察上方的树，我们可以发现B, C, H, I, P, Q, K, L, M, N为树叶。

具有相同父亲的节点称为兄弟(Sibling)，因此观察F节点，可以发现K, L, M皆为兄弟，因为F为他们共同的父亲。

接下来对於树的一些名词进行定义:

1. 树根(root) : 指的是树中最上面那个节点，一个树中只会有一个树根。
2. 子树(subtree) : 由一个节点和其後代所构成的集合。
3. 子节点(child node) : 有父节点的节点，基本上除了树根以外，其余节点皆为子节点。
4. 叶子(left) : 该节点没有其他子节点。
5. 节点ni的深度(depth) : 对於节点ni，ni的深度(depth)为从树根到ni的唯一路径长。

• 举例 : 对於上图，E的深度即为A到E的路径长，也就是1 ，P的深度为A到P的路径长，也就是3。

6. 节点ni的高度(height) : ni节点到一片树叶(left)的'最长'路径长。

• 举例 : 对於上图，E的高度为2，原因为我们可以找到P, 或是Q这样的叶子，他们到E的路径长为2，且我们没办法找到一片叶子他们到E的路径长大於2，因此E节点高度为2

7. 完美二元树 : 除了叶节点，其他节点皆有两个子节点，也就是每一层都填满，也就是深度为的二元树，具有个节点
8. 完全二元树 : 除了最後一层，其余层皆为满的，对於一棵深度为的二元树，最少有个节点，最多有个节点。

如果我们观察整棵树，可以知道这个树的高度为3，也就是A节点到树叶的路径长。而观察节点F，可以发现节点F的深度为1，也就是A到F的路径长，F的高度为1，也就是K, L, M这些叶子到F的路径长。

树的实作

我们由上面的推论，可以推测出每一个节点需要三个资讯，节点的数据，以及下面两个子节点的指标。这边有几个问题需要解决，首先，每一个节点不一定只有1个或是2个儿子，可能会有很多儿子，因此，把每一个儿子都宣告在节点的结构内是不可行的。

我们的解决方法为一个指标指向儿子，另一个指标指向儿子的兄弟们，透过NextSibling去存取儿子们。

typedef struct TreeNode{
    ElementType Element;
    struct *TreeNode FirstChild;
    struct *TreeNode NextSibling;
}TreeNode;

如果我们上面示范的树，用这个结构进行表达，情况会像是下图所演示

由左到右的箭头表示指向兄弟(NextSibling)，下向的箭头表示指向儿子(FirstChild)。
以节点E举例:节点E的NextSibling指标指向节点F，NextSibling指标指向节点I。

二元树(Binary Tree)

二元树(Binary Tree)是一棵树，其中每一个节点都不能多於两个儿子，下图为由一个树根，和两颗子树所组成的二元树，TL和TR可能为NULL。

二元树有一个重要的性质，为平均二元树的深度比N小的很多，平均深度为，而这种特殊的二元树，我们又把他称作为二元搜寻树(Binary Search Tree)，其深度平均为，而深度最大为如下图所示

左图即为深度为的情况。

二元树实作

因为一颗二元树最多只有两个儿子，我们可以直接用指标指向他们。节点的宣告很类似循环串列的宣告方式。每个节点就是节点内的值，加上两个子节点的指标。

typedef sturct TreeNode{
    ElementType Element;
    struct TreeNode* Left;
    struct TreeNode* Right;
}TreeNode;

二元搜寻树(Binary Search Tree)

二元树其中一个重要的应用就是用於搜寻节点中特定的数值。要使二元树成为二元搜寻树，需要具备一项性质，便是对於树中每一个节点X，他的左子树每一个树值都会小於节点X的树值，也因此当我们把一堆资料丢入二元搜寻树时，他会有固定的排列方式。如下图所示

我们可以看到，只有左边这棵树为二元搜寻树，右边这棵树为二元树，右边之所以不是二元搜寻树，原因为在左子树中，节点7的数值大於节点6的数值，这种情况在二元搜寻树中是不允许发生的。

二元搜寻树能够使用多种对於动态集合的操作，像是SEARCH, INSERT, DELETE等操作，也因此我们可以使用二元搜寻树实作出优先队列或是字典序的资料集合。

二元搜寻树进行各项操作的时间复杂度取决於这棵树的高度，对於有个节点的完全二元搜寻树，这些操作最差的执行时间为，如果这棵树刚好是由一条由个节点所构成的线性链状结构，也就是深度为的情况，那麽最差即为，不过，一棵二元搜寻树高度的期望值为，因此每一种操作执行时间的期望值皆为。

二元搜寻树(Binary Search Tree)的ADT

以下为二元搜寻树的ADT，其中，树提供了三种走访的方式，分别为中序走访(inorder), 前序走访(preorder), 後序走访(postorder)。

#ifndef _Tree_H

TreeNode* Create_tree(TreeNode*);
TreeNode* MakeEmpty(TreeNode* T);
void In_order(TreeNode*);
void Pre_order(TreeNode*);
void Post_order(TreeNode*);
void Level_order(TreeNode*);
TreeNode* Search_node(ElementType X, TreeNode* T);
TreeNode* FindMin(TreeNode* T);
TreeNode* FineMax(TreeNode* T);
TreeNode* Ineset(ElementType X, TreeNode* T);
TreeNode* Delete(ElementType X, TreeNode* T);
ElementType Retrieve(TreeNode* P);

#endif /*_Tree_H*/

/*Place in the implementation file"*/
typedef sturct TreeNode{
    ElementType Element;
    struct TreeNode* Left;
    struct TreeNode* Right;
}TreeNode;

Create_tree函式实作

TreeNode* Create_tree(TreeNode* root, int value)
{
    root = malloc(sizeof(TreeNode));
    root->left = NULL;
    root->right = NULL;
    root->value = value;
    return root;
}

MakeEmpty函式实作

TreeNode* Make_empty(TreeNode* root)
{
    if(root != NULL)
    {
        make_empty(root->left);
        make_empty(root->right);
        free(root);
    }
    return NULL;
}

In_order函式实作

In_order，中序走访，命名的理由为输出的形式为根节点会出现在左节点和右节点之间，也就是依照左节点 根节点 右节点形式输出。

void In_order(TreeNode* root)
{
    if(root != NULL)
    {
        inOrder(root->left);
        printf("%d ", root->value);
        inOrder(root->right);
    }
    return;
}

(为了方便说明，上面的树只是二元树而已)

In_order = 7,4,8,2,5,1,3,9,6,10

Pre_order函式实作

Pre_order，顾名思义，就是输出的形式为根结点会出现在左结点和右结点之前，也就根节点 左节点 右节点。

void Pre_order(TreeNode* root)
{
    if(root != NULL)
    {
        printf("%d ", root->value);
        preOrder(root->left);
        preOrder(root->right);
    }
}

(为了方便说明，上面的树只是二元树而已)

Pre_order = 1,2,4,7,8,5,3,6,9,10

Post_order函式实作

Post_order，顾名思义，就是输出的形式为根结点出现在左结点和右结点之後

void postOrder(TreeNode* root)
{
    if(root != NULL)
    {
        postOrder(root->left);
        postOrder(root->right);
        printf("%d ", root->value);
    }
}

(为了方便说明，上面的树只是二元树而已)

Post_order = 7,8,4,5,2,9,10,6,3,1

Level_order函式实作

Level_order，就是依照节点所在的层数，由小到大，由左到右输出，这里使用queue，将结点依序推入并输出

void level_order(TreeNode *root)
{
    queue<TreeNode *> q;
    q.push(root);
    while (!q.empty())
    {
        TreeNode *temp = q.front();
        q.pop();
        printf("%d ", temp->value);

        if (temp->left != NULL)
        {
            q.push(temp->left);
        }
        if (temp->right != NULL)
        {
            q.push(temp->right);
        }
    }
}

Search_node函式实作

给定一个指向树根的指标，和我们要查询的数值，如果有节点为该数值，则回传该节点的指标，否则回传NULL。

TREE-SEARCH(x,k)
if x == NULL or k == x.key
    return x
if k < x.key
    return TREE-SEARCH(x.left, k)
else
    return TREE-SEARCH(x.right, k)

TreeNode* search_node(TreeNode* root, int value)
{
    if(root == NULL || value == root->value)
    {
        return root;
    }
    if(value < root->value)
    {
        return search_node(root->left, value);
    }
    else
    {
        return search_node(root->right, value);
    }
}

从树根开始走访，遇到每一个节点，比较节点的数值，如果相等，则回传该节点的指标。
如果小於，则查询的左子树并继续寻找，也就是递回的概念。
如果大於，则查询的右子树并继续递回寻找。
而寻找走过的最简单路径，即为树的高度，因此整个TREE-SEARCH的时间复杂度为

也可以使用while回圈来实作，相比於递回，效率会来的快上许多

ITERATIVE-TREE-SEARCH(x, k)
while x != NULL and k != x.key
    if k < x.key
        x = x.left
    else x = x.right
return x

min_value_node和max_value_node函式实作

TreeNode* min_value_node(TreeNode* root)
{
    TreeNode* cur_ptr = root;
    while(cur_ptr->left != NULL)
    {
        cur_ptr = cur_ptr->left;
    }
    return cur_ptr;
}

TreeNode* max_value_node(TreeNode* root)
{
    TreeNode* cur_ptr = root;
    while(cur_ptr->right != NULL)
    {
        cur_ptr = cur_ptr->right;
    }
    return cur_ptr;
}

寻找最大值和最小值时间复杂度也是

Insert函式实作

从树根开始，使用root指标不断的向下遍历整棵树，找到适当的插入位置，如果要插入的值小於子树根的值，表示该节点需要向左子树移动(因为二元搜寻树的性质)，反之则向右子树移动，通过递回的方式查看每一个子树。

TreeNode* Insert(TreeNode* root, int value)
{
    TreeNode* newPtr = malloc(sizeof(TreeNode));
    newPtr->value = value;
    newPtr->left = NULL;
    newPtr->right = NULL;

    if(root == NULL)
    {
        root = newPtr;
    }
    else if (value < root->value)
    {
        root->left = insert(root->left, value);
    }
    else if(value > root->value)
    {
        root->right = insert(root->right, value);
    }
    return root;
}

或是也可以使用回圈进行实作，使用root指标不断的向下遍历整棵树，并使用temp_root纪录root的父节点的指标，while回圈使得这两个指标不断向下遍历，直到root == NULL，而root所指向的位置像是欲插入节点的位置

TreeNode *insert(TreeNode *root, int value)
{
    TreeNode *newPtr = (TreeNode *)malloc(sizeof(TreeNode));
    newPtr->value = value;
    newPtr->left = NULL;
    newPtr->right = NULL;

    TreeNode *temp_root = NULL;
    while (root != NULL)
    {
        temp_root = root;
        if (newPtr->value < root->value)
        {
            root = root->left;
        }
        else
        {
            root = root->right;
        }
    }
    newPtr->parent = temp_root;
    if (temp_root == NULL)
    {
        root = newPtr;
    }
    else if (newPtr->value < temp_root->value)
    {
        temp_root->left = newPtr;
    }
    else
    {
        temp_root->right = newPtr;
    }
}

在一棵高度为的树，INSERT的时间复杂度为

Delete函式实作

从一棵二元搜寻树中删除一个节点可以分为三种情况

1. 如果没有任何子节点，我们只需要将的父节点指向子节点NULL即可。

2. 如果只有一个子节点，则把该子节点放到原本节点的位置，并修改的父节点，使他指向到的子节点。
   
   (a)表示只有右子节点 (b)表示只有左子节点

3. 如果有两个子节点，我们可以试着寻找出左子树的最大节点，并将节点的数值设为左子树中最大节点的数值，这样做可以让我们维持二元搜寻树的性质，之後将指向到新的左子树。

TreeNode* delete(TreeNode* root, int value)
{
    if(root == NULL)
    {

    }
    else if(value < root->value)
    {
        root->left = delete(root->left, value);
    }
    else if(value > root->value)
    {
        root->right = delete(root->right, value);
    }
    else if(value == root->value)
    {
        if(root->left == NULL && root->right == NULL)
        {
            free(root);
            root = NULL;
        }
        else if(root->left == NULL)
        {
            TreeNode* tempnode = root->right;
            free(root);
            root = tempnode;
        }
        else if(root->right == NULL)
        {
            TreeNode* tempnode = root->left;
            free(root);
            root = tempnode;
        }
        else
        {
            TreeNode* tempnode = max_value_node(root->left);
            root->value = tempnode->value;
            root->left = delete(root->left, tempnode->value);
        }
    }
    return root;
}

前面的过程为透过递回的方式寻找我们要删除的节点，而欲删除的节点会有上面说的四种情况，分别为没有子节点，只有右子节点，只有左子节点，和有两个子节点。

如果树的高度为，则delete的时间复杂度为

树的遍历和应用

树有很多种应用，最常见的应用为UNIX, VAX/VMS和DOS等等，许多作业系统中作为目录结构的表示，我们在windows平台上，在cmd中输入tree也会列出目录的树状结构，下图为UNIX档案系统中常见的目录表示

上图即为常见UNIX系统中的档案目录结构
这个目录的树根为'/'(也被称做根目录)，根目录有5个儿子，分别为etc, bin, home, lib, var。而档案路径"/etc/hosts"，这种路径表示法也被称为绝对路径(absolute path)，而hosts这个档案，是先後通过两个子节点所取的，而从档案路径来看，可以看到有两个'/'符号，表示通过了两条边。
这种档案系统十分的流行，方便之处在於可以让使用者有逻辑性的管理档案，且不同目录底下的档案可以使用相同的名称。

如果我们想要写个程序，用印出目录中所有档案的名称，我们的输出方式为，深度为d的档案名称前面会空出d个tab并列印出来(也就是windows底下tree指令的逻辑)，以下为虚拟码

备注: 其实UNIX档案系统中，每一个目录都还有一个指向自己目录本身以及指向自己目录的父目录，因此，严格来说UNIX档案系统并不是树，而是类似树状的结构(treelike)

参考资料: 大话数据结构，C语言程序设计现代方法第2版，Introduction of algorithm 3rd，图片源於网路