/**************** A ***************/
char main()
{
char choice;
apstring item;
float newprice;
struct treetype;
typedef treeptr * treetype;
struct treetype
{
apstring name;
float price;
treeptr left, right; // or can be written as:
// apvector <treeptr> child;
};
treeptr root = NULL, found;

// procedure begins
do
{
// selection and input of selection
cout << "(D)elete \n(A)dd \n(P)ricing \nP(R)int\n (Q)uit\n";
cin >> choice;
choice = toupper(choice);
// selects choice
if (choice == 'D')
{
// deletes assuming that the tree exists
cout << "Delete what?\n";
cin >> item;
delete (item, root);
}
else if (choice == 'A')
{
// adds new item and price
cout << "Add what?\n";
cin >> item;
cout << "What is the price?\n";
cin >> newprice;
insert (item, newprice, root);
}
else if (choice == 'P')
{
// prints out the price of the desired item
cout << "Price of what?\n";
cin >> item;
found = find (item, root);
cout << found -> price;
}
// goes through with in order traversal function prints
else if (choice == 'R')
inorder(root);
else if (choice == 'Q')
else
cout << "That was not a choice! Try again!\n";
}
while(toupper(choice) != 'Q');
return choice;
}

/*********** B ******************/
struct treetype;
typedef treeptr * treetype;
struct treetype
{
char function;
treeptr left, right;
};

int eval(treeptr root)
{
char sign;
treeptr root=newroot, found;
if (root->left == NULL)
return root -> data;
else if (root -> right == NULL)
return root -> data;
else
{
switch (root)
'+':
return (eval(root->left) + eval (root -> right))
'-':
return (eval(root -> right) - eval (root -> left))
'*':
return (eval(root -> right) * eval (root -> left))
'/':
return (eval(root -> right) / eval (root -> left))
default:
}
}
/************** C ******************/
struct treetype
{
int data;
treeptr left, right;
};
// function that finds the the size of the tree
int treesize(treeptr root)
{
// first node has a length of one
int size = 1;
// recursive if statements that will
// act as a counter if the root has children
if(root->left != NULL)
size += treesize(root->left);
if(root->right != NULL)
size += treesize(root->right);
return size;
}

// puts the tree into a queue by going through
// the tree inorder traversal
void inorder(apqueue <treeptr> & queue, treeptr root)
{
if(root->left != NULL)
inorder(queue, root->left);
// if the node is a leaf, it will be added to the
// queue and this is done inorder traversal
queue.enqueue(root);
if(root->right != NULL)
inorder(queue, root->right);
}

// turns the array or queue of treeptrs into
// a tree by passing into the function the
// array of treeptrs, the index of the treeptr,
// and the depth of that particular root
treeptr convert(treeptr array[], int pos, int len)
{
int mid = pos + int(len + 0.5);
// initializes a root
treeptr root;
// if the root is a leaf node, its children are null
if(len == 1)
{
root = array[pos];
root->left = root->right = NULL;
return root;
}
// if the root is not a leaf mode, builds the root
// from the middle
root = array[mid];
// begins to create the left branch recursively
// by subdividing all of the left nodes
int llen = mid - pos;
root->left = convert(array, pos, llen);
// if root has one child to the left
if (len == 2)
{
root-> right = NULL;
return root;
}
// builds the right branch recursively
int rlen = pos + len - mid - 1;
root->right = convert(array, pos, rlen);
// if root has one child to the right
if (len == 2)
{
root-> left = NULL;
return root;
}
return root;
}
// balances the tree
void balance (treeptr root)
{
if(root == null)
return;
// size of tree
int size = treesize(root);
// takes the tree and places it into the queue vector
apqueue <treeptr> queue;
inorder(queue, root);
// creates a new, empty array of the size necessary
treeptr array = new treeptr[size];
// takes the queue vector and dequeues
// the treeptrs into a into a new array
int i=0;
while(!queue.isEmpty)
{
queue.dequeue(array[i]);
i++;
}
// puts the modified array back into a tree form
root = convert(array, 0, size);
}
/************** D ******************/

int main()
{
struct treetype;
typedef treetype * treeptr;
struct treetype
{
int data;
treeptr left, right;
};
int dep;
treeptr newroot;

dep = depth (newroot);
cout << dep;
return dep;
}
// recursively finds the depth of the
// root by traveling to the maximum
// depth on either side of the root
// and compares the left and right
// maximum values to chose which is the depth
int depth(treeptr root)
{
char c;
int l=0, r=0;
if (root -> left != NULL)
l = 1 + depth(root -> left);
if (root -> right != NULL)
r = 1 + depth(root -> right);
if (l > r)
return l;
else
return r;
}

/************* E ******************/
int main()
{
struct treetype;
typedef treetype * treeptr;
struct treetype
{
int data;
treeptr left, right;
};
treeptr root;
int num = 0;

nodecounter(root);
}
int nodecounter(treeptr root)
{
if (root != NULL)
return nodecounter (root->left) + nodecounter (root -> right);
else
return 0;
}
bool leaf(treeptr root)
return (root->left ==NULL && root-> right == NULL)
int leafcounter(treeptr root)
{
if(root != NULL)
{
if(leaf(root))
return 1;
else
return 0;
}
return 0;
}
/************* F ******************/
// A binary tree has more null nodes because the leafs
// are always pointing to two null nodes and children
// are only pointed to by one node. There are more
// than half null nodes in a strictly binary tree
// because the number of nodes increases exponentially
// : 1, 2, 4, 8, 16, 32, etx. The null nodes will
// always be one less than the total number of
// nodes. To have the null node point to the root or the
// parent node in a sort of circular portion of the tree.
// This allows you to traverse the tree backwards.

/************** G ****************/
// The number of nodes in a strictly binary tree of
// depth N is approximately 2N + 1.

/************** H ****************/
// preorder: abdglmehincfjkop
// inorder: lgmdbheniacjfokp
// postorder: lmgdhniebjopkfca
// The node between i and a would be placed on the right leaf of node i.
// The node between m and d would be placed on the right leaf of node m.
// The node between f and o would be placed on the left leaf of node o.
//
// deleting C
/*
A
/ \
B F
/ \ / \
D E J K
/ / \ / \
G H I O P
/ \ /
L M N
*/
// deleting H
/*
A
/ \
B C
/ \ / \
D E F
/ / \ / \
G I J K
/ \ / / \
L M N O P
*/
// deleting b
/*
A
/ \
D C
/ \ / \
G E F
/ \ / \ / \
L M H I J K
/ / \
N O P

*/
/************** I ****************/
// exp tree a: use the last operator as the root, go in descending order of
// operation
/*
-
/ \
+ *
/ \ / \
* c a +
/ \ / \
a b c b
*/
// exp tree b
/*
^
/ \
+ /
/ \ / \
/ * 1 2
/ \ /\
- 3 4 z
/ \
x y

*/