CODEWITHSUNDEEP
c++tree
It's Just a Printer Driver
It's Just a Printer Driver

Reputation: 860

Copy binary tree in order

The code I wrote so far is:

void copyInOrder(TNode *orgTree, Tnode *& copyTree){
    if(orgTree !=NULL){
        copyInOrder(orgTree->left_link);
        //create leftmost node of tree but how to link to parent
        copyInOrder(orgTree->right_link);
    }
}

I dont know how to link to the parent to the nodes as its inorder.

Upvotes: 1

Views: 32295

Answers (5)

Arun
Arun

Reputation: 20383

Suppose orgTree points to root (2). For copying, we have to do the following:

alt text

  1. create a node at copyTree, and the copy the value 2 into it
  2. if orgTree->left != NULL, call copyInOrder( orgTree->left, copyTree->left );
  3. if orgTree->right != NULL, call copyInOrder( orgTree->right, copyTree->right );

BTW, this type of traversal is known as pre-order traversal, in-order traversal is different.

Upvotes: 5

Indinfer
Indinfer

Reputation: 97

I am not authorized to flag or comment. Maybe someone who is authorized will take action on the hijacked link. And then, maybe delete my post (this post) since it will no longer be relevant.

Referring to the post of Oct 12 '10 at 21:02 by Arun:

I inspected the link (i.e., right-click, then click on "inspect"). The URL looks legitimate. However, when I actually click on the link, I get redirected to a completely different URL of a website that wants to download and install a plugin. Norton Security blocks the website. To me, it looks like the original link was hijacked.

The original post shows knowledge and helpfulness.

For safety, maybe we should change to google the search term "pre-order traversal."

Upvotes: 0

user10934677
user10934677

Reputation:

This is a recursive method that works and is simple

Tnode* CopyInOrder(Tnode* root){
    if(root == NULL){return NULL;}
    else{
        Tnode* temp = new Tnode;
        temp -> data = root -> data;
        temp -> left = copyInOrder(root -> left);
        temp -> right = copyInOrder(root -> right);
        return temp;
        }
}

Upvotes: 0

mohammad ghamgosar
mohammad ghamgosar

Reputation: 31

tnode *copy(tnode *root) {
     tnode *new_root;
     if(root!=NULL){
         new_root=new tnode;
         new_root->data=root->data;
         new_root->lchild=copy(root->lchild);
         new_root->rchild=copy(root->rchild);
     } else return NULL;
     return new_root;
 }

Upvotes: 3

Alpha
Alpha

Reputation: 7868

I think it would be something like this.

void copyInOrder(TNode *orgTree, Tnode *& copyTree){
    if(orgTree !=NULL){
        //left side
        TNode newLeftNode = cloneNode(orgTree->left_link);
        copyTree->left_link = newLeftNode;
        copyInOrder(orgTree->left_link, copyTree->left_link);

        //right side
        TNode newRightNode = cloneNode(orgTree->right_link);
        copyTree->right_link = newRightNode;
        copyInOrder(orgTree->right_link, copyTree->right_link);
    }
}

Upvotes: 4

Related Questions