直接上代码了
package com.datastruct.binarytee;
import java.util.ArrayDeque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class BinaryTree {
//根节点
private BinaryTreeNode root;
public BinaryTreeNode getRoot() {
return root;
}
public void setRoot(BinaryTreeNode root) {
this.root = root;
}
/**
* @param val
* @return
* 创建二叉树节点
*/
public BinaryTreeNode createBinaryTreeNode(char val){
BinaryTreeNode node=new BinaryTreeNode(val,null,null);
return node;
}
/**
* @param parent
* @param left
* @param right
* @return
* 连接二叉树节点
*/
public BinaryTreeNode connectBinaryTreeNode(BinaryTreeNode parent,BinaryTreeNode left,BinaryTreeNode right){
if(parent!=null){
parent.leftChild=left;
parent.rightChild=right;
}
return parent;
}
/**
* 创建一棵二叉树
*
* A
* B C
* D E F
*/
public BinaryTreeNode createBinaryTree(char[] values){
BinaryTreeNode nodeA=new BinaryTreeNode('A',null,null);
BinaryTreeNode nodeB=new BinaryTreeNode('B',null,null);
BinaryTreeNode nodeC=new BinaryTreeNode('C',null,null);
BinaryTreeNode nodeD=new BinaryTreeNode('D',null,null);
BinaryTreeNode nodeE=new BinaryTreeNode('E',null,null);
BinaryTreeNode nodeF=new BinaryTreeNode('F',null,null);
nodeA.leftChild=nodeB;
nodeA.rightChild=nodeC;
nodeB.leftChild=nodeD;
nodeB.rightChild=nodeE;
nodeC.rightChild=nodeF;
root=nodeA;
return root;
}
/**
* @param node
* 递归前序遍历
*/
public void preOrderByRec(BinaryTreeNode node){
if(node==null)
return;
System.out.print(node.value);
preOrderByRec(node.leftChild);
preOrderByRec(node.rightChild);
}
/**
* @param node
* 递归中序遍历
*/
public void inOrderByRec(BinaryTreeNode node){
if(node==null)
return;
inOrderByRec(node.leftChild);
System.out.print(node.value);
inOrderByRec(node.rightChild);
}
/**
* @param node
* 递归后遍历
*/
public void postOrderByRec(BinaryTreeNode node){
if(node==null)
return;
postOrderByRec(node.leftChild);
postOrderByRec(node.rightChild);
System.out.print(node.value);
}
/**
* 非递归遍历二叉树
*/
public void preOrderByIte(BinaryTreeNode node){
if(node==null)
return;
Stack<BinaryTree.BinaryTreeNode> stack=new Stack<BinaryTree.BinaryTreeNode>();
stack.push(node);
while(!stack.empty()){
node=stack.pop();
System.out.print(node.value);
if(node.rightChild!=null)
stack.push(node.rightChild);
if(node.leftChild!=null)
stack.push(node.leftChild);
}
}
/**
* @param node
* 非递归中序遍历
*/
public void inOrderByIte(BinaryTreeNode node){
if(node==null)
return;
Stack<BinaryTree.BinaryTreeNode> stack=new Stack<BinaryTree.BinaryTreeNode>();
while(node!=null||stack.size()>0){
//左节点不为空，则进栈
while(node!=null){
stack.push(node);
node=node.leftChild;
}
//栈非空
if(stack.size()>0){
node=stack.pop();
System.out.print(node.value);
node=node.rightChild;
}
}
}
/**
* @param node
* 非递归后续遍历
*/
public void postOrderByIte(BinaryTreeNode node){
if(node==null)
return;
Stack<BinaryTree.BinaryTreeNode> stack=new Stack<BinaryTree.BinaryTreeNode>();
BinaryTreeNode pre=node;
while(node!=null){
//左子树非空的结点进栈
while(node.leftChild!=null){
stack.push(node);
node=node.leftChild;
}
//当前结点无右子树或右子树已访问输出
while(node!=null&&(node.rightChild==null||node.rightChild==pre)){
System.out.print(node.value);
pre=node;//记录上一个已经输出的结点
if(stack.empty())
return;
node=stack.pop();
}
//处理右子树
stack.push(node);
node=node.rightChild;
}
}
/**
* @param node
* 层序遍历
*/
public void levelTranvese(BinaryTreeNode node){
if(node==null)
return;
Queue<BinaryTreeNode> queue=new LinkedList<BinaryTree.BinaryTreeNode>();
queue.offer(node);
while(queue.size()!=0){
BinaryTreeNode temp=queue.poll();
System.out.print(temp.value);
if(temp.leftChild!=null)
queue.offer(temp.leftChild);
if(temp.rightChild!=null)
queue.offer(temp.rightChild);
}
}
/**
* @param node
* 计算节点数
*/
public int countNodeNum(BinaryTreeNode node){
if(node==null)
return 0;
return 1+countNodeNum(node.leftChild)+countNodeNum(node.rightChild);
}
/**
* @param node
* @return
* 计算二叉树的深度
*/
public int getMaxDepth(BinaryTreeNode node){
if(node==null)
return 0;
else{
int leftDepth=getMaxDepth(node.leftChild);
int rightDepth=getMaxDepth(node.rightChild);
return 1+(leftDepth>rightDepth?leftDepth:rightDepth);
}
}
/**
* @param node
* @return
* 计算二叉树的宽度
*/
public int getMaxWidth(BinaryTreeNode node){
if(node==null)
return 0;
Queue<BinaryTreeNode> queue=new ArrayDeque<BinaryTree.BinaryTreeNode>();
queue.offer(node);
int width=1;
while(true){
int len=queue.size();//当前层的结点数
if(len==0)
break;
while(len>0){//如果当前层还有结点
BinaryTreeNode temp=queue.poll();
len--;
if(temp.leftChild!=null)
queue.offer(temp.leftChild);//下一层结点入队
if(temp.rightChild!=null)
queue.offer(temp.rightChild);//下一层结点入队
}
width=width>queue.size()?width:queue.size();
}
return width;
}
/**
* 二叉树节点类
*
*/
class BinaryTreeNode{
char value;
BinaryTreeNode leftChild;
BinaryTreeNode rightChild;
//构造函数
public BinaryTreeNode(char value,BinaryTreeNode left,BinaryTreeNode right){
this.value=value;
this.leftChild=left;
this.rightChild=right;
}
}
}
还希望大家共同探讨，指出错误和不足之处