-
Exercise17_2
#include
#include
#include
#include
using namespace std;
#ifndef BINARYTREE_H
#define BINARYTREE_H
template < typename T >
class TreeNode
{
public:
T element; // Element contained in the node
TreeNode < T > * left; // Pointer to the left child
TreeNode < T > * right; // Pointer to the right child
TreeNode() // No-arg constructor
{
left = NULL;
next = NULL;
}
TreeNode(T element) // Constructor
{
this->element = element;
left = NULL;
right = NULL;
}
};
template < typename T >
class BinaryTree
{
public:
BinaryTree();
BinaryTree(T elements[], int arraySize);
bool insert(T element);
void inorder();
void preorder();
void postorder();
int getSize();
bool search(T element);
void breadthFirstTraversal();
int depth();
private:
TreeNode < T > * root;
int size;
void inorder(TreeNode < T > * root);
void postorder(TreeNode < T > * root);
void preorder(TreeNode < T > * root);
bool search(T element, TreeNode < T > * root);
int depth(TreeNode
};
template < typename T >
BinaryTree < T >::BinaryTree()
{
root = NULL;
size = 0;
}
template < typename T >
BinaryTree < T >::BinaryTree(T elements[], int arraySize)
{
root = NULL;
size = 0;
for (int i = 0; i < arraySize; i++)
{
insert(elements[i]);
}
}
/* Insert element into the binary tree * Return true if the element is inserted successfully
* Return false if the element is already in the list */
template < typename T >
bool BinaryTree < T >::insert(T element)
{
if (root == NULL)
root = new TreeNode < T > (element); // Create a new root
else
{
// Locate the parent node
TreeNode < T > * parent = NULL;
TreeNode < T > * current = root;
while (current != NULL)
if (element < current->element)
{
parent = current;
current = current->left;
}
else if (element > current->element)
{
parent = current;
current = current->right;
}
else
return false; // Duplicate node not inserted
// Create the new node and attach it to the parent node
if (element < parent->element)
parent->left = new TreeNode < T > (element);
else
parent->right = new TreeNode < T > (element);
}
size++;
return true; // Element inserted
}
/* Inorder traversal */
template < typename T >
void BinaryTree < T >::inorder()
{
inorder(root);
}
/* Inorder traversal from a subtree */
template < typename T >
void BinaryTree < T >::inorder(TreeNode < T > * root)
{
if (root == NULL) return;
inorder(root->left);
cout << root->element <<
inorder(root->right);
}
/* Postorder traversal */
template < typename T >
void BinaryTree < T >::postorder()
{
postorder(root);
}
/** Inorder traversal from a subtree */
template < typename T >
void BinaryTree < T >::postorder(TreeNode < T > * root)
{
if (root == NULL) return;
postorder(root->left);
postorder(root->right);
cout << root->element <<
}
/* Preorder traversal */
template < typename T >
void BinaryTree < T >::preorder()
{
preorder(root);
}
/* Preorder traversal from a subtree */
template < typename T >
void BinaryTree < T >::preorder(TreeNode < T > * root)
{
if (root == NULL) return;
cout << root->element <<
preorder(root->left);
preorder(root->right);
}
/* Get the number of nodes in the tree */
template < typename T >
int BinaryTree < T >::getSize()
{
return size;
}
template < typename T >
void BinaryTree < T >::breadthFirstTraversal()
{
Queue
if (root != NULL)
e(root);
while (e() > 0)
{
TreeNode
cout << node->element <<
if ( (node->left) != NULL)
e(node->left);
if ( (node->right) != NULL)
e(node->right);
}
}
#endif
int main()
{
BinaryTree < string > tree1;
(
(
(
(
(
(
(
cout <<
r();
cout <<
der();
cout <<
er();
cout <<
int numbers[] =
{
2, 4, 3, 1, 8, 5, 6, 7
};
BinaryTree < int > tree2(numbers, 8);
cout <<
r();
// Test breadth-first
cout <<
hFirstTraversal();
return 0;
}
Exercise17_4
#include
#include
#include
#include
using namespace std;
#ifndef BINARYTREE_H
#define BINARYTREE_H
template < typename T >
class TreeNode
{
public:
T element; // Element contained in the node
TreeNode < T > * left; // Pointer to the left child
TreeNode < T > * right; // Pointer to the right child
TreeNode() // No-arg constructor
{
left = NULL;
next = NULL;
}
TreeNode(T element) // Constructor
{
this->element = element;
left = NULL;
right = NULL;
}
};
template < typename T >
class BinaryTree
{
public:
BinaryTree();
BinaryTree(T elements[], int arraySize);
bool insert(T element);
void inorder();
void preorder();
void postorder();
int getSize();
bool search(T element);
void breadthFirstTraversal();
int depth();
private:
TreeNode < T > * root;
int size;
void inorder(TreeNode < T > * root);
void postorder(TreeNode < T > * root);
void preorder(TreeNode < T > * root);
bool search(T element, TreeNode < T > * root);
int depth(TreeNode
};
template < typename T >
BinaryTree < T >::BinaryTree()
{
root = NULL;
size = 0;
}
template < typename T >
BinaryTree < T >::BinaryTree(T elements[], int arraySize)
{
root = NULL;
-
-
-
-
-
-
-
-
本文更新与2021-01-25 09:24，由作者提供，不代表本网站立场，转载请注明出处：https://www.bjmy2z.cn/gaokao/565092.html
-
上一篇：广工数据结构实验报告平衡二叉树
下一篇：服装尺寸英语术语