Advertisement
jtentor

DemoTree2 - BinaryTree.java

Jun 23rd, 2020
485
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Created by Julio Tentor <jtentor@fi.unju.edu.ar>
  2. //
  3. public class BinaryTree<ELEMENT> {
  4.  
  5.     protected class BTNode<ELEMENT> {
  6.         public ELEMENT item;
  7.         public BTNode<ELEMENT> left;
  8.         public BTNode<ELEMENT> right;
  9.  
  10.         public BTNode() {
  11.             this(null, null, null);
  12.         }
  13.         public BTNode(ELEMENT item) {
  14.             this(item, null, null);
  15.         }
  16.         public BTNode(ELEMENT item, BTNode<ELEMENT> left, BTNode<ELEMENT> right) {
  17.             this.item = item;
  18.             this.left = left;
  19.             this.right = right;
  20.         }
  21.  
  22.         @Override
  23.         public String toString() {
  24.             return this.item.toString();
  25.         }
  26.  
  27.         // Método para propósitos académicos
  28.         public void Visit() {
  29.             System.out.printf("%s ", this.item.toString());
  30.         }
  31.     }
  32.  
  33.  
  34.  
  35.  
  36.     protected BTNode<ELEMENT> root;
  37.  
  38.     public BinaryTree() {
  39.         this.root = null;
  40.     }
  41.     // Métodos para propósitos académicos
  42.     public BinaryTree(ELEMENT item) {
  43.         this(item, null, null);
  44.     }
  45.     public BinaryTree(ELEMENT item, BinaryTree<ELEMENT> left, BinaryTree<ELEMENT> right) {
  46.         this.root = new BTNode<ELEMENT>(item, null, null);
  47.         if (left != null) {
  48.             this.root.left = left.root;
  49.         }
  50.         if (right != null) {
  51.             this.root.right = right.root;
  52.         }
  53.     }
  54.  
  55.     @Override
  56.     public String toString() {
  57.         return toString(this.root);
  58.     }
  59.     protected String toString(BTNode<ELEMENT> root) {
  60.         StringBuilder sb = new StringBuilder();
  61.         if (root != null) {
  62.             sb.append(root.item.toString());
  63.             if (root.left != null) {
  64.                 sb.append("(" + toString(root.left));
  65.                 if (root.right != null) {
  66.                     sb.append("," + toString(root.right));
  67.                 }
  68.                 sb.append(")");
  69.             } else {
  70.                 if (root.right != null) {
  71.                     sb.append("(," + toString(root.right) + ")");
  72.                 }
  73.             }
  74.         }
  75.         return sb.toString();
  76.     }
  77.  
  78.  
  79.     public void PreOrder() {
  80.         PreOrder(this.root);
  81.     }
  82.     protected void PreOrder(BTNode<ELEMENT> root) {
  83.         if (root != null) {
  84.             root.Visit();
  85.             PreOrder(root.left);
  86.             PreOrder(root.right);
  87.         }
  88.     }
  89.  
  90.     public void InOrder() {
  91.         InOrder(this.root);
  92.     }
  93.     protected void InOrder(BTNode<ELEMENT> root) {
  94.         if (root != null) {
  95.             InOrder(root.left);
  96.             root.Visit();
  97.             InOrder(root.right);
  98.         }
  99.     }
  100.  
  101.     public void PostOrder() {
  102.         PostOrder(this.root);
  103.     }
  104.     protected void PostOrder(BTNode<ELEMENT> root) {
  105.         if (root != null) {
  106.             PostOrder(root.left);
  107.             PostOrder(root.right);
  108.             root.Visit();
  109.         }
  110.     }
  111.  
  112.     public void DescendingOrder() {
  113.         DescendingOrder(this.root);
  114.     }
  115.     protected void DescendingOrder(BTNode<ELEMENT> root) {
  116.         if (root != null) {
  117.             DescendingOrder(root.right);
  118.             root.Visit();
  119.             DescendingOrder(root.left);
  120.         }
  121.     }
  122.  
  123.  
  124.     public int NodeCount() {
  125.         return NodeCount(this.root);
  126.     }
  127.     protected int NodeCount(BTNode<ELEMENT> root) {
  128.         if (root != null) {
  129.             return 1 + NodeCount(root.left) + NodeCount(root.right);
  130.         }
  131.         return 0;
  132.     }
  133.  
  134.  
  135.     public int LeafCount() {
  136.         return LeafCount(this.root);
  137.     }
  138.     protected int LeafCount(BTNode<ELEMENT> root) {
  139.         if (root != null) {
  140.             if ( (root.left == null) && (root.right == null) ) {
  141.                 return 1;
  142.             } else {
  143.                 return LeafCount(root.left) + LeafCount(root.right);
  144.             }
  145.         }
  146.         return 0;
  147.     }
  148.  
  149.  
  150.     public int InternalCount() {
  151.         return InternalCount(this.root);
  152.     }
  153.     protected int InternalCount(BTNode<ELEMENT> root) {
  154.         if (root != null) {
  155.             if ( (root.left == null) && (root.right == null) ) {
  156.                 return 0;
  157.             } else {
  158.                 return 1 + InternalCount(root.left) + InternalCount(root.right);
  159.             }
  160.         }
  161.         return 0;
  162.     }
  163.  
  164.  
  165.     public int MaxLevel() {
  166.         return MaxLevel(this.root);
  167.     }
  168.     protected int MaxLevel(BTNode<ELEMENT> root) {
  169.         if (root != null) {
  170.             if ( (root.left != null) || (root.right != null) ) {
  171.                 int leftLevel = MaxLevel(root.left);
  172.                 int rightLevel = MaxLevel(root.right);
  173.                 return 1 + Math.max(leftLevel, rightLevel);
  174.             }
  175.             return 0;
  176.         }
  177.         return -1;
  178.     }
  179.  
  180.  
  181.     public int Height() {
  182.         return MaxLevel() + 1;
  183.     }
  184. }
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement