Thread: can anyone teach me how to convert a general tree to binary tree and vice versa?

  1. #1
    Registered User
    Join Date
    Aug 2007
    Posts
    1

    Wink can anyone teach me how to convert a general tree to binary tree and vice versa?

    Actually im really confused about converting a general tree to binary tree and vice versa as well...can anyone give me an example on how to do that?

  2. #2
    The larch
    Join Date
    May 2006
    Posts
    3,573
    A general tree is an unordered tree?

    You could iterate the unordered tree and insert things into the binary tree as usual.

    Since that loses information about the original ordering you might not be able to get that back. But if it is a binary tree, the data is already in a (general) tree?

    Or do I misunderstand something?
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  3. #3
    l'Anziano DavidP's Avatar
    Join Date
    Aug 2001
    Location
    Plano, Texas, United States
    Posts
    2,743
    It depends what you consider a "general tree" and what you consider a "binary tree"

    I assume when you say "binary tree", you probably really mean "binary search tree"

    Here are some definitions taken from The Dictionary of Algorithms and Data Structures:

    Tree: A data structure accessed beginning at the root node. Each node is either a leaf or an internal node. An internal node has one or more child nodes and is called the parent of its child nodes. All children of the same node are siblings. Contrary to a physical tree, the root is usually depicted at the top of the structure, and the leaves are depicted at the bottom.

    Binary Tree: A tree with at most two children for each node.

    Binary Search Tree: A binary tree where every node's left subtree has keys less than the node's key, and every right subtree has keys greater than the node's key.

    So...now that we have those different terms defined, what do you really want? To convert a tree to a binary tree, you need to take all your nodes, make one of them a root node, and then make sure it has two children or less, and all of its children also have two children or less.

    To take a binary tree (which I think you are referring to as a "general tree") and convert it to a binary search tree, you need to take all your nodes, and make sure the values in each node are on the left of the root if they are less than the value of the root or on the right of the root if they are greater than the value of the root.
    My Website

    "Circular logic is good because it is."

Popular pages Recent additions subscribe to a feed