//*****本程序包括简单的二叉树类的实现和前序,中序,后序,层次遍历二叉树算法,*******//
//******以及确定二叉树的高度,制定对象在树中的所处层次以及将树中的左右***********//
//******孩子节点对换位置,返回叶子节点个数删除叶子节点,并输出所删除的叶子节点**//
//*******************************CopyRight By phoenix*******************************************//
//************************************Jan 12,2008*************************************************//
//****************************************************************************************************//
public class BinTree {
public final static int MAX=40
private Object data//数据元数
private BinTree left,right//指向左,右孩子结点的链
BinTree []elements = new BinTree[MAX]//层次遍历时保存各个节点
int front//层次遍历时队首
int rear//层次遍历时队尾
public BinTree()
{
}
public BinTree(Object data)
{ //构造有值结点
this.data = data
left = right = null
}
public BinTree(Object data,BinTree left,BinTree right)
{ //构造有值结点
this.data = data
this.left = left
this.right = right
}
public String toString()
{
return data.toString()
}//前序遍历二叉树
public static void preOrder(BinTree parent){
if(parent == null)
return
System.out.print(parent.data+" ")
preOrder(parent.left)
preOrder(parent.right)
}//中序遍历二叉树
public void inOrder(BinTree parent){
if(parent == null)
return
inOrder(parent.left)
System.out.print(parent.data+" ")
inOrder(parent.right)
}//后序遍历二叉树
public void postOrder(BinTree parent){
if(parent == null)
return
postOrder(parent.left)
postOrder(parent.right)
System.out.print(parent.data+" ")
}// 层次遍历二叉树
public void LayerOrder(BinTree parent)
{
elements[0]=parent
front=0rear=1
while(front<rear)
{
try
{
if(elements[front].data!=null)
{
System.out.print(elements[front].data + " ")
if(elements[front].left!=null)
elements[rear++]=elements[front].left
if(elements[front].right!=null)
elements[rear++]=elements[front].right
front++
}
}catch(Exception e){break}
}
}//返回树的叶节点个数
public int leaves()
{
if(this == null)
return 0
if(left == null&&right == null)
return 1
return (left == null ? 0 : left.leaves())+(right == null ? 0 : right.leaves())
}//结果返回树的高度
public int height()
{
int heightOfTree
if(this == null)
return -1
int leftHeight = (left == null ? 0 : left.height())
int rightHeight = (right == null ? 0 : right.height())
heightOfTree = leftHeight<rightHeight?rightHeight:leftHeight
return 1 + heightOfTree
}
//如果对象不在树中,结果返回-1否则结果返回该对象在树中所处的层次,规定根节点为第一层
public int level(Object object)
{
int levelInTree
if(this == null)
return -1
if(object == data)
return 1//规定根节点为第一层
int leftLevel = (left == null?-1:left.level(object))
int rightLevel = (right == null?-1:right.level(object))
if(leftLevel<0&&rightLevel<0)
return -1
levelInTree = leftLevel<rightLevel?rightLevel:leftLevel
return 1+levelInTree
}
//将树中的每个节点的孩子对换位置
public void reflect()
{
if(this == null)
return
if(left != null)
left.reflect()
if(right != null)
right.reflect()
BinTree temp = left
left = right
right = temp
}// 将树中的所有节点移走,并输出移走的节点
public void defoliate()
{
String innerNode = ""
if(this == null)
return
//若本节点是叶节点，则将其移走
if(left==null&&right == null)
{
System.out.print(this + " ")
data = null
return
}
//移走左子树若其存在
if(left!=null){
left.defoliate()
left = null
}
//移走本节点，放在中间表示中跟移走...
innerNode += this + " "
data = null
//移走右子树若其存在
if(right!=null){
right.defoliate()
right = null
}
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
BinTree e = new BinTree("E")
BinTree g = new BinTree("G")
BinTree h = new BinTree("H")
BinTree i = new BinTree("I")
BinTree d = new BinTree("D",null,g)
BinTree f = new BinTree("F",h,i)
BinTree b = new BinTree("B",d,e)
BinTree c = new BinTree("C",f,null)
BinTree tree = new BinTree("A",b,c)
System.out.println("前序遍历二叉树结果: ")
tree.preOrder(tree)
System.out.println()
System.out.println("中序遍历二叉树结果: ")
tree.inOrder(tree)
System.out.println()
System.out.println("后序遍历二叉树结果: ")
tree.postOrder(tree)
System.out.println()
System.out.println("层次遍历二叉树结果: ")
tree.LayerOrder(tree)
System.out.println()
System.out.println("F所在的层次: "+tree.level("F"))
System.out.println("这棵二叉树的高度: "+tree.height())
System.out.println("--------------------------------------")
tree.reflect()
System.out.println("交换每个节点的孩子节点后......")
System.out.println("前序遍历二叉树结果: ")
tree.preOrder(tree)
System.out.println()
System.out.println("中序遍历二叉树结果: ")
tree.inOrder(tree)
System.out.println()
System.out.println("后序遍历二叉树结果: ")
tree.postOrder(tree)
System.out.println()
System.out.println("层次遍历二叉树结果: ")
tree.LayerOrder(tree)
System.out.println()
System.out.println("F所在的层次: "+tree.level("F"))
System.out.println("这棵二叉树的高度: "+tree.height())
}
java构造二叉树，可以通过链表来构造，如下代码：
public class BinTree {public final static int MAX=40
BinTree []elements = new BinTree[MAX]//层次遍历时保存各个节点
int front//层次遍历时队首
int rear//层次遍历时队尾
private Object data //数据元数
private BinTree left,right //指向左,右孩子结点的链
public BinTree()
{
}
public BinTree(Object data)
{ //构造有值结点
this.data = data
left = right = null
}
public BinTree(Object data,BinTree left,BinTree right)
{ //构造有值结点
this.data = data
this.left = left
this.right = right
}
public String toString()
{
return data.toString()
}
//前序遍历二叉树
public static void preOrder(BinTree parent){
if(parent == null)
return
System.out.print(parent.data+" ")
preOrder(parent.left)
preOrder(parent.right)
}
//中序遍历二叉树
public void inOrder(BinTree parent){
if(parent == null)
return
inOrder(parent.left)
System.out.print(parent.data+" ")
inOrder(parent.right)
}
//后序遍历二叉树
public void postOrder(BinTree parent){
if(parent == null)
return
postOrder(parent.left)
postOrder(parent.right)
System.out.print(parent.data+" ")
}
// 层次遍历二叉树
public void LayerOrder(BinTree parent)
{
elements[0]=parent
front=0rear=1
while(front<rear)
{
try
{
if(elements[front].data!=null)
{
System.out.print(elements[front].data + " ")
if(elements[front].left!=null)
elements[rear++]=elements[front].left
if(elements[front].right!=null)
elements[rear++]=elements[front].right
front++
}
}catch(Exception e){break}
}
}
//返回树的叶节点个数
public int leaves()
{
if(this == null)
return 0
if(left == null&&right == null)
return 1
return (left == null ? 0 : left.leaves())+(right == null ? 0 : right.leaves())
}
//结果返回树的高度
public int height()
{
int heightOfTree
if(this == null)
return -1
int leftHeight = (left == null ? 0 : left.height())
int rightHeight = (right == null ? 0 : right.height())
heightOfTree = leftHeight<rightHeight?rightHeight:leftHeight
return 1 + heightOfTree
}
//如果对象不在树中,结果返回-1否则结果返回该对象在树中所处的层次,规定根节点为第一层
public int level(Object object)
{
int levelInTree
if(this == null)
return -1
if(object == data)
return 1//规定根节点为第一层
int leftLevel = (left == null?-1:left.level(object))
int rightLevel = (right == null?-1:right.level(object))
if(leftLevel<0&&rightLevel<0)
return -1
levelInTree = leftLevel<rightLevel?rightLevel:leftLevel
return 1+levelInTree
}
//将树中的每个节点的孩子对换位置
public void reflect()
{
if(this == null)
return
if(left != null)
left.reflect()
if(right != null)
right.reflect()
BinTree temp = left
left = right
right = temp
}
// 将树中的所有节点移走,并输出移走的节点
public void defoliate()
{
if(this == null)
return
//若本节点是叶节点，则将其移走
if(left==null&&right == null)
{
System.out.print(this + " ")
data = null
return
}
//移走左子树若其存在
if(left!=null){
left.defoliate()
left = null
}
//移走本节点，放在中间表示中跟移走...
String innerNode += this + " "
data = null
//移走右子树若其存在
if(right!=null){
right.defoliate()
right = null
}
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
BinTree e = new BinTree("E")
BinTree g = new BinTree("G")
BinTree h = new BinTree("H")
BinTree i = new BinTree("I")
BinTree d = new BinTree("D",null,g)
BinTree f = new BinTree("F",h,i)
BinTree b = new BinTree("B",d,e)
BinTree c = new BinTree("C",f,null)
BinTree tree = new BinTree("A",b,c)
System.out.println("前序遍历二叉树结果: ")
tree.preOrder(tree)
System.out.println()
System.out.println("中序遍历二叉树结果: ")
tree.inOrder(tree)
System.out.println()
System.out.println("后序遍历二叉树结果: ")
tree.postOrder(tree)
System.out.println()
System.out.println("层次遍历二叉树结果: ")
tree.LayerOrder(tree)
System.out.println()
System.out.println("F所在的层次: "+tree.level("F"))
System.out.println("这棵二叉树的高度: "+tree.height())
System.out.println("--------------------------------------")
tree.reflect()
System.out.println("交换每个节点的孩子节点后......")
System.out.println("前序遍历二叉树结果: ")
tree.preOrder(tree)
System.out.println()
System.out.println("中序遍历二叉树结果: ")
tree.inOrder(tree)
System.out.println()
System.out.println("后序遍历二叉树结果: ")
tree.postOrder(tree)
System.out.println()
System.out.println("层次遍历二叉树结果: ")
tree.LayerOrder(tree)
System.out.println()
System.out.println("F所在的层次: "+tree.level("F"))
System.out.println("这棵二叉树的高度: "+tree.height())
}
二叉树的相关操作，包括创建，中序、先序、后序（递归和非递归），其中重点的是java在先序创建二叉树和后序非递归遍历的的实现。package com.algorithm.tree
import java.io.File
import java.io.FileNotFoundException
import java.util.Queue
import java.util.Scanner
import java.util.Stack
import java.util.concurrent.LinkedBlockingQueue
public class Tree {
private Node root
public Tree() {
}
public Tree(Node root) {
this.root = root
}
//创建二叉树
public void buildTree() {
Scanner scn = null
try {
scn = new Scanner(new File("input.txt"))
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace()
}
root = createTree(root,scn)
}
//先序遍历创建二叉树
private Node createTree(Node node,Scanner scn) {
String temp = scn.next()
if (temp.trim().equals("#")) {
return null
} else {
node = new Node((T)temp)
node.setLeft(createTree(node.getLeft(), scn))
node.setRight(createTree(node.getRight(), scn))
return node
}
}
//中序遍历(递归)
public void inOrderTraverse() {
inOrderTraverse(root)
}
public void inOrderTraverse(Node node) {
if (node != null) {
inOrderTraverse(node.getLeft())
System.out.println(node.getValue())
inOrderTraverse(node.getRight())
}
}
//中序遍历(非递归)
public void nrInOrderTraverse() {
Stack<Node>stack = new Stack<Node>()
Node node = root
while (node != null || !stack.isEmpty()) {
while (node != null) {
stack.push(node)
node = node.getLeft()
}
node = stack.pop()
System.out.println(node.getValue())
node = node.getRight()
}
}
//先序遍历(递归)
public void preOrderTraverse() {
preOrderTraverse(root)
}
public void preOrderTraverse(Node node) {
if (node != null) {
System.out.println(node.getValue())
preOrderTraverse(node.getLeft())
preOrderTraverse(node.getRight())
}
}
//先序遍历（非递归）
public void nrPreOrderTraverse() {
Stack<Node>stack = new Stack<Node>()
Node node = root
while (node != null || !stack.isEmpty()) {
while (node != null) {
System.out.println(node.getValue())
stack.push(node)
node = node.getLeft()
}
node = stack.pop()
node = node.getRight()
}
}
//后序遍历(递归)
public void postOrderTraverse() {
postOrderTraverse(root)
}
public void postOrderTraverse(Node node) {
if (node != null) {
postOrderTraverse(node.getLeft())
postOrderTraverse(node.getRight())
System.out.println(node.getValue())
}
}
//后续遍历(非递归)
public void nrPostOrderTraverse() {
Stack<Node>stack = new Stack<Node>()
Node node = root
Node preNode = null//表示最近一次访问的节点
while (node != null || !stack.isEmpty()) {
while (node != null) {
stack.push(node)
node = node.getLeft()
}
node = stack.peek()
if (node.getRight() == null || node.getRight() == preNode) {
System.out.println(node.getValue())
node = stack.pop()
preNode = node
node = null
} else {
node = node.getRight()
}
}
}
//按层次遍历
public void levelTraverse() {
levelTraverse(root)
}
public void levelTraverse(Node node) {
Queue<Node>queue = new LinkedBlockingQueue<Node>()
queue.add(node)
while (!queue.isEmpty()) {
Node temp = queue.poll()
if (temp != null) {
System.out.println(temp.getValue())
queue.add(temp.getLeft())
queue.add(temp.getRight())
}
}
}
}
//树的节点
class Node {
private Node left
private Node right
private T value
public Node() {
}
public Node(Node left,Node right,T value) {
this.left = left
this.right = right
this.value = value
}
public Node(T value) {
this(null,null,value)
}
public Node getLeft() {
return left
}
public void setLeft(Node left) {
this.left = left
}
public Node getRight() {
return right
}
public void setRight(Node right) {
this.right = right
}
public T getValue() {
return value
}
public void setValue(T value) {
this.value = value
}
}
测试代码：
package com.algorithm.tree
public class TreeTest {
/**
* @param args
*/
public static void main(String[] args) {
Tree tree = new Tree()
tree.buildTree()
System.out.println("中序遍历")
tree.inOrderTraverse()
tree.nrInOrderTraverse()
System.out.println("后续遍历")
//tree.nrPostOrderTraverse()
tree.postOrderTraverse()
tree.nrPostOrderTraverse()
System.out.println("先序遍历")
tree.preOrderTraverse()
tree.nrPreOrderTraverse()
//
}
}
