天天看點
傳回

大話資料結構之二叉樹1. 樹的定義2. 樹的基本術語3、二叉樹的性質（需要了解）3.1滿二叉樹3.2 完全二叉樹3.3 二叉查找樹3. 查找

上一遍寫了一個簡單的樹，沒有給大家介紹樹的概念，對應初學者可能不是很容易看懂，等一下在這一篇介紹樹的概念和自己看完大話資料結構寫的一篇容易了解的二叉樹。

1. 樹的定義

樹是一種資料結構，它是由n（n>=1）個有限節點組成一個具有層次關系的集合。

大話資料結構之二叉樹1. 樹的定義2. 樹的基本術語3、二叉樹的性質（需要了解）3.1滿二叉樹3.2 完全二叉樹3.3 二叉查找樹3. 查找

把它叫做“樹”是因為它看起來像一棵倒挂的樹，也就是說它是根朝上，而葉朝下的。它具有以下的特點：

(01) 每個節點有零個或多個子節點；

(02) 沒有父節點的節點稱為根節點；

(03) 每一個非根節點有且隻有一個父節點；

(04) 除了根節點外，每個子節點可以分為多個不相交的子樹。

2. 樹的基本術語

若一個結點有子樹，那麼該結點稱為子樹根的"雙親"，子樹的根是該結點的"孩子"。有相同雙親的結點互為"兄弟"。一個結點的所有子樹上的任何結點都是該結點的後裔。從根結點到某個結點的路徑上的所有結點都是該結點的祖先。

結點的度：結點擁有的子樹的數目。

葉子：度為零的結點。

分支結點：度不為零的結點。

樹的度：樹中結點的最大的度。

層次：根結點的層次為1，其餘結點的層次等于該結點的雙親結點的層次加1。

樹的高度：樹中結點的最大層次。

無序樹：如果樹中結點的各子樹之間的次序是不重要的，可以交換位置。

有序樹：如果樹中結點的各子樹之間的次序是重要的, 不可以交換位置。

森林：0個或多個不相交的樹組成。對森林加上一個根，森林即成為樹；删去根，樹即成為森林。

  1. 二叉樹的定義

二叉樹是每個節點最多有兩個子樹的樹結構。它有五種基本形态：二叉樹可以是空集；根可以有空的左子樹或右子樹；或者左、右子樹皆為空。

大話資料結構之二叉樹1. 樹的定義2. 樹的基本術語3、二叉樹的性質（需要了解）3.1滿二叉樹3.2 完全二叉樹3.3 二叉查找樹3. 查找

3、二叉樹的性質（需要了解）

大話資料結構之二叉樹1. 樹的定義2. 樹的基本術語3、二叉樹的性質（需要了解）3.1滿二叉樹3.2 完全二叉樹3.3 二叉查找樹3. 查找

3.1滿二叉樹

大話資料結構之二叉樹1. 樹的定義2. 樹的基本術語3、二叉樹的性質（需要了解）3.1滿二叉樹3.2 完全二叉樹3.3 二叉查找樹3. 查找

3.2 完全二叉樹

（一棵滿二叉樹必定是一棵完全二叉樹，而完全二叉樹未必是滿二叉樹）重點了解

大話資料結構之二叉樹1. 樹的定義2. 樹的基本術語3、二叉樹的性質（需要了解）3.1滿二叉樹3.2 完全二叉樹3.3 二叉查找樹3. 查找

3.3 二叉查找樹

定義：二叉查找樹(Binary Search Tree)，又被稱為二叉搜尋樹。設x為二叉查找樹中的一個結點，x節點包含關鍵字key，節點x的key值記為key[x]。

如果y是x的左子樹中的一個結點，則key[y] <= key[x]；

如果y是x的右子樹的一個結點，則key[y] >= key[x]。

大話資料結構之二叉樹1. 樹的定義2. 樹的基本術語3、二叉樹的性質（需要了解）3.1滿二叉樹3.2 完全二叉樹3.3 二叉查找樹3. 查找

(01) 若任意節點的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；

(02) 任意節點的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；

(03) 任意節點的左、右子樹也分别為二叉查找樹。

(04) 沒有鍵值相等的節點（no duplicate nodes）。

