Question

C++

How can I insert normal array as degenerate tree. Plz use sequential implementation. Thanks.

Answer 1

answer-

C++ program to insert normal array as degenerate tree.-

#include<bit/std++.h>

using namespace std;

// tree Node

struct Node

{ int key;

struct Node *left, *right; };

Node * newNode(int key)

{

Node *temp =new Node;

temp->key =key;

temp->left =temp->right=NULL;

return (temp);

}

void createNode(int parent[], int i, Node *created[], Node **root)

{

if (created[i] != NULL)  

return;

// create a new Node & set created[i]

created[i] = newNode(i);

if (parent[i] == -1)

{

*root = created[i];

return;

}     

if (created[parent[i]] == NULL)

createNode(parent, parent[i], created, root);

Node *p = created[parent[i]];

// find parent pointer

if (p->left == NULL)

    p->left = created[i];

  else

// second child

p->right = created[i];

}

  Node *createTree(int parent[], int n)

{

    Node *created[n];

for (int i=0; i<n; i++)

created[i] = NULL;

Node *root = NULL;

for (int i=0; i<n; i++)

createNode(parent, i, created, &root);

return root;

}

//For adding new line in a program

inline void newLine()

{

cout << "\n";

}  

void inorder(Node *root)

{

if (root != NULL)

{

inorder(root->left);

cout << root->key << " ";

inorder(root->right);

}

}  

// Driver method

int main()

{

   int parent[] = {-1, 0, 0, 1, 1, 3, 5};

int n = sizeof parent / sizeof parent[0];

Node *root = createTree(parent, n);

cout << "Inorder Traversal of constructed tree\n";

  inorder(root);

newLine();

}

Output:

Inorder Traversal of constructed tree

6 5 3 1 4 0 2