CS 2114 Chapter 24: CS-2114 - Notes - Reading 12 - Tree Implementations
29 Apr 2018
School
Department
Course
Professor
Daniel T. Eisert CS-2114
1
24 – Tree Implementations
Reading XII
CS-2114: Software Design & Data Structures
Tree
Implementations
The more common implementation of a tree uses a linked structure where nodes
represent each element in the tree. Each node can reference its children which are
other nodes in the tree.
- Arrays or vectors could also be used to implement a tree, but these options
are only advantageous when the tree is complete—the parent and child is
not stored explicitly, so the ADT is simpler than if the tree is not complete.
Nodes in a Binary
Tree
Overview:
- A node object that represents a node in a tree references both data and the
node’s children.
- Either reference to a child could be null; if both are null, the node is a leaf
node.
- The class of tree nodes will not be internal to the class of binary trees;
rather, the class of tree nodes will be defined outside of the binary tree
class. The class of nodes will NOT be public—use a package instead
(contains the classes of various trees and their interfaces).
- It is advantageous to use packages to allow the node to remain an
implementation detail that is not available to any of the tree’s clients.
• EXAMPLE: The class BinaryNode
package TreePackage;
class BinaryNode<T> {
private T data;
private BinaryNode<T> leftChild;
private BinaryNode<T> rightChild;
public BinaryNode() {
this(null);
}
public BinaryNode(T dataPortion) {
this(dataPortion, null, null);
}
public BinaryNode(T dataPortion, BinaryNode<T>
newLeftChild,BinaryNode<T> newRightChild) {
data = dataPortion;
leftChild = newLeftChild;
rightChild = newRightChild;
}
public T getData() {
return data;
}
public void setData(T newData) {
data = newData;
}
public BinaryNode<T> getLeftChild() {
return leftChild;
}
find more resources at oneclass.com
find more resources at oneclass.com
Daniel T. Eisert CS-2114
2
Nodes in a Binary
Tree
public void setLeftChild(BinaryNode<T>newLeftChild)
{
leftChild = newLeftChild;
}
public boolean hasLeftChild() {
return leftChild != null;
}
public BinaryNode<T> getRightChild() {
return rightChild;
}
public void setRightChild(BinaryNode<T>
newRightChild) {
rightChild = newRightChild;
}
public boolean hasRightChild() {
return rightChild != null;
}
public boolean isLeaf() {
return (leftChild == null)
&& (rightChild == null);
}
public int getNumberOfNodes() {
int leftNumber = 0;
int rightNumber = 0;
if (leftChild != null)
leftNumber = leftChild.getNumberOfNodes();
if (rightChild != null)
rightNumber = rightChild.getNumberOfNodes()
return 1 + leftNumber + rightNumber;
}
public int getHeight() {
return getHeight(this); // call private method
}
private int getHeight(BinaryNode<T> node) {
int height = 0;
if (node != null)
height = 1 +
Math.max(getHeight(node.getLeftChild()),
getHeight(node.getRightChild()));
return height;
}
public BinaryNode<T> copy() {
BinaryNode<T> newRoot = new BinaryNode<>(data);
if (leftChild != null)
newRoot.setLeftChild(leftChild.copy());
if (rightChild != null)
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
The more common implementation of a tree uses a linked structure where nodes represent each element in the tree. Each node can reference its children which are other nodes in the tree. A node object that represents a node in a tree references both data and the node"s children. Either reference to a child could be null; if both are null, the node is a leaf node. The class of tree nodes will not be internal to the class of binary trees; rather, the class of tree nodes will be defined outside of the binary tree class. The class of nodes will not be public use a package instead (contains the classes of various trees and their interfaces). Math. max(getheight(node. getleftchild()), getheight(node. getrightchild())); return height; public binarynode copy() { Binarynode newroot = new binarynode<>(data); if (leftchild != null) newroot. setleftchild(leftchild. copy()); if (rightchild != null) Recall the interface binarytreeinterface and its methods. public interface binarytreeinterface extends.
.jpg)