【DataStructure】Implemantation of Binary Tree

本文主要是介绍【DataStructure】Implemantation of Binary Tree，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Statements: This blog was written by me, but most of content is quoted from book【Data Structure with Java Hubbard】

Here is a class for binary trees that directly implements the recursive definition. By extending the AbstractCollectionclass, it remains consistent with the Java Collections Framework.

【Implementation】

package com.albertshao.ds.tree;//  Data Structures with Java, Second Edition
//  by John R. Hubbard
//  Copyright 2007 by McGraw-Hillimport java.util.*;public class BinaryTree<E> extends AbstractCollection {protected E root;protected BinaryTree<E> left, right, parent;protected int size;public BinaryTree() {}public BinaryTree(E root) {this.root = root;size = 1;}public BinaryTree(E root, BinaryTree<E> left, BinaryTree<E> right) {this(root);if (left != null) {this.left = left;left.parent = this;size += left.size();}if (right != null) {this.right = right;right.parent = this;size += right.size();}}public boolean equals(Object object) {if (object == this) {return true;} else if (!(object instanceof BinaryTree)) {return false;}BinaryTree that = (BinaryTree)object;return that.root.equals(this.root)&& that.left.equals(this.left)&& that.right.equals(this.right)&& that.parent.equals(this.parent)&& that.size == this.size;}public int hashCode() {return root.hashCode() + left.hashCode() + right.hashCode() + size;}public int size() {return size;}public Iterator iterator() {return new java.util.Iterator() { // anonymous inner classprivate boolean rootDone;private Iterator lIt, rIt;  // child iteratorspublic boolean hasNext() {return !rootDone || lIt != null && lIt.hasNext()|| rIt != null && rIt.hasNext();}public Object next() {if (rootDone) {if (lIt != null && lIt.hasNext()) {return lIt.next();}if (rIt != null && rIt.hasNext()) {return rIt.next();}return null;}if (left != null) {lIt = left.iterator();}if (right != null) {rIt = right.iterator();}rootDone = true;return root;}public void remove() {throw new UnsupportedOperationException(); }};}
}

【Test】

package com.albertshao.ds.tree;//  Data Structures with Java, Second Edition
//  by John R. Hubbard
//  Copyright 2007 by McGraw-Hillpublic class TestBinaryTree {static public void main(String[] args) {BinaryTree<String> e = new BinaryTree<String>("E");BinaryTree<String> g = new BinaryTree<String>("G");BinaryTree<String> h = new BinaryTree<String>("H");BinaryTree<String> i = new BinaryTree<String>("I");BinaryTree<String> d = new BinaryTree<String>("D", null, g);BinaryTree<String> f = new BinaryTree<String>("F", h, i);BinaryTree<String> b = new BinaryTree<String>("B", d, e);BinaryTree<String> c = new BinaryTree<String>("C", f, null);BinaryTree<String> tree = new BinaryTree<String>("A", b, c);System.out.printf("tree: %s", tree);}
}

【Result】