parent = s1.remove(0) ;
s2.remove(0) ;
}else{
break ;
}
}
return parent ;//返回第一个祖先节点
}
/**
* 从root开始查找值为data1的所有祖先节点，并将祖先节点存放在s中
* @param s : 存放祖先节点的栈
* @param root : 开始寻找的及诶单
* @param data ： 寻找节点的值
* @return ： 是否找到值为data1的节点
*/
public boolean findParents(Stack
if(root != null && !find){
s.push(root) ;//根节点入栈
if(data == root.getData()){
find = true ;//找到了节点
}else{
if(root.getLeftChild() != null){
findParents(s , root.getLeftChild() , data) ;//如果左边找到了
}
if(root.getRightChild() != null){
findParents(s, root.getRightChild() , data) ;
}
if(!find){//如果当前节点的左孩子和有孩子中都没有找到要查找的节点，则当前节点出栈。
s.pop() ;
}
}
}
return find;
}
/**
* 中序遍历递归算法
* @param node
*/
public void midList(Node node){
if(node != null){
midList(node.getLeftChild()) ;
System.out.print(node.getData() + ",");
midList(node.getRightChild()) ;
}
}
/**
* 中序遍历非递归算法
* @param node
*/
public void midList2(Node node){
Stack
while(node != null || !stack.isEmpty()){
if(node != null){
stack.push(node) ;
node = node.getLeftChild() ;
}else{
node = stack.pop() ;
System.out.print(node.getData() + ",");
node = node.getRightChild() ;
}
}
}
/**
* 先序遍历递归算法
* @param node
*/
public void preList(Node node){
if(node != null){
System.out.print(node.getData() + ",");
preList(node.getLeftChild()) ;
preList(node.getRightChild()) ;
}
}
/**
* 线序遍历的非递归实现
* @param node
*/
public void preList2(Node p){
Stack
while(p != null || !stack.isEmpty()){
if(p != null){
System.out.print(p.getData() + ",") ;//输出节点的值
stack.push(p) ; //把根节点入栈
p = p.getLeftChild() ;//寻找左孩子
}else{
p = stack.pop().getRightChild() ;
}
}
}
public Node getRoot() {
return root;
}
public void setRoot(Node root) {
this.root = root;
}
public int getCount() {
return count;
}
public void setCount(int count) {
this.count = count;
}
}
这里主要实现了二叉树的先序、中序、后序遍历的递归算法和非递归算法。对二叉树的深度和层次遍历没有实现，希望看了此文章的朋友们可以自己实现！
p rP @ an>
/**
* 查找值data1和data2的第一个祖先节点，返回第一个祖先节点.此处定义了两个栈作为辅助，需要遍历两次二叉树。程序可以大量优化。
* @param root : 从root开始查找
* @param data1 ： 值为data1的节点
* @param data2 : 值为data2的节点
* @return
*/
public Node findNode(Node root , int data1 , int data2) {
Stack
Stack
findParents(s1 , root , data1) ;//将data1的所有祖先节点存放在s1中
this.find = false ;
findParents(s2 , root , data2) ;//将data2的所有祖先节点存放在s2中
Node parent = null ;
while(s1.size()>0 && s2.size()>0 ){//查找第一个祖先节点
if(s1.get(0).getData() == s2.get(0).getData()){
parent = s1.remove(0) ;
s2.remove(0) ;
}else{
break ;
}
}
return parent ;//返回第一个祖先节点
}
/**
* 从root开始查找值为data1的所有祖先节点，并将祖先节点存放在s中
* @param s : 存放祖先节点的栈
* @param root : 开始寻找的及诶单
* @param data ： 寻找节点的值
* @return ： 是否找到值为data1的节点
*/
public boolean findParents(Stack
if(root != null && !find){
s.push(root) ;//根节点入栈
if(data == root.getData()){
find = true ;//找到了节点
}else{
if(root.getLeftChild() != null){
findParents(s , root.getLeftChild() , data) ;//如果左边找到了
}
if(root.getRightChild() != null){
findParents(s, root.getRightChild() , data) ;
}
if(!find){//如果当前节点的左孩子和有孩子中都没有找到要查找的节点，则当前节点出栈。
s.pop() ;
}
}
}
return find;
}
/**
* 中序遍历递归算法
* @param node
*/
public void midList(Node node){
if(node != null){
midList(node.getLeftChild()) ;
System.out.print(node.getData() + ",");
midList(node.getRightChild()) ;
}
}
/**
* 中序遍历非递归算法