Flipping a binary tree using recursion

This is a discussion on Flipping a binary tree using recursion within the C++ Programming forums, part of the General Programming Boards category; can anyone give me some ideas on how i could flip a binary tree around using a recursive function..for example. ...

  1. #1
    Jim0669
    Guest

    Flipping a binary tree using recursion

    can anyone give me some ideas on how i could flip a binary tree around using a recursive function..for example.

    struct BinaryTreeNode
    {
    int data;
    BinaryTreeNode *left;
    BinaryTreeNode *right;
    };

    Example original tree: Example new tree:
    1 1
    / \ / \
    2 3 3 2
    / \ / \
    4 5 5 4

  2. #2
    Unregistered
    Guest
    old tree
    1
    /\
    2 3
    /\
    4 5

    new tree
    1
    /\
    3 2
    /\
    5 4

  3. #3
    Unregistered
    Guest

    Unhappy

    is it a binary tree? binary tree should be
    1
    \
    2
    \
    3
    \
    4
    \
    5

    according your data

  4. #4
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,801
    Unregistered said:

    is it a binary tree? binary tree should be
    1
    \
    2
    \
    3
    \
    4
    \
    5
    The way a binary tree looks depends on the order the items are added to a tree. If the numbers were added in order (least to greatest), then yes the tree would look like you describe.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  5. #5
    S­énior Member
    Join Date
    Jan 2002
    Posts
    982
    Copy the tree, then either do a pre-order traversal on the source copying to the destination by means of a post-order traversal, or do a post-order traversal of the source and a pre-order traversal of the destination.

  6. #6
    Budding Synth Programmer samGwilliam's Avatar
    Join Date
    Feb 2002
    Location
    Trefforest
    Posts
    368
    Originally posted by hk_mp5kpdw
    Unregistered said:



    The way a binary tree looks depends on the order the items are added to a tree. If the numbers were added in order (least to greatest), then yes the tree would look like you describe.
    ...which is where the height balancing comes in.

  7. #7
    S­énior Member
    Join Date
    Jan 2002
    Posts
    982
    Using a binary tree you can insert elements any way you like. A binary search tree orders the elements on insertion in some pre-defined manner.

  8. #8
    Unregistered
    Guest
    I have some code that could help. Let's see your code first.

    When I think height balancing I think AVL trees not binary trees.!!!

    Mr. c.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 0
    Last Post: 11-04-2006, 10:07 AM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 08:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21