树的一些操作，杂记

树的一些操作，杂记

//新建结点数据类型 

typedef struct{

    typename data;
    node* lchild;
    node* rchild;



}Node;


//新建树结点 

Node* new_node(int v)
{
    Node* node=new Node;
    node->data=v;
    node->lchild=node->rchild=NULL;

    return node;




}

//查找并修改数据 

void search(Node* root,int x,int  newdata)
{
    if(root==NULL)
    {
        return; //空树，死胡同 

    }

    if(root->data==x)
    {

        root->data=newdata;

    }

    search(root->lchild,x,newdata);
    search(root->rchild,x,newdata);




}

//插入数据 


void  insert(Node* &root,int x)
{
    if(root==NULL)
    {
        root= new_node(x);

        return;     //空树，也就是查找失败，也就是插入位置 

    }


    if(由二叉树的性质，x应该插在左子树)
    {

        insert(root->lchild,x);

    }
    else
    {
        insert(root->rchild,x);


    }




}

//建树 

Node* create(int data[],int n)
{
    Node* root=NULL;

    for(int i=0;i<n;i++) 
    {
        insert(root,data[i]);


    }
    return root;


}

//前序遍历 

void preorder(Node* root)
{
    if(root==NULL)
    {
        return;

    }

    printf("%d",root->data);

    preorder(root->lchild);
    preorder(root->rchild);



}


//层序遍历 

void layerorder(Node* root)
{
    queue<Node*> queue;

    queue.push(root);

    while(!queue.empty())
    {
        Node* now=queue.front();
        queue.pop();


        printf("%d",now->data);


        if(now->lchild!=NULL)
        {
            queue.push(now->lchild);

        }

        if(now->rchild!=NULL)
        {

            queue.push(now->rchild);

        }





    }






}



//加入 层 的树结点。 

struct ndoe{

    int data;   //数据域 
    int layer;  //层次
    node* lchild;
    node* rchild; 


};



//新的层序遍历 

void layerorder(Node* root)
{

    queue<Node*> queue;

    root->layer=1;

    queue.push(root);

    while(!queue.empty())
    {
        Node* now=queue.front();

        queue.pop();

        printf("%d",now->data);

        if(now->lchild!=NULL)
        {

            now->lchild->layer=now->layer+1;
            queue.push(now->lchild);

        }

        if(now->rchild!=NULL)
        {

            now->rchild->layer=now->layer+1;

            queue.push(now->rchild);

        }





    }








}




//已知当前 先序序列 和 中序序列， 返回树的根结点地址。

Node* create(int preL,int preR,int inL,int inR)
{
    if(preL>preR)
    {

        return NULL;

    }

    Node* root=new Node;        //新建一个新的结点，用来保存二叉树的根结点

    root->data=pre[preL];   //新结点的数据域为根结点的值 

    int k;

    //在中序序列中找到in[k] == pre[L]的结点 


    for(k=inL;k<=inR;k++) 
    {
        if(in[k] == pre[preL] )
        {
            break;

        }

    }

    //左子树的结点个数 
    int num_left = k-inL;

    root->lchild=create(prL+1,preL+num_left,inL,k-1);

    root->rchild=create(preL+num_left+1,preR,k+1,inR); 





}