깊이 검색 귀속과 비귀속

  
  
  
  

   
   
   
   
public int depth(BinaryTreeNode<T> root) {  
   
   
   
   
int heightleft;  
   
   
   
   
int heightright;  
   
   
   
   
if (root == null) {  
   
   
   
   
return 0;  
   
   
   
   
}  
   
   
   
   
heightleft = depth(root.left);  
   
   
   
   
heightright = depth(root.right);  
   
   
   
   
return (heightleft > heightright ? heightleft : heightright) + 1;  
   
   
   
   
}  
   
   
   
   
 
   
   
   
   
public int depth() {  
   
   
   
   
Stack<BinaryTreeNode<T>> stack = new Stack<BinaryTreeNode<T>>();  
   
   
   
   
if (root == null)  
   
   
   
   
return 0;  
   
   
   
   
stack.push(root);  
   
   
   
   
BinaryTreeNode<T> node = root;  
   
   
   
   
BinaryTreeNode<T> popednode = null;  
   
   
   
   
int height = 0;  
   
   
   
   
int maxheight = 1;  
   
   
   
   
System.out.println("===================start===================");  
   
   
   
   
while (!stack.isEmpty()) {  
   
   
   
   
if (node.left != null && node.left != popednode) {  
   
   
   
   
System.out.println(" ");  
   
   
   
   
stack.push(node.left);  
   
   
   
   
node = node.left;  
   
   
   
   
maxheight++;  
   
   
   
   
} else if (node.right != null && node.right != popednode) {  
   
   
   
   
System.out.println(" ");  
   
   
   
   
popednode = stack.pop();  
   
   
   
   
stack.push(node.right);  
   
   
   
   
node = node.right;  
   
   
   
   
maxheight++;  
   
   
   
   
} else {  
   
   
   
   
System.out.println(" ");  
   
   
   
   
popednode = stack.pop();  
   
   
   
   
if (!stack.isEmpty()) {  
   
   
   
   
node = stack.peek();  
   
   
   
   
} else {  
   
   
   
   
node = null;  
   
   
   
   
}  
   
   
   
   
if (maxheight > height) {  
   
   
   
   
height = maxheight;  
   
   
   
   
}  
   
   
   
   
maxheight--;  
   
   
   
   
}  
   
   
   
   
}  
   
   
   
   
return height;  
   
   
   
   
}