Classification of binary trees (by storage structure)
Classification of trees (by storage structure)
Sequential storage (represented by arrays (static binary tree))
Chain storage
Some special binary roots:
Complete binary tree, balanced binary tree (AVL), clue binary tree, tri-fork (pointer with father)
Binary search tree or Binary search tree (BST)
The binary tree used is shown in the following figure:
Java implementation of binary tree (chain storage structure)
class TreeNode { private int key = 0; private String data = null; private boolean isVisted = false; private TreeNode leftChild = null; private TreeNode rightChild = null; public TreeNode(){ } public TreeNode(int key, String data){ this.key = key; this.data = data; this.leftChild = null; this.rightChild = null; } public int getKey() { return key; } public void setKey(int key) { this.key = key; } public String getData() { return data; } public void setData(String data) { this.data = data; } public TreeNode getLeftChild() { return leftChild; } public void setLeftChild(TreeNode leftChild) { this.leftChild = leftChild; } public TreeNode getRightChild() { return rightChild; } public void setRightChild(TreeNode rightChild) { this.rightChild = rightChild; } public boolean isVisted() { return isVisted; } public void setVisted(boolean isVisted) { this.isVisted = isVisted; }}public class BinaryTree { private TreeNode root = null; public BinaryTree() { root = new TreeNode(1, "rootNode(A)"); } public void createBinTree(TreeNode root){ //Manual creation (the structure is shown in the figure) TreeNode newNodeB = new TreeNode(2,"B"); TreeNode newNodeC = new TreeNode(3,"C"); TreeNode newNodeD = new TreeNode(4,"D"); TreeNode newNodeE = new TreeNode(5,"E"); TreeNode newNodeF = new TreeNode(6,"F"); root.setLeftChild(newNodeB); root.setRightChild(newNodeC); root.getLeftChild().setLeftChild(newNodeD); root.getLeftChild().setRightChild(newNodeE); root.getRightChild().setRightChild(newNodeF); } public boolean IsEmpty() { // Determine whether the binary tree is empty or not return root == null; } public int Height() { // Find the tree height return Height(root); } public int Height(TreeNode subTree) { if (subTree == null) return 0; //Recursive end: the height of the empty tree is 0 else { int i = Height(subTree.getLeftChild()); int j = Height(subTree.getRightChild()); return (i < j) ? j + 1 : i + 1; } } public int Size() { // Find the number of nodes return Size(root); } public int Size(TreeNode subTree) { if (subTree == null) return 0; else { return 1 + Size(subTree.getLeftChild()) + Size(subTree.getRightChild()); } } public TreeNode Parent(TreeNode element) { //Return the parent node return (root == null || root == element) ? null : Parent(root, element); } public TreeNode Parent(TreeNode subTree, TreeNode element) { if (subTree == null) return null; if (subTree.getLeftChild() == element || subTree.getRightChild() == element) //Finish, Return the parent node address return subTree; TreeNode p; //First look in the left subtree. If it is not found in the left subtree, go to the right subtree to find if ((p = Parent(subTree.getLeftChild(), element)) != null) //Recursively search for return p; else //Recursively search for return Parent(subTree.getRightChild(), element); } public TreeNode LeftChild(TreeNode element) { //Return the left subtree return (element != null) ? element.getLeftChild() : null; } public TreeNode RightChild(TreeNode element) { //Return the right subtree return (element != null) ? element.getRightChild() : null; } public TreeNode getRoot() { //Get the root node return root; } public void destroy(TreeNode subTree) { //Private function: Delete the subtree with root subTree if (subTree != null) { destroy(subTree.getLeftChild()); //Delete the left subtree destroy(subTree.getRightChild()); //Delete the right subtree//delete subTree; //Delete the root node subTree = null; } } public void Traverse(TreeNode subTree) { System.out.println("key:" + subTree.getKey() + "--name:" + subTree.getData()); Traverse(subTree.getLeftChild()); Traverse(subTree.getRightChild()); } public void PreOrder(TreeNode subTree) { //Root first if (subTree != null) { visted(subTree); PreOrder(subTree.getLeftChild()); PreOrder(subTree.getRightChild()); } } public void InOrder(TreeNode subTree) { //Medium root if (subTree != null) { InOrder(subTree.getLeftChild()); visted(subTree); InOrder(subTree.getRightChild()); } } public void PostOrder(TreeNode subTree) { //Post root if (subTree != null) { PostOrder(subTree.getLeftChild()); PostOrder(subTree.getRightChild()); visted(subTree); } } public void LevelOrder(TreeNode subTree) { //Horily periphery} public boolean Insert(TreeNode element){ //Insert return true; } public boolean Find(TreeNode element){ //Find return true; } public void witnessed(TreeNode subTree) { subTree.setVisted(true); System.out.println("key:" + subTree.getKey() + "--name:" + subTree.getData()); } public static void main(String[] args) { BinaryTree bt = new BinaryTree(); bt.createBinTree(bt.root); System.out.println("the size of the tree is " + bt.Size()); System.out.println("the height of the tree is " + bt.Height()); System.out.println("*********PreOrder (Preorder)[ABDECF]Transfer ****************"); bt.PreOrder(bt.root); System.out.println("*********Medium Root (Inner Order)[DBEACF]Transfer ****************"); bt.InOrder(bt.root); System.out.println("*********Last Root (Post Order)[DEBFCA]Transfer ****************"); bt.PostOrder(bt.root); }} Results output:
the size of the tree is 6
the height of the tree is 3
*******First root (preorder) [ABDECF] traversal ****************
key:1--name:rootNode(A)
key:2--name:B
key:4--name:D
key:5--name:E
key:3--name:C
key:6--name:F
*******Medium root (middle order)[DBEACF] traversal******************
key:4--name:D
key:2--name:B
key:5--name:E
key:1--name:rootNode(A)
key:3--name:C
key:6--name:F
*******Last Root (Post Order) [DEBFCA] traversal ****************
key:4--name:D
key:5--name:E
key:2--name:B
key:6--name:F
key:3--name:C
key:1--name:rootNode(A)
I hope this article will be helpful to students who study JAVA programming.