因為比較重要（逐漸分析）：

1.1 節點定義 

typedef int Type;

typedef struct BSTreeNode{
    Type   key;                    // 關鍵字(鍵值)
    struct BSTreeNode *left;    // 左孩子
    struct BSTreeNode *right;    // 右孩子
    struct BSTreeNode *parent;    // 父結點
}Node, *BSTree;

二叉查找樹的節點包含的基本資訊：

(01) key – 它是關鍵字，是用來對二叉查找樹的節點進行排序的。

(02) left --> 它指向目前節點的左孩子。

(03) right – 它指向目前節點的右孩子。

(04) parent – 它指向目前節點的父結點。

1.2 建立節點 

static Node* create_bstree_node(Type key, Node *parent, Node *left, Node* right)
{
    Node* p;
    if ((p = (Node *)malloc(sizeof(Node))) == NULL)
        return NULL;
    p->key = key;
    p->left = left;
    p->right = right;
    p->parent = parent;
    return p;
}

2 周遊

這裡講解前序周遊、中序周遊、後序周遊3種方式。

2.1 前序周遊

若二叉樹非空，則執行以下操作：

(01) 通路根結點；

(02) 先序周遊左子樹；

(03) 先序周遊右子樹。

void preorder_bstree(BSTree tree)
{
    if(tree != NULL)
    {
        printf("%d ", tree->key);
        preorder_bstree(tree->left);
        preorder_bstree(tree->right);
    }
}

2.2 中序周遊

若二叉樹非空，則執行以下操作：

(01) 中序周遊左子樹；

(02) 通路根結點；

(03) 中序周遊右子樹。

void inorder_bstree(BSTree tree)
{
    if(tree != NULL)
    {
        inorder_bstree(tree->left);
        printf("%d ", tree->key);
        inorder_bstree(tree->right);
    }
}

2.3 後序周遊

若二叉樹非空，則執行以下操作：

(01) 後序周遊左子樹；

(02) 後序周遊右子樹；

(03) 通路根結點。

後序周遊代碼

void postorder_bstree(BSTree tree)
{
    if(tree != NULL)
    {
        postorder_bstree(tree->left);
        postorder_bstree(tree->right);
        printf("%d ", tree->key);
    }
}

下面通過例子對這些周遊方式進行介紹。

大話資料結構之二叉樹1. 樹的定義2. 樹的基本術語3、二叉樹的性質（需要了解）3.1滿二叉樹3.2 完全二叉樹3.3 二叉查找樹3. 查找

對于上面的二叉樹而言，

(01) 前序周遊結果： 3 1 2 5 4 6

(02) 中序周遊結果： 1 2 3 4 5 6

(03) 後序周遊結果： 2 1 4 6 5 3

3. 查找

遞歸版本的代碼

Node* bstree_search(BSTree x, Type key)
{
    if (x==NULL || x->key==key)
        return x;

    if (key < x->key)
        return bstree_search(x->left, key);
    else
        return bstree_search(x->right, key);
}

非遞歸版本的代碼

Node* iterative_bstree_search(BSTree x, Type key)
{
    while ((x!=NULL) && (x->key!=key))
    {
        if (key < x->key)
            x = x->left;
        else
            x = x->right;
    }

    return x;
}

4. 最大值和最小值

查找最大值的代碼

Node* bstree_maximum(BSTree tree)
{
    if (tree == NULL)
        return NULL;

    while(tree->right != NULL)
        tree = tree->right;
    return tree;
}

查找最小值的代碼

Node* bstree_minimum(BSTree tree)
{
    if (tree == NULL)
        return NULL;

    while(tree->left != NULL)
        tree = tree->left;
    return tree;
}

5. 前驅和後繼

節點的前驅：是該節點的左子樹中的最大節點。

節點的後繼：是該節點的右子樹中的最小節點。

查找前驅節點的代碼

