406 lines
24 KiB
HTML
406 lines
24 KiB
HTML
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
|
|
<html>
|
|
<head>
|
|
<title>TreeASDV.java</title>
|
|
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
|
|
<style type="text/css">
|
|
<!--
|
|
body {color: #a9b7c6; background-color: #2b2b2b; font-family: monospace; font-weight: bold}
|
|
pre {color: #a9b7c6; background-color: #2b2b2b; font-family: monospace; font-weight: bold}
|
|
table {color: #888888; background-color: #313335; font-family: monospace; font-weight: bold}
|
|
.string {color: #6a8759}
|
|
.number {color: #6897bb}
|
|
.ST2 {color: #9876aa}
|
|
.ST3 {color: #ffc66d}
|
|
.ST1 {color: #8a653b}
|
|
.comment {color: #808080}
|
|
.whitespace {color: #505050}
|
|
.ST4 {color: #9876aa; font-family: monospace; font-weight: bold; font-style: italic}
|
|
.ST6 {color: #ffc66d; font-family: monospace; font-weight: bold; font-style: italic}
|
|
.ST0 {color: #287bde}
|
|
.literal {color: #cc7832}
|
|
.ST5 {font-family: monospace; font-weight: bold; font-style: italic}
|
|
-->
|
|
</style>
|
|
</head>
|
|
<body>
|
|
<table width="100%"><tr><td align="center">/home/caleb/ASDV-Java/Semester 4/Assignments/ProjectTrees_CalebFontenot/src/main/java/edu/slcc/asdv/caleb/projecttrees_calebfontenot/TreeASDV.java</td></tr></table>
|
|
<pre>
|
|
<span class="comment">/*</span>
|
|
<span class="comment"> * Click </span><span class="ST0">nbfs://nbhost/SystemFileSystem/Templates/Licenses/license-default.txt</span><span class="comment"> to change this license</span>
|
|
<span class="comment"> * Click </span><span class="ST0">nbfs://nbhost/SystemFileSystem/Templates/Classes/Class.java</span><span class="comment"> to edit this template</span>
|
|
<span class="comment"> */</span>
|
|
<span class="literal">package</span> edu.slcc.asdv.caleb.projecttrees_calebfontenot;
|
|
|
|
<span class="literal">import</span> java.util.ArrayList;
|
|
<span class="literal">import</span> java.util.Iterator;
|
|
<span class="literal">import</span> java.util.LinkedList;
|
|
<span class="comment">import</span> <span class="comment">java</span><span class="comment">.</span><span class="comment">util</span><span class="comment">.</span><span class="comment">ListIterator</span><span class="comment">;</span>
|
|
<span class="literal">import</span> java.util.Queue;
|
|
<span class="literal">import</span> java.util.Stack;
|
|
|
|
<span class="comment">/**</span>
|
|
<span class="comment"> *</span>
|
|
<span class="comment"> * </span><span class="comment">@author</span> <span class="comment">caleb</span>
|
|
<span class="comment"> * </span><span class="comment">@param</span> <span class="ST1"><T></span>
|
|
<span class="comment">*/</span>
|
|
<span class="literal">public</span> <span class="literal">class</span> TreeASDV<T <span class="literal">extends</span> Comparable> <span class="literal">implements</span> Cloneable {
|
|
|
|
<span class="literal">private</span> Node<T> <span class="ST2">root</span>;
|
|
|
|
<span class="literal">class</span> Node<T> {
|
|
|
|
T <span class="ST2">data</span>;
|
|
Node<T> <span class="ST2">leftChild</span>;
|
|
Node<T> <span class="ST2">rightChild</span>;
|
|
}
|
|
|
|
@Override
|
|
<span class="literal">public</span> Object <span class="ST3">clone</span>()
|
|
{
|
|
System.<span class="ST4">out</span>.println(<span class="string">"</span><span class="string">Cloning...</span><span class="string">"</span>);
|
|
TreeASDV<T> clone = <span class="literal">new</span> TreeASDV<T>();
|
|
ArrayList<T> oldData = <span class="literal">this</span>.getBreadthFirstArray();
|
|
<span class="literal">for</span> (<span class="literal">int</span> i = <span class="number">0</span>; i < oldData.size(); ++i) {
|
|
<span class="comment">//System.out.println(oldData.get(i));</span>
|
|
clone.insert(oldData.get(i));
|
|
}
|
|
<span class="literal">return</span> clone;
|
|
}
|
|
|
|
<span class="literal">public</span> <span class="literal">boolean</span> <span class="ST3">insert</span>(T t)
|
|
{
|
|
Node<T> newNode = <span class="literal">new</span> Node<>();
|
|
newNode.<span class="ST2">data</span> = t;
|
|
|
|
<span class="literal">if</span> (<span class="ST2">root</span> == <span class="literal">null</span>) {
|
|
<span class="ST2">root</span> = newNode;
|
|
<span class="literal">return</span> <span class="literal">true</span>;
|
|
}
|
|
|
|
Node<T> current = <span class="ST2">root</span>;
|
|
Node<T> parent = <span class="literal">null</span>;
|
|
|
|
<span class="literal">while</span> (current != <span class="literal">null</span>) {
|
|
parent = current;
|
|
<span class="literal">if</span> (t.compareTo(current.<span class="ST2">data</span>) >= <span class="number">0</span>) {
|
|
current = current.<span class="ST2">rightChild</span>;
|
|
} <span class="literal">else</span> {
|
|
current = current.<span class="ST2">leftChild</span>;
|
|
}
|
|
}
|
|
|
|
<span class="comment">// At this point, 'parent' is the node where the new node should be inserted as a child</span>
|
|
<span class="literal">if</span> (t.compareTo(parent.<span class="ST2">data</span>) >= <span class="number">0</span>) {
|
|
parent.<span class="ST2">rightChild</span> = newNode;
|
|
} <span class="literal">else</span> {
|
|
parent.<span class="ST2">leftChild</span> = newNode;
|
|
}
|
|
|
|
<span class="literal">return</span> <span class="literal">true</span>;
|
|
}
|
|
|
|
<span class="literal">private</span> <span class="literal">void</span> <span class="comment">inOrder</span>(Node<T> p)
|
|
{
|
|
<span class="literal">if</span> (p == <span class="literal">null</span>) {
|
|
<span class="literal">return</span>;
|
|
}
|
|
|
|
inOrder(p.<span class="ST2">leftChild</span>);
|
|
System.<span class="ST4">out</span>.print(p.<span class="ST2">data</span> + <span class="string">"</span> <span class="string">"</span>);
|
|
inOrder(p.<span class="ST2">rightChild</span>);
|
|
}
|
|
|
|
<span class="literal">public</span> Node<T> <span class="ST3">findNode</span>(T t)
|
|
{
|
|
Node<T> currentNode = <span class="ST2">root</span>;
|
|
<span class="literal">while</span> (currentNode != <span class="literal">null</span>) {
|
|
<span class="literal">if</span> (t.compareTo(currentNode.<span class="ST2">data</span>) == <span class="number">0</span>) {
|
|
<span class="literal">return</span> currentNode;
|
|
} <span class="literal">else</span> <span class="literal">if</span> (t.compareTo(currentNode.<span class="ST2">data</span>) > <span class="number">0</span>) {
|
|
currentNode = currentNode.<span class="ST2">rightChild</span>;
|
|
} <span class="literal">else</span> {
|
|
currentNode = currentNode.<span class="ST2">leftChild</span>;
|
|
}
|
|
}
|
|
<span class="literal">return</span> <span class="literal">null</span>;
|
|
}
|
|
|
|
<span class="literal">public</span> <span class="literal">boolean</span> <span class="ST3">remove</span>(T t) {
|
|
<span class="comment">// Initialize parent and current nodes for traversal</span>
|
|
Node<T> parent = <span class="literal">null</span>;
|
|
Node<T> current = <span class="ST2">root</span>;
|
|
|
|
<span class="comment">// Search for the node to be removed</span>
|
|
<span class="literal">while</span> (current != <span class="literal">null</span> && !current.<span class="ST2">data</span>.equals(t)) {
|
|
parent = current;
|
|
<span class="literal">if</span> (t.compareTo(current.<span class="ST2">data</span>) > <span class="number">0</span>) {
|
|
current = current.<span class="ST2">rightChild</span>;
|
|
} <span class="literal">else</span> {
|
|
current = current.<span class="ST2">leftChild</span>;
|
|
}
|
|
}
|
|
|
|
<span class="comment">// If node not found, return false</span>
|
|
<span class="literal">if</span> (current == <span class="literal">null</span>) {
|
|
<span class="literal">return</span> <span class="literal">false</span>;
|
|
}
|
|
|
|
<span class="comment">// Case 1: Node with no children</span>
|
|
<span class="literal">if</span> (current.<span class="ST2">leftChild</span> == <span class="literal">null</span> && current.<span class="ST2">rightChild</span> == <span class="literal">null</span>) {
|
|
<span class="literal">if</span> (current == <span class="ST2">root</span>) {
|
|
<span class="ST2">root</span> = <span class="literal">null</span>; <span class="comment">// Removing root node</span>
|
|
} <span class="literal">else</span> <span class="literal">if</span> (parent.<span class="ST2">leftChild</span> == current) {
|
|
parent.<span class="ST2">leftChild</span> = <span class="literal">null</span>; <span class="comment">// Removing a left child</span>
|
|
} <span class="literal">else</span> {
|
|
parent.<span class="ST2">rightChild</span> = <span class="literal">null</span>; <span class="comment">// Removing a right child</span>
|
|
}
|
|
} <span class="comment">// Case 2: Node with one child</span>
|
|
<span class="literal">else</span> <span class="literal">if</span> (current.<span class="ST2">leftChild</span> == <span class="literal">null</span> || current.<span class="ST2">rightChild</span> == <span class="literal">null</span>) {
|
|
Node<T> child = (current.<span class="ST2">leftChild</span> != <span class="literal">null</span>) ? current.<span class="ST2">leftChild</span> : current.<span class="ST2">rightChild</span>;
|
|
<span class="literal">if</span> (current == <span class="ST2">root</span>) {
|
|
<span class="ST2">root</span> = child; <span class="comment">// Replace root with its child</span>
|
|
} <span class="literal">else</span> <span class="literal">if</span> (parent.<span class="ST2">leftChild</span> == current) {
|
|
parent.<span class="ST2">leftChild</span> = child; <span class="comment">// Replace parent's left child with the node's child</span>
|
|
} <span class="literal">else</span> {
|
|
parent.<span class="ST2">rightChild</span> = child; <span class="comment">// Replace parent's right child with the node's child</span>
|
|
}
|
|
} <span class="comment">// Case 3: Node with two children</span>
|
|
<span class="literal">else</span> {
|
|
Node<T> successorParent = current;
|
|
Node<T> successor = current.<span class="ST2">rightChild</span>;
|
|
<span class="literal">while</span> (successor.<span class="ST2">leftChild</span> != <span class="literal">null</span>) {
|
|
successorParent = successor;
|
|
successor = successor.<span class="ST2">leftChild</span>;
|
|
}
|
|
current.<span class="ST2">data</span> = successor.<span class="ST2">data</span>; <span class="comment">// Replace data with successor's data</span>
|
|
<span class="literal">if</span> (successorParent == current) {
|
|
successorParent.<span class="ST2">rightChild</span> = successor.<span class="ST2">rightChild</span>;
|
|
} <span class="literal">else</span> {
|
|
successorParent.<span class="ST2">leftChild</span> = successor.<span class="ST2">rightChild</span>;
|
|
}
|
|
}
|
|
|
|
<span class="literal">return</span> <span class="literal">true</span>;
|
|
}
|
|
|
|
|
|
<span class="comment">// Helper method to find in-order successor of a node</span>
|
|
<span class="literal">private</span> Node<T> <span class="comment">getSuccessor</span>(Node<T> node)
|
|
{
|
|
Node<T> current = node.<span class="ST2">rightChild</span>;
|
|
Node<T> successorParent = node;
|
|
Node<T> successor = node;
|
|
|
|
<span class="comment">// Find the leftmost node in the right subtree (in-order successor)</span>
|
|
<span class="literal">while</span> (current != <span class="literal">null</span>) {
|
|
successorParent = successor;
|
|
successor = current;
|
|
current = current.<span class="ST2">leftChild</span>;
|
|
}
|
|
|
|
<span class="comment">// If the successor is not the right child of the node to be removed,</span>
|
|
<span class="comment">// adjust the successor's parent's leftChild reference</span>
|
|
<span class="literal">if</span> (successor != node.<span class="ST2">rightChild</span>) {
|
|
successorParent.<span class="ST2">leftChild</span> = successor.<span class="ST2">rightChild</span>;
|
|
successor.<span class="ST2">rightChild</span> = node.<span class="ST2">rightChild</span>;
|
|
}
|
|
|
|
<span class="literal">return</span> successor;
|
|
}
|
|
|
|
<span class="comment">// Inorder ListIterator</span>
|
|
<span class="literal">public</span> Iterator<T> <span class="ST3">listIterator</span>()
|
|
{
|
|
<span class="literal">return</span> <span class="literal">new</span> InorderIterator();
|
|
}
|
|
|
|
<span class="literal">private</span> <span class="literal">class</span> InorderIterator <span class="literal">implements</span> Iterator<T> {
|
|
|
|
<span class="literal">private</span> Stack<Node<T>> <span class="ST2">stack</span>;
|
|
|
|
<span class="literal">public</span> InorderIterator()
|
|
{
|
|
<span class="ST2">stack</span> = <span class="literal">new</span> Stack<>();
|
|
pushLeft(<span class="ST2">r</span><span class="ST2">oot</span>);
|
|
}
|
|
|
|
<span class="literal">private</span> <span class="literal">void</span> <span class="ST3">pushLeft</span>(Node<T> node)
|
|
{
|
|
<span class="literal">while</span> (node != <span class="literal">null</span>) {
|
|
<span class="ST2">stack</span>.push(node);
|
|
node = node.<span class="ST2">leftChild</span>;
|
|
}
|
|
}
|
|
|
|
@Override
|
|
<span class="literal">public</span> <span class="literal">boolean</span> <span class="ST3">hasNext</span>()
|
|
{
|
|
<span class="literal">return</span> !<span class="ST2">stack</span>.isEmpty();
|
|
}
|
|
|
|
@Override
|
|
<span class="literal">public</span> T <span class="ST3">next</span>()
|
|
{
|
|
<span class="literal">if</span> (!hasNext()) {
|
|
<span class="literal">throw</span> <span class="literal">new</span> java.util.NoSuchElementException();
|
|
}
|
|
Node<T> current = <span class="ST2">stack</span>.pop();
|
|
pushLeft(current.<span class="ST2">rightChild</span>);
|
|
<span class="literal">return</span> current.<span class="ST2">data</span>;
|
|
}
|
|
|
|
@Override
|
|
<span class="literal">public</span> <span class="literal">void</span> <span class="ST3">remove</span>()
|
|
{
|
|
<span class="literal">throw</span> <span class="literal">new</span> UnsupportedOperationException();
|
|
}
|
|
}
|
|
|
|
<span class="literal">public</span> ArrayList<T> <span class="ST3">getBreadthFirstArray</span>()
|
|
{
|
|
ArrayList<T> returnArray = <span class="literal">new</span> ArrayList<T>();
|
|
<span class="literal">if</span> (<span class="ST2">root</span> == <span class="literal">null</span>) {
|
|
<span class="literal">return</span> returnArray;
|
|
}
|
|
Queue<Node<T>> queue = <span class="literal">new</span> LinkedList<>();
|
|
|
|
queue.offer(<span class="ST2">r</span><span class="ST2">oot</span>);
|
|
|
|
<span class="literal">while</span> (!queue.isEmpty()) {
|
|
Node<T> current = queue.poll();
|
|
returnArray.add(current.<span class="ST2">data</span>);
|
|
|
|
<span class="literal">if</span> (current.<span class="ST2">leftChild</span> != <span class="literal">null</span>) {
|
|
queue.offer(current.<span class="ST2">leftChild</span>);
|
|
}
|
|
<span class="literal">if</span> (current.<span class="ST2">rightChild</span> != <span class="literal">null</span>) {
|
|
queue.offer(current.<span class="ST2">rightChild</span>);
|
|
}
|
|
}
|
|
<span class="literal">return</span> returnArray;
|
|
}
|
|
|
|
<span class="literal">public</span> <span class="literal">void</span> <span class="ST3">breadthFirstTraversal</span>()
|
|
{
|
|
<span class="literal">if</span> (<span class="ST2">root</span> == <span class="literal">null</span>) {
|
|
<span class="literal">return</span>;
|
|
}
|
|
|
|
Queue<Node<T>> queue = <span class="literal">new</span> LinkedList<>();
|
|
queue.offer(<span class="ST2">r</span><span class="ST2">oot</span>);
|
|
|
|
<span class="literal">while</span> (!queue.isEmpty()) {
|
|
Node<T> current = queue.poll();
|
|
System.<span class="ST4">out</span>.print(current.<span class="ST2">data</span> + <span class="string">"</span> <span class="string">"</span>);
|
|
|
|
<span class="literal">if</span> (current.<span class="ST2">leftChild</span> != <span class="literal">null</span>) {
|
|
queue.offer(current.<span class="ST2">leftChild</span>);
|
|
}
|
|
<span class="literal">if</span> (current.<span class="ST2">rightChild</span> != <span class="literal">null</span>) {
|
|
queue.offer(current.<span class="ST2">rightChild</span>);
|
|
}
|
|
}
|
|
}
|
|
|
|
@Override
|
|
<span class="literal">public</span> <span class="literal">boolean</span> <span class="ST3">equals</span>(Object obj) {
|
|
<span class="literal">return</span> <span class="literal">this</span>.getBreadthFirstArray().equals(((TreeASDV) obj).getBreadthFirstArray());
|
|
}
|
|
|
|
<span class="literal">public</span> <span class="literal">int</span> <span class="ST3">height</span>()
|
|
{
|
|
<span class="literal">return</span> calculateHeight(<span class="ST2">r</span><span class="ST2">oot</span>);
|
|
}
|
|
|
|
<span class="literal">private</span> <span class="literal">int</span> <span class="ST3">calculateHeight</span>(Node<T> node)
|
|
{
|
|
<span class="literal">if</span> (node == <span class="literal">null</span>) {
|
|
<span class="literal">return</span> <span class="number">0</span>;
|
|
}
|
|
|
|
<span class="literal">int</span> leftHeight = calculateHeight(node.<span class="ST2">leftChild</span>);
|
|
<span class="literal">int</span> rightHeight = calculateHeight(node.<span class="ST2">rightChild</span>);
|
|
|
|
<span class="literal">return</span> <span class="number">1</span> + Math.<span class="ST5">max</span>(leftHeight, rightHeight);
|
|
}
|
|
|
|
<span class="literal">public</span> <span class="literal">boolean</span> <span class="ST3">isFullBST</span>()
|
|
{
|
|
<span class="literal">int</span> height = height();
|
|
<span class="literal">int</span> nodeCount = countNodes(<span class="ST2">r</span><span class="ST2">oot</span>);
|
|
<span class="literal">return</span> nodeCount == (<span class="number">1</span> << height) - <span class="number">1</span>; <span class="comment">// Formula for full binary tree</span>
|
|
}
|
|
|
|
<span class="literal">private</span> <span class="literal">int</span> <span class="ST3">countNodes</span>(Node<T> node)
|
|
{
|
|
<span class="literal">if</span> (node == <span class="literal">null</span>) {
|
|
<span class="literal">return</span> <span class="number">0</span>;
|
|
}
|
|
<span class="literal">return</span> <span class="number">1</span> + countNodes(node.<span class="ST2">leftChild</span>) + countNodes(node.<span class="ST2">rightChild</span>);
|
|
}
|
|
|
|
<span class="literal">public</span> <span class="literal">void</span> <span class="ST3">inOrder</span>()
|
|
{
|
|
<span class="literal">if</span> (<span class="ST2">root</span> == <span class="literal">null</span>) {
|
|
<span class="literal">return</span>;
|
|
}
|
|
|
|
Stack<Node<T>> stack = <span class="literal">new</span> Stack<>();
|
|
Node<T> current = <span class="ST2">root</span>;
|
|
|
|
<span class="literal">while</span> (current != <span class="literal">null</span> || !stack.isEmpty()) {
|
|
<span class="literal">while</span> (current != <span class="literal">null</span>) {
|
|
stack.push(current);
|
|
current = current.<span class="ST2">leftChild</span>;
|
|
}
|
|
current = stack.pop();
|
|
System.<span class="ST4">out</span>.print(current.<span class="ST2">data</span> + <span class="string">"</span> <span class="string">"</span>);
|
|
current = current.<span class="ST2">rightChild</span>;
|
|
}
|
|
}
|
|
|
|
<span class="literal">public</span> <span class="literal">static</span> <span class="literal">void</span> <span class="ST6">main</span>(String[] args) <span class="literal">throws</span> CloneNotSupportedException
|
|
{
|
|
TreeASDV<Integer> tree = <span class="literal">new</span> TreeASDV<>();
|
|
<span class="comment">// Insert some elements into the tree</span>
|
|
tree.insert(<span class="number">5</span>);
|
|
tree.insert(<span class="number">3</span>);
|
|
tree.insert(<span class="number">7</span>);
|
|
tree.insert(<span class="number">2</span>);
|
|
tree.insert(<span class="number">4</span>);
|
|
tree.insert(<span class="number">6</span>);
|
|
tree.insert(<span class="number">8</span>);
|
|
|
|
<span class="comment">// Test breadth-first traversal</span>
|
|
System.<span class="ST4">out</span>.println(<span class="string">"</span><span class="string">Breadth-First Traversal:</span><span class="string">"</span>);
|
|
tree.breadthFirstTraversal();
|
|
System.<span class="ST4">out</span>.println();
|
|
|
|
<span class="comment">// Test height calculation</span>
|
|
System.<span class="ST4">out</span>.println(<span class="string">"</span><span class="string">Height of the tree: </span><span class="string">"</span> + tree.height());
|
|
|
|
<span class="comment">// Test if the tree is a full binary tree</span>
|
|
System.<span class="ST4">out</span>.println(<span class="string">"</span><span class="string">Is the tree a full binary tree? </span><span class="string">"</span> + tree.isFullBST());
|
|
|
|
<span class="comment">// Test inorder traversal without recursion</span>
|
|
System.<span class="ST4">out</span>.println(<span class="string">"</span><span class="string">Inorder Traversal without Recursion:</span><span class="string">"</span>);
|
|
tree.inOrder();
|
|
System.<span class="ST4">out</span>.println();
|
|
System.<span class="ST4">out</span>.println(<span class="string">"</span><span class="string">array list from breadth traversal</span><span class="string">"</span>);
|
|
System.<span class="ST4">out</span>.println(tree.getBreadthFirstArray());
|
|
System.<span class="ST4">out</span>.println(<span class="string">"</span><span class="string">Cloned Tree:</span><span class="string">"</span>);
|
|
TreeASDV<Integer> clonedTree = (TreeASDV<Integer>) tree.clone();
|
|
clonedTree.breadthFirstTraversal();
|
|
System.<span class="ST4">out</span>.println();
|
|
System.<span class="ST4">out</span>.println(<span class="string">"</span><span class="string">Does the original tree and the clone tree equal? </span><span class="string">"</span> + (tree.equals(clonedTree) ? <span class="string">"</span><span class="string">yes</span><span class="string">"</span> : <span class="string">"</span><span class="string">no</span><span class="string">"</span>) );
|
|
tree.insert(<span class="number">3</span><span class="number">000000</span>);
|
|
System.<span class="ST4">out</span>.println(<span class="string">"</span><span class="string">Does the original tree and the clone tree equal? </span><span class="string">"</span> + (tree.equals(clonedTree) ? <span class="string">"</span><span class="string">yes</span><span class="string">"</span> : <span class="string">"</span><span class="string">no</span><span class="string">"</span>) );
|
|
tree.remove(<span class="number">5</span>);
|
|
tree.breadthFirstTraversal();
|
|
}
|
|
}
|
|
|
|
</pre></body>
|
|
</html>
|