ツリーのその他の操作

以前は二叉木の作成,非再帰遍歴,再帰遍歴を実現した.次のような他の操作を追加します.

木を1本破棄

木の深さ(高さ)

を計算する

.リーフノードの個数を計算する

すべてのノードの個数を計算する

複製ツリー

具体的には、コードを参照してください.

#include 
#include 
typedef struct Node
{
    int data;
    struct Node* lchild;
    struct Node* rchild;
}Node;
//   
Node* create_tree()
{
    int _data;
    scanf("%d",&_data);
    if(_data==100)
    {
        return NULL;
    }
    Node* root=(Node*)malloc(1*sizeof(Node));
    if(root==NULL)
    {
        return ;
    }
    root->data=_data;
    root->lchild=create_tree();
    root->rchild=create_tree();
    return root;
}
//     
void pre_print(Node* root)
{
    if(root==NULL)
    {
        return ;
    }
    printf("%d\t",root->data);
    pre_print(root->lchild);
    pre_print(root->rchild);
}
/****************************************************/
//     
void free_tree(Node* root)
{
    if(root==NULL)
        return ;
    free_tree(root->lchild);
    free_tree(root->rchild);
    free(root);
    root=NULL;
}
//      （  ）
int depth(Node* root)
{
    if(root==NULL)
        return 0;
    int l=depth(root->lchild);
    int r=depth(root->rchild);
    if(l>r)
    {
        return l+1;
    }
    return r+1;
}
//         
int count_leaf(Node* root)
{
    if(root==NULL)
    {
        return 0;
    }
    if(root->lchild==NULL && root->rchild==NULL)
    {
        return 1;
    }
    else
    {
        return count_leaf(root->lchild)+count_leaf(root->rchild);
    }
}
//         
int count_all_node(Node* root)
{
    if(root==NULL)
    {
        return 0;
    }
    return count_all_node(root->lchild)+count_all_node(root->rchild)+1;
}
//     
Node* copy_tree(Node* root)
{
    if(root==NULL)
    {
        return NULL;
    }
    Node* l_tree,*r_tree,*root_tree;
    l_tree=copy_tree(root->lchild);
    r_tree=copy_tree(root->rchild);
    root_tree=malloc(1*sizeof(Node));
    root_tree->data=root->data;
    root_tree->lchild=l_tree;
    root_tree->rchild=r_tree;
    return root_tree;
}
int main(int argc, char const *argv[])
{
    Node* root=create_tree();
    pre_print(root);
    printf("
");
    printf("Depth:%d
",depth(root));
    printf("count_leaf:%d
",count_leaf(root));
    printf("count_all_node:%d
",count_all_node(root));
    Node* copy_root=copy_tree(root);
    pre_print(root);
    printf("
");
    return 0;
}