二叉树之二叉链表

　　/**
　　* 求二叉树中特定子结点的父结点
　　* @param root
　　* @param childNode
　　* @return 存在父结点时，返回父结点；否则，返回null
　　*/
　　public BinaryTreeNode<E> getParent(BinaryTreeNode<E> root， BinaryTreeNode<E> childNode){
　　if(root == null){
　　return null;
　　}
　　if(root.leftChild == childNode || root.rightChild == childNode){
　　return root;
　　}
　　if(getParent(root.leftChild， childNode) != null){
　　return getParent(root.leftChild， childNode);
　　}else{
　　return getParent(root.rightChild， childNode);
　　}
　　}
　　/**
　　* 递归删除二叉树，释放相应的存储空间
　　* @param root
　　*/
　　public void destoryBinaryTree(BinaryTreeNode<E> root){
　　if(root != null){
　　destoryBinaryTree(root.leftChild);
　　destoryBinaryTree(root.rightChild);
　　root = null;
　　}
　　}
　　/**
　　* 层序遍历（广度优先遍历）
　　* @param root
　　*/
　　public void levelOrder(BinaryTreeNode<E> root){
　　Queue<BinaryTreeNode<E>> queue = new LinkedBlockingQueue<BinaryTreeNode<E>>();
　　BinaryTreeNode<E> pointer = root;
　　/**
　　* 当前结点非空时，放入队首
　　*/
　　if(pointer != null){
　　queue.add(pointer);
　　}
　　/*
　　* 队列不为空时，先访问中间节点，访问完成后弹出队首节点；然后是左节点，再是右节点；
　　*/
　　while(!queue.isEmpty()){
　　pointer = queue.peek();  
　　visit(pointer);
　　queue.remove();
　　if(pointer.leftChild != null){
　　queue.add(pointer);
　　}
　　if(pointer.rightChild != null){
　　queue.add(pointer);
　　}
　　}
　　}
　　/**
　　* 递归先序遍历二叉树
　　* @param root
　　*/
　　public void preOrder(BinaryTreeNode<E> root){
　　if (root == null){
　　return;
　　}             
　　visit(root);
　　preOrder(root.leftChild);
　　preOrder(root.rightChild);
　　}
　　/**
　　* 非递归先序遍历二叉树
　　* @param root
　　*/
　　public void nPreOrder(BinaryTreeNode<E> root){
　　Stack<BinaryTreeNode<E>> stack = new Stack<BinaryTreeNode<E>>();
　　BinaryTreeNode<E> pointer = root;
　　while(!stack.isEmpty() || pointer != null){
　　if(pointer != null){
　　visit(pointer);
　　if(pointer.rightChild != null){
　　stack.push(pointer.rightChild);
　　}
　　pointer = pointer.leftChild;
　　}else{
　　pointer = stack.pop();
　　}
　　}
　　}
　　/**
　　* 递归中序遍历
　　* @param root
　　*/
　　public void inOrder(BinaryTreeNode<E> root){
　　if (root == null){
　　return;
　　}  
　　inOrder(root.leftChild);
　　visit(root);
　　inOrder(root.rightChild);
　　}
　　/**
　　* 非递归中序遍历1
　　* @param root
　　*/
　　public void nInOrder(BinaryTreeNode<E> root){
　　Stack<BinaryTreeNode<E>> stack = new Stack<BinaryTreeNode<E>>();
　　BinaryTreeNode<E> pointer = root;
　　while(pointer != null || !stack.isEmpty()){
　　if(pointer != null){
　　stack.push(pointer);
　　pointer = pointer.leftChild;
　　}else{
　　pointer = stack.pop();
　　visit(pointer);
　　pointer = pointer.rightChild;              
　　}
　　}
　　}
　　/**
　　* 非递归中序遍历2
　　* @param root
　　*/
　　public void nInOrders(BinaryTreeNode<E> root){
　　Stack<BinaryTreeNode<E>> stack = new Stack<BinaryTreeNode<E>>();
　　BinaryTreeNode<E> pointer = root;
　　stack.push(pointer);
　　while(!stack.isEmpty()){
　　while(pointer != null){
　　stack.push(pointer.leftChild);
　　pointer = pointer.leftChild;
　　}
　　stack.pop();
　　if(!stack.isEmpty()){
　　pointer = stack.pop();
　　visit(pointer);
　　pointer = pointer.rightChild;
　　stack.push(pointer);
　　}
　　}
　　}
　　/**
　　* 递归后序遍历
　　* @param root
　　*/
　　public void postOrder(BinaryTreeNode<E> root){
　　if (root == null){
　　return;
　　}  
　　postOrder(root.leftChild);
　　postOrder(root.rightChild);
　　visit(root);
　　}
　　/**
　　* 非递归后序遍历
　　* @param root
　　*/
　　public void nPostOrder(BinaryTreeNode<E> root){
　　Stack<BinaryTreeNode<E>> stack = new Stack<BinaryTreeNode<E>>(); //初始化栈，用于保存带访问的节点
　　BinaryTreeNode<E> pointer = root;                                //保存根节点
　　BinaryTreeNode<E> preNode = root;                                //保存前一个被访问的节点
　　while(!stack.isEmpty() || pointer != null){
　　//若当前节点不空，一直进栈，然后继续向左走
　　while(pointer.leftChild != null){
　　stack.push(pointer);
　　pointer = pointer.leftChild;
　　}
　　/*
　　* 当前节点为空时，分两种情况：
　　* 1、当前节点移动到栈顶处，然后访问栈顶元素的右节点
　　* 2、当前节点移动到栈顶，但是栈顶元素没有右节点，这需要弹出栈顶元素，再对此元素访问；
　　* 然后再对新的栈顶元素进行判断即可
　　*/
　　while((pointer != null && pointer.rightChild == null) || pointer.rightChild == preNode){
　　visit(pointer);
　　preNode = pointer;
　　if(stack.isEmpty()){
　　return;
　　}
　　pointer = stack.pop();
　　}
　　stack.push(pointer);
　　pointer = pointer.rightChild;
　　}
　　}
　　/**
　　* 访问当前结点
　　* @param current
　　*/
　　public void visit(BinaryTreeNode<E> current){
　　if(current != null && current.element != null){
　　System.out.println(current.element);
　　}else{
　　System.out.println("null");
　　}
　　}
　　}
　　3. 参考文献
　　1. java创建二叉树并递归遍历二叉树
　　2. java实现二叉树相关代码—–数据结构
　　3. Java实现二叉树的创建、递归/非递归遍历
　　4. Java实现二叉树的创建和遍历操作（有更新）