二叉树操作

有以下几点需要注意：

1.为根节点分配内存时，需要在函数中为一个指针分配内存，再将该指针作为返回值，用在主函数中定义的根节点指针接收该返回值。(不能将指针作为参数还妄想要给他分配内存)

2.该程序在linux 64位操作系统上成功运行。

正文部分

0.二叉树节点的结构体

typedef struct Node Node;
struct Node
{
    int value;
    Node *left;
    Node *right;
    int lsign;
    int rsign;
};

1.二叉树的创建。

用-1表示每一个叶子节点的左右孩子的值，但-1并不会出现在二叉树中，你在给二叉树填值时可以先将其画出来，便于理解。

Node* create()
{
    int n;
    Node* root=NULL;
    printf("Input the value(quit when you input -1):");
    scanf("%d",&n);
    if(n==-1)
    return root;
    else{
        root=(Node*)malloc(sizeof(Node));
        root->value=n;
        root->lsign=0;
        root->rsign=0;
        root->left=create();
        root->right=create();
        return root;
    }
}

注意：需要在主函数中创建一个根指针用于接收该函数分配出的内存(即二叉树本身)。

2.前序遍历。

void list(Node* root)
{
    if(!root)
    return;
    printf("%d ",root->value);
    list(root->left);
    list(root->right);
}

3.中序遍历。

void list(Node* root)
{
    if(!root)
    return;
    list(root->left);
    printf("%d ",root->value);
    list(root->right);
}

4.后序遍历。

void list(Node* root)
{
    if(!root)
    return;
    list(root->left);
    list(root->right);
    printf("%d ",root->value);
}

5.二叉树的线索化及线索化之后的输出。

void Threading(Node* root)
{//以中序线索化为例
    if(root)
    {
        Threading(root->left);
        if(!root->left)
        {
            root->lsign=1;
            root->left=pre;
        }
        if(!pre->right)
        {
            pre->right=root;
            pre->rsign=1;
        }
        pre=root;
        Threading(root->right);
    }
}

void ThreadingList(Node* root)
{
    Node*p=root;
    while(p!=NULL)
    {
        while(p->lsign==0)
            p=p->left;
        printf("%d ",p->value);
        while(p->rsign==1)
        {
            p=p->right;
            printf("%d ",p->value);
        }
        p=p->right;
    }
}

注意：

        1.函数中的pre指针我是将其作为了全局变量；

        2.主函数中需要在引用该函数之前将pre指针指向root,即根指针。

6.层序遍历。

void layerlist(Node*root)
{
    Node* queue[100];
    int i=0,top=0;
    if(root){
        queue[top]=root;
    }
    while(i<=top)
    {
        if(queue[i]->left){
            queue[++top]=queue[i]->left;
        }
        if(queue[i]->right){
            queue[++top]=queue[i]->right;
        }
        i++;
    }
    for(int i=0;i<=top;i++)
    printf("%d ",queue[i]->value);
}

7.二叉树内存的释放。(普通的二叉树内存释放用后序遍历的思路很容易写出来，这里就不写了)

这里写出线索化之后的二叉树内存释放

void freeNode(Node*root)
{
    if(root!=NULL)
    {   
        if(root->lsign==0)//不通过前驱和后继
        freeNode(root->left);
        if(root->rsign==0)//不通过前驱和后继
        freeNode(root->right);
        free(root);
        root=NULL;
    }
}

注意在释放内存时不能通过前驱和后继。