Node* bstree_predecessor(Node *x)
{
    // 如果x存在左孩子，則"x的前驅結點"為 "以其左孩子為根的子樹的最大結點"。
    if (x->left != NULL)
        return bstree_maximum(x->left);

    // 如果x沒有左孩子。則x有以下兩種可能：
    // (01) x是"一個右孩子"，則"x的前驅結點"為 "它的父結點"。
    // (01) x是"一個左孩子"，則查找"x的最低的父結點，并且該父結點要具有右孩子"，找到的這個"最低的父結點"就是"x的前驅結點"。
    Node* y = x->parent;
    while ((y!=NULL) && (x==y->left))
    {
        x = y;
        y = y->parent;
    }

    return y;
}

查找後繼節點的代碼

Node* bstree_successor(Node *x)
{
    // 如果x存在右孩子，則"x的後繼結點"為 "以其右孩子為根的子樹的最小結點"。
    if (x->right != NULL)
        return bstree_minimum(x->right);

    // 如果x沒有右孩子。則x有以下兩種可能：
    // (01) x是"一個左孩子"，則"x的後繼結點"為 "它的父結點"。
    // (02) x是"一個右孩子"，則查找"x的最低的父結點，并且該父結點要具有左孩子"，找到的這個"最低的父結點"就是"x的後繼結點"。
    Node* y = x->parent;
    while ((y!=NULL) && (x==y->right))
    {
        x = y;
        y = y->parent;
    }

    return y;
}

6. 插入

插入節點的代碼

static Node* bstree_insert(BSTree tree, Node *z)
{
    Node *y = NULL;
    Node *x = tree;

    // 查找z的插入位置
    while (x != NULL)
    {
        y = x;
        if (z->key < x->key)
            x = x->left;
        else
            x = x->right;
    }

    z->parent = y;
    if (y==NULL)
        tree = z;
    else if (z->key < y->key)
        y->left = z;
    else
        y->right = z;

    return tree;
}

Node* insert_bstree(BSTree tree, Type key)
{
    Node *z;    // 建立結點

    // 如果建立結點失敗，則傳回。
    if ((z=create_bstree_node(key, NULL, NULL, NULL)) == NULL)
        return tree;

    return bstree_insert(tree, z);
}

bstree_insert(tree, z)是内部函數，它的作用是：将結點(z)插入到二叉樹(tree)中，并傳回插入節點後的根節點。

insert_bstree(tree, key)是對外接口，它的作用是：在樹中新增節點，key是節點的值；并傳回插入節點後的根節點。

注：本文實作的二叉查找樹是允許插入相同鍵值的節點的！若使用者不希望插入相同鍵值的節點，将bstree_insert()修改為以下代碼即可。

static Node* bstree_insert(BSTree tree, Node *z)
{
    Node *y = NULL;
    Node *x = tree;

    // 查找z的插入位置
    while (x != NULL)
    {
        y = x;
        if (z->key < x->key)
            x = x->left;
        else  if (z->key > x->key)
            x = x->right;
        else
        {
            free(z); // 釋放之前配置設定的系統。
            return tree;
        }
    }

    z->parent = y;
    if (y==NULL)
        tree = z;
    else if (z->key < y->key)
        y->left = z;
    else
        y->right = z;

    return tree;
}
  1. 删除

删除節點的代碼

static Node* bstree_delete(BSTree tree, Node *z)
{
    Node *x=NULL;
    Node *y=NULL;

    if ((z->left == NULL) || (z->right == NULL) )
        y = z;
    else
        y = bstree_successor(z);

    if (y->left != NULL)
        x = y->left;
    else
        x = y->right;

    if (x != NULL)
        x->parent = y->parent;

    if (y->parent == NULL)
        tree = x;
    else if (y == y->parent->left)
        y->parent->left = x;
    else
        y->parent->right = x;

    if (y != z) 
        z->key = y->key;

    if (y!=NULL)
        free(y);

    return tree;
}

Node* delete_bstree(BSTree tree, Type key)
{
    Node *z, *node; 

    if ((z = bstree_search(tree, key)) != NULL)
        tree = bstree_delete(tree, z);

    return tree;
}

bstree_delete(tree, z)是内部函數，它的作用是：删除二叉樹(tree)中的節點(z)，并傳回删除節點後的根節點。

delete_bstree(tree, key)是對外接口，它的作用是：在樹中查找鍵值為key的節點，找到的話就删除該節點；并傳回删除節點後的根節點。

8. 列印

列印二叉樹的代碼

void print_bstree(BSTree tree, Type key, int direction)
{
    if(tree != NULL)
    {
        if(direction==0)    // tree是根節點
            printf("%2d is root\n", tree->key);
        else                // tree是分支節點
            printf("%2d is %2d's %6s child\n", tree->key, key, direction==1?"right" : "left");

        print_bstree(tree->left, tree->key, -1);
        print_bstree(tree->right,tree->key,  1);
    }
}

print_bstree(tree, key, direction)的作用是列印整顆二叉樹(tree)。其中，tree是二叉樹節點，key是二叉樹的鍵值，而direction表示該節點的類型：

direction為 0，表示該節點是根節點;

direction為-1，表示該節點是它的父結點的左孩子;

direction為 1，表示該節點是它的父結點的右孩子。

9. 銷毀二叉樹

銷毀二叉樹的代碼

void destroy_bstree(BSTree tree)
{
    if (tree==NULL)
        return ;

    if (tree->left != NULL)
        destroy_bstree(tree->left);
    if (tree->right != NULL)
        destroy_bstree(tree->right);

    free(tree);
}

整體代碼：

二叉查找樹的頭檔案(bstree.h)

#ifndef _BINARY_SEARCH_TREE_H_
#define _BINARY_SEARCH_TREE_H_

typedef int Type;

typedef struct BSTreeNode{
    Type   key;                    // 關鍵字(鍵值)
    struct BSTreeNode *left;    // 左孩子
    struct BSTreeNode *right;    // 右孩子
    struct BSTreeNode *parent;    // 父結點
}Node, *BSTree;

// 前序周遊"二叉樹"
void preorder_bstree(BSTree tree);
// 中序周遊"二叉樹"
void inorder_bstree(BSTree tree);
// 後序周遊"二叉樹"
void postorder_bstree(BSTree tree);

// (遞歸實作)查找"二叉樹x"中鍵值為key的節點
Node* bstree_search(BSTree x, Type key);
// (非遞歸實作)查找"二叉樹x"中鍵值為key的節點
Node* iterative_bstree_search(BSTree x, Type key);

// 查找最小結點：傳回tree為根結點的二叉樹的最小結點。
Node* bstree_minimum(BSTree tree);
// 查找最大結點：傳回tree為根結點的二叉樹的最大結點。
Node* bstree_maximum(BSTree tree);

// 找結點(x)的後繼結點。即，查找"二叉樹中資料值大于該結點"的"最小結點"。
Node* bstree_successor(Node *x);
// 找結點(x)的前驅結點。即，查找"二叉樹中資料值小于該結點"的"最大結點"。
Node* bstree_predecessor(Node *x);

// 将結點插入到二叉樹中，并傳回根節點
Node* insert_bstree(BSTree tree, Type key);

// 删除結點(key為節點的值)，并傳回根節點
Node* delete_bstree(BSTree tree, Type key);

// 銷毀二叉樹
void destroy_bstree(BSTree tree);

// 列印二叉樹
void print_bstree(BSTree tree, Type key, int direction);

#endif

二叉查找樹的實作檔案(bstree.c)

/**
 * 二叉搜尋樹(C語言): C語言實作的二叉搜尋樹。
 *
 */

#include <stdio.h>
#include <stdlib.h>
#include "bstree.h"


/*
 * 前序周遊"二叉樹"
 */
void preorder_bstree(BSTree tree)
{
    if(tree != NULL)
    {
        printf("%d ", tree->key);
        preorder_bstree(tree->left);
        preorder_bstree(tree->right);
    }
}

/*
 * 中序周遊"二叉樹"
 */
void inorder_bstree(BSTree tree)
{
    if(tree != NULL)
    {
        inorder_bstree(tree->left);
        printf("%d ", tree->key);
        inorder_bstree(tree->right);
    }
}

/*
 * 後序周遊"二叉樹"
 */
void postorder_bstree(BSTree tree)
{
    if(tree != NULL)
    {
        postorder_bstree(tree->left);
        postorder_bstree(tree->right);
        printf("%d ", tree->key);
    }
}

/*
 * (遞歸實作)查找"二叉樹x"中鍵值為key的節點
 */
