DOCX

The C language implementation of binary tree

By Joanne Woods,2015-02-07 09:02
11 views 0
The C language implementation of binary tree

    Landpack

    Binary tree, usually should is the basis of the research of other complicated data structure.Often, therefore, we should be proficient in it, and not understand;May, of course, not everyone agree with this point of view, and even some people think that

    understand the data structure!There is no need to study how to implement, because most high-level language already contains very good with the implementation of the interface, can be called directly.I have difficult to understand why some classmates so

    hard to learning algorithm, and then to participate in the ACM contest, I even the most basic Fibonacci cannot achieve.But I still

    heart laugh at them, because I was studying Linux system programming.I think I'm doing is the right that matters.In fact, now I

    think algorithm is a reflection of a programmer's basic diathesis;

    Come on!Areas, to continue our binary tree 04 version;

    I would like to end in this version, but the binary tree was too much content.

    The story begins:

    Project manager said, you see the last time you write the function of the binary tree display very image!

    I don't have too much explanation, the BOSS will see come out is the structure of the tree;

    So, we are all very believe your next task will be completed very good;

    Task

    1, we need a destruction of the function of the whole tree;

    2, we need three common traversal way;

    3, we also need a called level traversal functions;

    4, we need you to tell me something about how to rotate to the tree;

    Problem

    Destruction of trees, is for the release of every node;

    Therefore, we need to traverse each node;

    But unlike search traversal, we will delete the node, so we must want to clear first release which;

    Don't let other nodes run! "startle";

    Solution

    Understand the structure of the can is good enough to destroy it, first take a look at the

    picture below;

    We obviously should not first remove 3 nodes;

    We should be first remove the leaf node;

    So we can use a technique called after sequence traversal solution;

    So we are trying to remove a tree, we all know, trees generally can be solved using

    recursive operation;

    So, first of all, the recursive thinking how to solve;

void destroy_recursive(Node * root)

    {

     if (root != NULL){

     // TODO

     }

    }

    As we know, only this node is not null, only can be said to be destroyed;

    So, first to habits to empty, and then on to the next step;

void destroy_recursive(Node * root)

    {

     if (root != NULL){

     free (root);

     }

    }

    Like this, perhaps this is your first idea.But think about it, for the tree you just cut the

    root of the tree.

    You don't climb the tree to pick fruit, this will be waste in (a lot of memory leak);

void destroy_recursive(Node * root)

    {

     if (root != NULL){

     destroy_recursive(root ->link[ 0 ]);

     destroy_recursive(root ->link[ 1 ]);

     free (root);

     }

    }

    To do this, you can smoothly from the root to the top of the tree, picked all the fruit after;

    Also cut the branches above, has been down to the ground during the year when the root also throw;

    Task will be completed;

    But, your function due to naked is a recursive function, so you need to wrap it up.

void destroy(Tree * tree)

    {

     destroy_recursive(tree -> root);

    }

    This function we will stay in the test, as has just invented a bomb last we study through ignition;

    Fried otherwise we all don't know how to reengineering;

    Problem

    Just now, we have used a recursive traversal.

    Obviously recursive solution to the problem of the tree is really handy when;

    For three common traversal is also very simple, and it is very similar;

void preorder_recursive(Node * root)

    {

     if (root != NULL){

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

     preorder_recursive(root ->link[ 0 ]);

     preorder_recursive(root ->link[ 1 ]);

     }

}

void preorder(Tree * tree)

    {

     preorder_recursive(tree -> root); }

    The preorder traversal is above, order and the order in if you already know how to write,

    you'd better don't look down.

    In the sequence traversal:

    void inorder_recursive(Node * root) {

     if (root != NULL){

     inorder_recursive(root ->link[ 0 ]);

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

     inorder_recursive(root ->link[ 1 ]);

     }

    }

void inorder(Tree * tree)

    {

     inorder_recursive(tree -> root); }

    After the sequence traversal:

    void postorder_recursive(Node * root) {

     if (root != NULL){

     postorder_recursive(root ->link[ 0 ]);

     postorder_recursive(root ->link[ 1 ]);

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

     }

    }

void postorder(Tree * tree)

    {

     postorder_recursive(tree -> root); }

    Okay! A task and complete;

    Problem

    Level traversal is special, we can not use a recursive solution;

void level_order(Tree * tree)

    {

     Node *it = tree-> root;

     Node *queue[ 10 ];

     int current = 0 ;

     int after_current = 0 ;

     if (it == NULL){

     return ;

     }

     // TODO

}

    First explain our local variables, these variables are called in to help you solve problems;

    Let me introduce myself;

    Hey, my name is queue array, is my type Node type, because I will store the Node type of the data, I function is to keep your current access to the Node;

    Hello, my name is current, the type is the basic type, I mainly responsible for recording the current which one node in the tree;

    Wow, I'm after_current, I'm sorry to late.My job is very simple, is responsible for following the current record before it passes through the latest nodes of a;

    Let's look at our implementation plan, put the figure and then opens;

    Level of access is unable to

    The first layer, 3

    The second floor, 1, 4

    The third layer, 0, 2

    Ok, we already know in order to achieve the effect;

    Current you first and queue the current it records;

    Our it'll probably want to change yourself.

queue[current++]=it;

    Current said, I have recorded, and I are now ready to record a message, I am now is 1 ",

    ";

void level_order(Tree * tree)

    {

     Node *it = tree-> root;

     Node *queue[ 10 ];

     int current = 0 ;

     int after_current = 0 ;

     if (it == NULL){

     return ;

     }

     queue[current ++] = it;

     while (current != after_current){

     // TODO

     }

    }

    After_current very impatiently say to the while, what the heck are you doing, you don't

    have to let me compared to the current?You know he is older than me in advance;

    While very cordial said don't worry, you only according to my way, you will catch up

    with it;

    void level_order(Tree * tree) {

     Node *it = tree-> root;

     Node *queue[ 10 ];

     int current = 0 ;

     int after_current = 0 ;

     if (it == NULL){

     return ;

     }

     queue[current ++] = it;

     while (current != after_current){

     it = queue[after_current++ ];

     printf( " %d\n " ,it-> data);

     // TODO

     }

    }

    Sure enough, after_current also long one year old;

    At this point, the current is not happy, he also don't back to go forward.

    I'm sorry, please look at a graph, this current at this time should go where?

    It can choose from the first, also can go first from the right of the left side;

    Assumes that the first from the left;

void level_order(Tree * tree)

    {

     Node *it = tree-> root;

     Node *queue[ 10 ];

     int current = 0 ;

     int after_current = 0 ;

     if (it == NULL){

     return ;

     }

Report this document

For any questions or suggestions please email
cust-service@docsford.com