資料結構筆記（3）樹——二叉查找樹

樹

1. 定義： 一顆樹是一些節點的結合，這個集合可以是空集，若非空，則一棵樹由稱為（root）的根節點與0個或多個非空的子樹組成。一棵樹由N個節點與N-1條邊構成。
2. 深度：從根到n的唯一路徑的長度，根的深度為0。
3. 高度：從n到一片樹葉最長路徑的長，葉的高度為0。

父子兄弟樹

typedef struct TreeNode *PtrToNode;
typedef struct treeNode
{//父子兄弟樹
    int element;//資料域
    PtrToNode  firstChild;//長子
    PtrToNode  nextSibling;//下一個兄弟姐妹
} TreeNode;
           

周遊方式

1. 先序周遊（preorder traversal）: 先輸出根節點，然後周遊左子樹，最後周遊右子樹。
2. 中序周遊（inorder traversal）： 先周遊左子樹，再輸出根節點，最後周遊右子樹（在特定情況下的二叉查找樹通過該周遊方式可以順序輸出整個樹）。
3. 後序周遊（postorder traversal）： 先周遊左子樹，再周遊右子樹，最後周遊根。

   

則圖示的數按照：

1. 先序周遊：10 5 8 6 15 12 11 22

2. 中序周遊：5 6 8 10 11 12 15 22

3. 後序周遊：6 8 5 11 12 22 15 10

二叉樹：

1. 每個節點都不能有多于兩個的兒子。
2. 實作：

struct binTreeNode
{
    int element;
    struct binTreeNode *left;//左子樹
    struct binTreeNode *right;//右子樹
};
           

利用棧與二叉樹實作表達式樹：

（略）

二叉樹的子集：二叉查找樹

1. 性質：對于樹中的每個節點X，它的左子樹中所有關鍵值小于X的關鍵字值，它的右子樹中所有關鍵字值大于X的關鍵字值。
2. 遊标（數組）實作：

typedef struct tREE
{
    int data;
    int left;
    int right;
} TREE;
//先序周遊、中序周遊、後序周遊
void pre_order(int root);
void mid_order(int root);
void pos_order(int root);

//查找key節點、查找最小節點
int find(int key,int root);
int findMin(int root);

//插入X（作為數組引用标簽）
int insert(int X,int root);

//删除X（作為數組引用标簽）
int delete(int X,int root);

void pre_order(int root)
{
    if(root<);
    else
    {
        printf("%d ",tr[root].data);
        pre_order(tr[root].left);
        pre_order(tr[root].right);
    }
}

void mid_order(int root)
{
    if(root<);
    else
    {
        mid_order(tr[root].left);
        printf("%d ",tr[root].data);
        mid_order(tr[root].right);
    }
}

void pos_order(int root)
{
    if(root<);
    else
    {
        pos_order(tr[root].left);
        pos_order(tr[root].right);
        printf("%d ",tr[root].data);
    }
}

int find(int key,int root)
{
    if(root<)
        return -;
    else
    {
        if(key<tr[root].data)
            root=find(key,tr[root].left);
        else if(key>tr[root].data)
            root=find(key,tr[root].right);
        return root;
    }
}

int findMin(int root)
{
    if(tr[root].left<)
        return root;
    else return findMin(tr[root].left);
}

int insert(int x,int root)
{
    if(root<)
        return x;
    else
    {
        if(tr[x].data<tr[root].data)
            tr[root].left=insert(x,tr[root].left);
        else if(tr[x].data>tr[root].data)
            tr[root].right=insert(x,tr[root].right);

        return root;
    }
}

int delete(int x,int root)
{
    int Tmp;
    if(root<)
        return -;
    else if(tr[x].data>tr[root].data)
         tr[root].right=delete(x,tr[root].right);
    else if(tr[x].data<tr[root].data)
         tr[root].left=delete(x,tr[root].left);
    else if(tr[root].left>&&tr[root].right>)
    {//if the leaf to be deleted has children
        Tmp=findMin(tr[root].right);
        tr[root].data=tr[Tmp].data;
        tr[root].right=delete(tr[root].data,tr[root].right);
    }
    else if(tr[root].left>)
        return tr[root].left;
    else return tr[root].right;

    return root;
}
           

1. 實作（連結清單）：

struct binTreeNode
{
    int element;
    struct binTreeNode *left;//左子樹
    struct binTreeNode *right;//右子樹
};
/**
 * 二叉查找樹性質：對于樹中的每個節點X，它的左子樹中所有關鍵值小于X的關鍵字值，它的右子樹中所有關鍵字值大于X的關鍵字值
 */
struct binTreeNode;
typedef struct binTreeNode* Position;
typedef struct binTreeNode* SearchTree;

SearchTree MakeEmpty(SearchTree T);
Position Find(int X,SearchTree T);
Position FindFather(int X,SearchTree T);
Position FindMin(SearchTree T);
Position FindMax(SearchTree T);
SearchTree Insert(int X,SearchTree T);
SearchTree Delete(int X,SearchTree T);
int Retrieve(Position P);

SearchTree MakeEmpty(SearchTree T)
{
    if(T!=NULL)
    {
        MakeEmpty(T->left);
        MakeEmpty(T->right);
        free(T);
    }

    return NULL;
}

Position Find(int X,SearchTree T)
{
    if(T==NULL)
        return NULL;
    if(X<T->element)
        return Find(X,T->left);
    else if(X>T->element)
        return Find(X,T->right);
    else
        return T;
}

Position FindFather(int X,SearchTree T)
{

}

Position FindMax(SearchTree T)
{//遞歸寫法
    if(T==NULL)
        return NULL;
    if(T->right==NULL)
        return T;
    else return FindMax(T->right);
}

Position FindMin(SearchTree T)
{//疊代寫法
    if(T!=NULL)
        while(T->left!=NULL)
            T=T->left;

    return T;
}

SearchTree Insert(int X,SearchTree T)
{
    if(T==NULL)
    {//此處注意：malloc()配置設定空間時所傳遞的sizeof()内應為結構體struct binTreeNode 而非指針SearchTree。
        //T = (binTreeNode*)(malloc(sizeof(struct binTreeNode)));
        //T=(SearchTree)malloc(sizeof(SearchTree));
        T=malloc(sizeof(struct binTreeNode));
       // T=malloc(sizeof())
        if(T==NULL)
            __mingw_printf("Out of Space");
            //頭檔案.h寫法，可改成printf();
        else
        {
            T->element=X;
            T->left=T->right=NULL;
        }
    }
    else if(X<T->element)
        T->left=Insert(X,T->left);
    else if(X>T->element)
        T->right=Insert(X,T->right);

    return T;
}

SearchTree Delete(int X,SearchTree T)
{
    Position TmpCell;

    if(T==NULL)
    {
        __mingw_printf("Element not found");
        return NULL;
    }

    else if(X<T->element)
        T->left=Delete(X,T->left);
    else if(X>T->element)
        T->right=Delete(X,T->right);
    else if(T->left&&T->right)
    {
        TmpCell=FindMin(T->right);
        T->element=TmpCell->element;
        T->right=Delete(T->element,T->right);
    } else
    {
        TmpCell=T;
        if(T->left==NULL)
            T=T->right;
        else if(T->right==NULL)
            T=T->left;
        free(TmpCell);
    }

    return T;
}