Node* bstree_search(BSTree x, Type key)
{
    if (x==NULL || x->key==key)
        return x;

    if (key < x->key)
        return bstree_search(x->left, key);
    else
        return bstree_search(x->right, key);
}

/*
 * (非遞歸實作)查找"二叉樹x"中鍵值為key的節點
 */
Node* iterative_bstree_search(BSTree x, Type key)
{
    while ((x!=NULL) && (x->key!=key))
    {
        if (key < x->key)
            x = x->left;
        else
            x = x->right;
    }

    return x;
}

/* 
 * 查找最小結點：傳回tree為根結點的二叉樹的最小結點。
 */
Node* bstree_minimum(BSTree tree)
{
    if (tree == NULL)
        return NULL;

    while(tree->left != NULL)
        tree = tree->left;
    return tree;
}
 
/* 
 * 查找最大結點：傳回tree為根結點的二叉樹的最大結點。
 */
Node* bstree_maximum(BSTree tree)
{
    if (tree == NULL)
        return NULL;

    while(tree->right != NULL)
        tree = tree->right;
    return tree;
}

/* 
 * 找結點(x)的後繼結點。即，查找"二叉樹中資料值大于該結點"的"最小結點"。
 */
Node* bstree_successor(Node *x)
{
    // 如果x存在右孩子，則"x的後繼結點"為 "以其右孩子為根的子樹的最小結點"。
    if (x->right != NULL)
        return bstree_minimum(x->right);

    // 如果x沒有右孩子。則x有以下兩種可能：
    // (01) x是"一個左孩子"，則"x的後繼結點"為 "它的父結點"。
    // (02) x是"一個右孩子"，則查找"x的最低的父結點，并且該父結點要具有左孩子"，找到的這個"最低的父結點"就是"x的後繼結點"。
    Node* y = x->parent;
    while ((y!=NULL) && (x==y->right))
    {
        x = y;
        y = y->parent;
    }

    return y;
}
 
/* 
 * 找結點(x)的前驅結點。即，查找"二叉樹中資料值小于該結點"的"最大結點"。
 */
Node* bstree_predecessor(Node *x)
{
    // 如果x存在左孩子，則"x的前驅結點"為 "以其左孩子為根的子樹的最大結點"。
    if (x->left != NULL)
        return bstree_maximum(x->left);

    // 如果x沒有左孩子。則x有以下兩種可能：
    // (01) x是"一個右孩子"，則"x的前驅結點"為 "它的父結點"。
    // (01) x是"一個左孩子"，則查找"x的最低的父結點，并且該父結點要具有右孩子"，找到的這個"最低的父結點"就是"x的前驅結點"。
    Node* y = x->parent;
    while ((y!=NULL) && (x==y->left))
    {
        x = y;
        y = y->parent;
    }

    return y;
}

/*
 * 建立并傳回二叉樹結點。
 *
 * 參數說明：
 *     key 是鍵值。
 *     parent 是父結點。
 *     left 是左孩子。
 *     right 是右孩子。
 */
static Node* create_bstree_node(Type key, Node *parent, Node *left, Node* right)
{
    Node* p;

    if ((p = (Node *)malloc(sizeof(Node))) == NULL)
        return NULL;
    p->key = key;
    p->left = left;
    p->right = right;
    p->parent = parent;

    return p;
}

/* 
 * 将結點插入到二叉樹中
 *
 * 參數說明：
 *     tree 二叉樹的根結點
 *     z 插入的結點
 * 傳回值：
 *     根節點
 */
static Node* bstree_insert(BSTree tree, Node *z)
{
    Node *y = NULL;
    Node *x = tree;

    // 查找z的插入位置
    while (x != NULL)
    {
        y = x;
        if (z->key < x->key)
            x = x->left;
        else
            x = x->right;
    }

    z->parent = y;
    if (y==NULL)
        tree = z;
    else if (z->key < y->key)
        y->left = z;
    else
        y->right = z;

    return tree;
}

/* 
 * 建立結點(key)，并将其插入到二叉樹中
 *
 * 參數說明：
 *     tree 二叉樹的根結點
 *     key 插入結點的鍵值
 * 傳回值：
 *     根節點
 */
Node* insert_bstree(BSTree tree, Type key)
{
    Node *z;    // 建立結點

    // 如果建立結點失敗，則傳回。
    if ((z=create_bstree_node(key, NULL, NULL, NULL)) == NULL)
        return tree;

    return bstree_insert(tree, z);
}

/* 
 * 删除結點(z)，并傳回根節點
 *
 * 參數說明：
 *     tree 二叉樹的根結點
 *     z 删除的結點
 * 傳回值：
 *     根節點
 */
static Node* bstree_delete(BSTree tree, Node *z)
{
    Node *x=NULL;
    Node *y=NULL;

    if ((z->left == NULL) || (z->right == NULL) )
        y = z;
    else
        y = bstree_successor(z);

    if (y->left != NULL)
        x = y->left;
    else
        x = y->right;

    if (x != NULL)
        x->parent = y->parent;

    if (y->parent == NULL)
        tree = x;
    else if (y == y->parent->left)
        y->parent->left = x;
    else
        y->parent->right = x;

    if (y != z) 
        z->key = y->key;

    if (y!=NULL)
        free(y);

    return tree;
}

/* 
 * 删除結點(key為節點的鍵值)，并傳回根節點
 *
 * 參數說明：
 *     tree 二叉樹的根結點
 *     z 删除的結點
 * 傳回值：
 *     根節點
 */
Node* delete_bstree(BSTree tree, Type key)
{
    Node *z, *node; 

    if ((z = bstree_search(tree, key)) != NULL)
        tree = bstree_delete(tree, z);

    return tree;
}

/*
 * 銷毀二叉樹
 */
void destroy_bstree(BSTree tree)
{
    if (tree==NULL)
        return ;

    if (tree->left != NULL)
        destroy_bstree(tree->left);
    if (tree->right != NULL)
        destroy_bstree(tree->right);

    free(tree);
}

/*
 * 列印"二叉樹"
 *
 * tree       -- 二叉樹的節點
 * key        -- 節點的鍵值 
 * direction  --  0，表示該節點是根節點;
 *               -1，表示該節點是它的父結點的左孩子;
 *                1，表示該節點是它的父結點的右孩子。
 */
void print_bstree(BSTree tree, Type key, int direction)
{
    if(tree != NULL)
    {
        if(direction==0)    // tree是根節點
            printf("%2d is root\n", tree->key);
        else                // tree是分支節點
            printf("%2d is %2d's %6s child\n", tree->key, key, direction==1?"right" : "left");

        print_bstree(tree->left, tree->key, -1);
        print_bstree(tree->right,tree->key,  1);
    }
}

#二叉查找樹的測試程式(btree_test.c)

/**
 * C 語言: 二叉查找樹
 *
 */

#include <stdio.h>
#include "bstree.h"

static int arr[]= {1,5,4,3,2,6};
#define TBL_SIZE(a) ( (sizeof(a)) / (sizeof(a[0])) )

void main()
{
    int i, ilen;
    BSTree root=NULL;

    printf("== 依次添加: ");
    ilen = TBL_SIZE(arr);
    for(i=0; i<ilen; i++)
    {
        printf("%d ", arr[i]);
        root = insert_bstree(root, arr[i]);
    }

    printf("\n== 前序周遊: ");
    preorder_bstree(root);

    printf("\n== 中序周遊: ");
    inorder_bstree(root);

    printf("\n== 後序周遊: ");
    postorder_bstree(root);
    printf("\n");

    printf("== 最小值: %d\n", bstree_minimum(root)->key);
    printf("== 最大值: %d\n", bstree_maximum(root)->key);
    printf("== 樹的詳細資訊: \n");
    print_bstree(root, root->key, 0);

    printf("\n== 删除根節點: %d", arr[3]);
    root = delete_bstree(root, arr[3]);

    printf("\n== 中序周遊: ");
    inorder_bstree(root);
    printf("\n");

    // 銷毀二叉樹
    destroy_bstree(root);
}
大話資料結構
上一篇: 大話pixhawk運作Ardu:Copter啟動過程
下一篇: 大話oraclerac叢集、高可用性、備份與恢複_如何做到 10T 叢集資料安全備份、1GB/s 快速恢複？...

繼續閱讀