Advertisement
jtentor

Árbol - BinaryTree.java

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