Implement in C++. PROBLEM 4 (135 points) 4.1 Write a program to store a tree as

Question

Implement in C++.

PROBLEM 4 (135 points) 4.1 Write a program to store a tree as an array. In your test program, be sure to print the array values, and to print the values in tree­­­ “format”. 4.2 Write a function to add an element to an existing tree. 4.3 Write a function to delete an element from an existing tree. 4.4 Write a function to perform an “in-order” traversal on an existing tree. 4.5 Write a function to perform an “pre-order” traversal on an existing tree. 4.6 Write a function to perform an “post-order” traversal on an existing tree. 4.7 Write a function to perform an “level-order” traversal on an existing tree. 4.8 Write a function to find the children of a specified node. 4.9 Write a function to find the parent of a specified node.

Explanation / Answer

#include <iostream>
#include<cstdio>
using namespace std;
struct Node{
int data;
struct Node *left;
struct Node *right;
};

Node* FindMin(Node* root){
while(root->left != NULL) root = root->left;
return root;
}

struct Node* Delete(struct Node *root, int data){
if(root == NULL) return root;
else if(data < root->data) root->left = Delete(root->left,data);
else if(data > root->data) root->right = Delete(root->right, data);
else {
// Case 1: No Child
if(root->left == NULL && root->right == NULL){
delete root;
root = NULL;
// Case 2: one child
} else if(root->left == NULL){
struct Node *temp = root;
root = root->right;
delete temp;
} else if(root->right == NULL){
struct Node *temp = root;
root = root->left;
delete temp;
} else{
struct Node *temp = FindMin(root->right);
root->data = temp->data;
root->right = Delete(root->right, temp->data);
}
}
return root;
}

void Inorder(Node *root){
if(root == NULL) return;
Inorder(root->left);
printf("%d ",root->data);
Inorder(root->right);
}

Node* Insert(Node *root, char data){
if(root == NULL){
root = new Node();
root->data = data;
root->left = root->right = NULL;
} else if(data <= root->data){
root->left = Insert(root->left, data);
} else {
root->right = Insert(root->right, data);
}
return root;
}

int main ()
{
Node* root = NULL;
root = Insert(root, 5);
root = Insert(root, 10);
root = Insert(root, 3);
root = Insert(root, 4);
root = Insert(root, 1);
root = Insert(root, 11);
  
root = Delete(root, 5);
  
cout<<"Inorder: ";
Inorder(root);
cout<<" ";
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.