Advertisement
jtentor

DemoTree1 - BinaryTree.java

Jun 23rd, 2020
505
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 4.81 KB | None | 0 0
  1. // Created by Julio Tentor <jtentor@fi.unju.edu.ar>
  2. //
  3. public class BinaryTree<ELEMENT> {
  4.  
  5.     private 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.     private 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 = sb + root.item.toString()
  63.             sb.append(root.item.toString());
  64.             if (root.left != null) {
  65.                 sb.append("(" + toString(root.left));
  66.                 if (root.right != null) {
  67.                     sb.append("," + toString(root.right));
  68.                 }
  69.                 sb.append(")");
  70.             } else {
  71.                 if (root.right != null) {
  72.                     sb.append("(," + toString(root.right) + ")");
  73.                 }
  74.             }
  75.         }
  76.         return sb.toString();
  77.     }
  78.  
  79.  
  80.     public void PreOrder() {
  81.         PreOrder(this.root);
  82.     }
  83.     protected void PreOrder(BTNode<ELEMENT> root) {
  84.         if (root != null) {
  85.             root.Visit();
  86.             PreOrder(root.left);
  87.             PreOrder(root.right);
  88.         }
  89.     }
  90.  
  91.     public void InOrder() {
  92.         InOrder(this.root);
  93.     }
  94.     protected void InOrder(BTNode<ELEMENT> root) {
  95.         if (root != null) {
  96.             InOrder(root.left);
  97.             root.Visit();
  98.             InOrder(root.right);
  99.         }
  100.     }
  101.  
  102.     public void PostOrder() {
  103.         PostOrder(this.root);
  104.     }
  105.     protected void PostOrder(BTNode<ELEMENT> root) {
  106.         if (root != null) {
  107.             PostOrder(root.left);
  108.             PostOrder(root.right);
  109.             root.Visit();
  110.         }
  111.     }
  112.  
  113.     public void DescendingOrder() {
  114.         DescendingOrder(this.root);
  115.     }
  116.     protected void DescendingOrder(BTNode<ELEMENT> root) {
  117.         if (root != null) {
  118.             DescendingOrder(root.right);
  119.             root.Visit();
  120.             DescendingOrder(root.left);
  121.         }
  122.     }
  123.  
  124.  
  125.     public int NodeCount() {
  126.         return NodeCount(this.root);
  127.     }
  128.     protected int NodeCount(BTNode<ELEMENT> root) {
  129.         if (root != null) {
  130.             return 1 + NodeCount(root.left) + NodeCount(root.right);
  131.         }
  132.         return 0;
  133.     }
  134.  
  135.  
  136.     public int LeafCount() {
  137.         return LeafCount(this.root);
  138.     }
  139.     protected int LeafCount(BTNode<ELEMENT> root) {
  140.         if (root != null) {
  141.             if ( (root.left == null) && (root.right == null) ) {
  142.                 return 1;
  143.             } else {
  144.                 return LeafCount(root.left) + LeafCount(root.right);
  145.             }
  146.         }
  147.         return 0;
  148.     }
  149.  
  150.  
  151.     public int InternalCount() {
  152.         return InternalCount(this.root);
  153.     }
  154.     protected int InternalCount(BTNode<ELEMENT> root) {
  155.         if (root != null) {
  156.             if ( (root.left == null) && (root.right == null) ) {
  157.                 return 0;
  158.             } else {
  159.                 return 1 + InternalCount(root.left) + InternalCount(root.right);
  160.             }
  161.         }
  162.         return 0;
  163.     }
  164.  
  165.  
  166.     public int MaxLevel() {
  167.         return MaxLevel(this.root);
  168.     }
  169.     protected int MaxLevel(BTNode<ELEMENT> root) {
  170.         if (root != null) {
  171.             if ( (root.left != null) || (root.right != null) ) {
  172.                 int leftLevel = MaxLevel(root.left);
  173.                 int rightLevel = MaxLevel(root.right);
  174.                 return 1 + Math.max(leftLevel, rightLevel);
  175.             }
  176.             return 0;
  177.         }
  178.         return -1;
  179.     }
  180.  
  181.  
  182.     public int Height() {
  183.         return MaxLevel() + 1;
  184.     }
  185. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement