1.Write a program that draws a binary tree.
Answer:
If we take a closer look at the pattern, we can notice following.
1) Rightmost node is printed in first line and leftmost node is printed in last line.
2) Space count increases by a fixed amount at every level.
So we do a reverse inorder traversal (right – root – left) and print tree nodes. We increase
space by a fixed amount at every level.
// C++ Program to print binary tree in 2D
#include<bits/stdc++.h>
using namespace std;
#define COUNT 10
// A binary tree node
class Node
{
public:
int data;
Node* left, *right;
/* Constructor that allocates a new node with the
given data and NULL left and right pointers. */
Node(int data){
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
// Function to print binary tree in 2D
// It does reverse inorder traversal
void print2DUtil(Node *root, int space)
{
// Base case
if (root == NULL)
return;
// Increase distance between levels
space += COUNT;
// Process right child first
print2DUtil(root->right, space);
// Print current node after space
// count
cout<<endl;
for (int i = COUNT; i < space; i++)
cout<<" ";
cout<<root->data<<"\n";
// Process left child
print2DUtil(root->left, space);
}
// Wrapper over print2DUtil()
void print2D(Node *root)
{
// Pass initial space count as 0
print2DUtil(root, 0);
}
// Driver code
int main()
{
Node *root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
root->right->left = new Node(6);
root->right->right = new Node(7);
root->left->left->left = new Node(8);
root->left->left->right = new Node(9);
root->left->right->left = new Node(10);
root->left->right->right = new Node(11);
root->right->left->left = new Node(12);
root->right->left->right = new Node(13);
root->right->right->left = new Node(14);
root->right->right->right = new Node(15);
print2D(root);
return 0;
}
2.Write a program that draws a general tree
Answer:
// CPP program to do level order traversal
// of a generic tree
#include <bits/stdc++.h>
using namespace std;
// Represents a node of an n-ary tree
struct Node
int key;
vector<Node *>child;
};
// Utility function to create a new tree node
Node *newNode(int key)
Node *temp = new Node;
temp->key = key;
return temp;
// Prints the n-ary tree level wise
void LevelOrderTraversal(Node * root)
if (root==NULL)
return;
// Standard level order traversal code
// using queue
queue<Node *> q; // Create a queue
q.push(root); // Enqueue root
while (!q.empty())
int n = q.size();
// If this node has children
while (n > 0)
// Dequeue an item from queue and print it
Node * p = q.front();
q.pop();
cout << p->key << " ";
// Enqueue all children of the dequeued item
for (int i=0; i<p->child.size(); i++)
q.push(p->child[i]);
n--;
cout << endl; // Print new line between two levels
// Driver program
int main()
{
/* Let us create below tree
* 10
* //\\
* 2 34 56 100
* /\ |/|\
* 77 88 1 7 8 9
*/
Node *root = newNode(10);
(root->child).push_back(newNode(2));
(root->child).push_back(newNode(34));
(root->child).push_back(newNode(56));
(root->child).push_back(newNode(100));
(root->child[0]->child).push_back(newNode(77));
(root->child[0]->child).push_back(newNode(88));
(root->child[2]->child).push_back(newNode(1));
(root->child[3]->child).push_back(newNode(7));
(root->child[3]->child).push_back(newNode(8));
(root->child[3]->child).push_back(newNode(9));
cout << "Level order traversal Before Mirroring\n";
LevelOrderTraversal(root);
return 0;
}
3.Write a program that can input and display a person's family tree.
Answer:
import java.awt.*;
import java.awt.event.*;
import java.util.*;
/*
* @author Amber Hisaw <ambehis@mail.regent.edu>
* @version 1.0
* @since 5-9-2015
* @purpose: This class creates a binary tree that
* holds strings and will add them to a
* specified node.
*/
public class FamilyTree
{
private class Node
{
String value; // Value stored in node
Node left, right; // Left and right child
/**
Constructor for leaf nodes.
@param val The value to store in the node.
*/
Node(String val)
{
value = val;
left = null;
right = null;
}
/**
Constructor for non-leaf nodes.
@param val The value to initialize the node.
@param leftChild The link to the left child.
@param rightChild The link to the right child.
*/
Node(String val, Node leftChild, Node rightChild)
{
value = val;
left = leftChild;
right = rightChild;
}
}
/**
The BTreeDisplay class graphically displays trees
in a JPanel. The JPanel is recursively partitioned
into a top part dislaying the root, and two lower
parts displaying the left and right subtrees.
*/
private class BTreeDisplay extends JPanel
{
/**
Constructor.
@param tree The root of the binary
tree to display.
*/
BTreeDisplay(Node tree)
{
setBorder(BorderFactory.createEtchedBorder());
setLayout(new BorderLayout());
if (tree != null)
{
String value = String.valueOf(tree.value);
int pos = SwingConstants.CENTER;
JLabel rootLabel = new JLabel(value, pos);
add(rootLabel, BorderLayout.NORTH);
JPanel panel = new JPanel(new GridLayout(1, 2));
panel.add(new BTreeDisplay(tree.left));
panel.add(new BTreeDisplay(tree.right));
add(panel);
}
}
}
private Node root = null; // Root of binary tree
/**
The getView method creates and returns a
a graphical view of the binary tree.
@return A panel that displays a view of the tree.
*/
public JPanel getView()
{
return new BTreeDisplay(root);
}
/**
The public root method adds a value to the
tree by calling a private root method and
passing it the root of the tree.
@param x The value to make root.
@return true.
*/
public boolean root(String x)
{
if (root == null){
root = new Node(x);
return true;}
else
return false;
}
/**
The public addLeft method adds a value to the
tree by locating the desired parent and ensuring
all requirements are met.
@param p The desired parent. x The value to add to the tree.
@return true.
*/
public boolean addLeft(String p, String x)
{
Node parent = locate(p);
//Check if root is established.
if (root == null ){
return false;}
//Locate desired parent and checks if child exists.
else if (parent != null && parent.left == null){
//Adds node
parent.left = new Node(x);
return true;}
else
return false;
}
/**
The public addRight method adds a value to the
tree by locating the desired parent and ensuring
all requirements are met.
@param p The desired parent. x The value to add to the tree.
@return true.
*/
public boolean addRight(String p, String x)
{
Node parent = locate(p);
//Check if root is established.
if (root == null ){
return false;}
//Locate desired parent and checks if child exists.
else if (parent != null && parent.right == null){
//Adds node
parent.right = new Node(x);
return true;}
else
return false;
}
public Node locate(String p)
{
// Call the private recursive method
return locate(p, root);
}
/**
The method contains checks whether an
item is in a binary search tree.
@param x The item to check for.
@param famTree The binary tree to look in.
@return true if found, false otherwise.
*/
private Node locate(String p, Node famTree)
{
//new Node result, set to null.
Node result = null;
if (famTree == null)
return null;
//if passed node contains value, return it.
if (famTree.value.equals(p))
return famTree;
//if left child not null, recursively call locate with left child.
if (famTree.left != null)
result = locate(p,famTree.left);
//if parent still not found, recursively call right locate passing the right child.
if (result == null)
result = locate(p,famTree.right);
return result;
}
}
