利用栈建立一个二叉树，然后用递归实现二叉树两个结点的最近公共祖先结点

import java.util.Stack; public class BinaryTree<T> { //二叉树类，二叉链表存储，T指定结点的元素类型 public BinaryNode<T>root; //根结点，二叉链表结点结构 public BinaryTree() //����ն����� { this.root=null; } public boolean isEmpty() //判断是否为空二叉树 { return this.root==null; } public void preOrder() //先根根次序遍历二叉树 { System.out.print("先根次序遍历二叉树： "); preOrder(root); System.out.println(); } public void preOrder(BinaryNode<T> p) //先根次序遍历以p结点为根的子二叉树，递归方法 { if (p!=null) { System.out.print(p.data.toString()+" "); preOrder(p.left); //先根次序遍历左子树，递归调用 preOrder(p.right); //先根次序遍历右子树，递归调用 } } public void inOrder() //中根次序遍历二叉树 { System.out.print("中根次序遍历二叉树： "); inOrder(root); System.out.println(); } public void inOrder(BinaryNode<T> p) //中根次序遍历以p结点为根的子二叉树，递归方法 { if (p!=null) { inOrder(p.left); //中根次序遍历左子树，递归调用 System.out.print(p.data.toString()+" "); inOrder(p.right); //中根次序遍历右子树，递归调用 } } public void postOrder() //后根次序遍历二叉树 { System.out.print("后根次序遍历二叉树： "); postOrder(root); System.out.println(); } public void postOrder(BinaryNode<T> p) //后根次序遍历以p结点为根的子二叉树，递归方法 { if (p!=null) { postOrder(p.left); postOrder(p.right); System.out.print(p.data.toString()+" "); } } /* public BinaryTree(T[] prelist) //以标明空子树的先根序列构造二叉树 { this.root = create(prelist); } //以标明空子树的先根序列构造一棵子二叉树，子树的根值是prelist[i]，返回所创建子树的根结点 private int i=0; private BinaryNode<T> create(T[] prelist) { BinaryNode<T> p = null; if (i<prelist.length) { T elem=prelist[i]; i++; if (elem!=null) //不能elem!="^"，因为T不一定是String { p = new BinaryNode<T>(elem); //创建叶子结点 p.left = create(prelist); //创建p的左子树 p.right = create(prelist); //创建p的右子树 } } return p; }*/ public BinaryTree(T[] prelist) //以标明空子树的先根序列构造二叉树 { this.root = createBiTree(prelist); } // 二叉树的建立（非递归）（按照先序遍历的顺序来生成一颗二叉树） public BinaryNode<T> createBiTree(T[] prelist) { BinaryNode<T> stack[]=new BinaryNode[1000]; // 用来存储节点的栈 int top = -1; int flag = 1; // 标志位 int i = 0; if (prelist[i] ==null) return null; BinaryNode<T> temp; BinaryNode<T> root = new BinaryNode<T>(); root.data = prelist[i++]; root.left = null; root.right =null; stack[++top] = root; // 根节点入栈 while (i < prelist.length) { BinaryNode<T> p = null; if (flag == 1) // 创建左孩子 { if (prelist[i] ==null) flag = 2; else { p= new BinaryNode<T>(); p.data = prelist[i]; p.left = null; p.right = null; temp = stack[top]; // 栈顶元素(取出栈顶元素赋予temp，注意，这不是出栈操作，因为栈top没有变) temp.left = p; stack[++top] = p; // 栈顶元素的左子树入栈 flag = 1; } } else if (flag == 2) // 创建右孩子 { if (prelist[i] ==null) flag = 3; else { p = new BinaryNode<T>(); p.data = prelist[i]; p.left = null; p.right = null; temp = stack[top]; // 栈顶元素 temp.right= p; stack[++top] = p; // 栈顶元素的右子树入栈 flag = 1; } } else // 左右孩子都已经创建完毕 { temp = stack[top--]; // 栈顶元素出栈，并修改栈顶 while (top > 0 && stack[top].right == temp) // 若此时栈中的元素个数仍大于1个，并且刚刚出栈的元素是当前栈顶元素的右子树，则继续让栈顶元素出栈，并修改栈顶指针。 --top; flag = 2; // 跳出此while循环时，创建当前栈顶节点的右孩子，此时的i在prelist[]中对应的数据刚好就是下一个待使用的数据，所以执行 --i是为了防止下面的 ++i跳过了该数据(即当前i对应的数据就是我们下一步创建右子树所应该使用的数据)。 --i; } i++; } return root; } //寻找两个结点的最近公共祖先结点 public BinaryNode<T> ancestor(BinaryNode<T> root,T x,T y){ if(root==null){ return null; } if(root.data== x|| root.data== y) return root; BinaryNode<T> left=ancestor(root.left,x,y); BinaryNode<T> right=ancestor(root.right,x,y); if(left==null){ return right; } else if(right==null){ return left; } else { return root; } } public BinaryNode<T> ancestor(T x,T y){ return ancestor(root,x,y); } public static void main(String args[]){ String[] prelist = {"A","B","D",null,"G",null,null,null,"C","E",null,null,"F","H",null,null,null}; BinaryTree<String> bitree = new BinaryTree<String>(prelist); bitree.preOrder(); bitree.inOrder(); bitree.postOrder(); String value1="E"; String value2="G"; System.out.println(value1+"和"+value2+"的最近的共同祖先结点为"+bitree.ancestor(value1,value2)); } }