数据结构笔记（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;
}