Home > Java, Mini-tips, Programación, Tips > Profundidad y diametro de un arbol binario en Java

Profundidad y diametro de un arbol binario en Java

November 9, 2011 Leave a comment Go to comments

public class Trees {
	public static int treeDepth(NodeBinaryTree root) {
		if (root == null)
			return 0;
                int lh = treeDepth(root.getLeft());
                int rh = treeDepth(root.getRight());
		return Util.max(lh, rh) + 1;
	}

	public static int treeDiameter(NodeBinaryTree root, Data ref) {
		if (root == null) {
			ref.level = 0;
			return 0;
		}
		Data lh = new Data(0), rh = new Data(0);
		int leftSubTree = treeDiameter(root.getLeft(), lh);
		int rightSubTree = treeDiameter(root.getRight(), rh);
		int subtreeDiameter = lh.elevel + rh.level + 1;
		ref.level = Util.max(lh.level, rh.level) + 1;
                int maxSubTree = Util.max(leftSubTree, rightSubTree);
		return Util.max(subtreeDiameter, maxSubTree);
	}

	public static void main(String args[]) {
		NodeBinaryTree uno = new NodeBinaryTree(1), 
			dos = new NodeBinaryTree(2), 
			tres = new NodeBinaryTree(3), 
			cuatro = new NodeBinaryTree(4), 
			cinco = new NodeBinaryTree(5);
		dos.setLeft(cuatro);
		dos.setRight(cinco);
		uno.setLeft(dos);
		uno.setRight(tres);
		System.out.println("La altura del arbol es " + treeDepth(uno));
		System.out.println("El diametro del arbol es "
				+ treeDiameter(uno, new Data(0)));
	}
}

Las clases utilizadas:


public class NodeBinaryTree {
	private NodeBinaryTree left, right;
	private Object value;

	public NodeBinaryTree getLeft() {
		return left;
	}

	public void setLeft(NodeBinaryTree left) {
		this.left = left;
	}

	public NodeBinaryTree getRight() {
		return right;
	}

	public void setRight(NodeBinaryTree right) {
		this.right = right;
	}

	public NodeBinaryTree() {
		left = null;
		right = null;
		setValue(null);
	}
	public NodeBinaryTree(int value){
		this();
		this.setValue(value);
	}

	public Object getValue() {
		return value;
	}

	public void setValue(Object value) {
		this.value = value;
	}

}



public class Util {
	public static int max(int a, int b){
		if(a > b)
			return a;
		return b;
	}
}


public class Data {
	int level;
	public Data(int val) {
		level = val;
	}
}

Fuente: GeeksForGeeks

Categories: Java, Mini-tips, Programación, Tips
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: