java实现二叉树的创建递归非递归遍历.docx
《java实现二叉树的创建递归非递归遍历.docx》由会员分享，可在线阅读，更多相关《java实现二叉树的创建递归非递归遍历.docx（9页珍藏版）》请在冰点文库上搜索。
java实现二叉树的创建递归非递归遍历
Java实现二叉树的创建、递归非递归遍历
/**二叉树的结点定义*/
classNode<T>{
privateTvalue;
privateNode<T>left;
privateNode<T>right;
publicNode（）{
}
publicNode（Node<T>left,Node<T>right,Tvalue）{
this.left=left;
this.right=right;
this.value=value;
}
publicNode（Tvalue）{
this（null,null,value）;
}
publicNode<T>getLeft（）{
returnthis.left;
}
publicvoidsetLeft（Node<T>left）{
this.left=left;
}
publicNode<T>getRight（）{
returnthis.right;
}
publicvoidsetRight（Node<T>right）{
this.right=right;
}
publicTgetValue（）{
returnthis.value;
}
publicvoidsetValue（Tvalue）{
this.value=value;
}
}
[java]viewplaincopyimportjava.io.File;
importjava.io.FileNotFoundException;
importjava.util.LinkedList;
importjava.util.Scanner;
/**
*二叉树的定义：
或为空，或只有根节点，或有左子树和右子树（5种基本形态）
*二叉树性质：
*1、在二叉树的第i层上至多有2^（i-1）个结点（i>=1）
*2、深度为k的二叉树至多有2^（k）-1个结点（k>=1）
*3、对于任何一颗二叉树，如果其终端结点数为n，度数为2的结点数为m，则n=m+1
*4、具有n个结点的完全二叉树的深度为k=floor（log2（n））+1
*5、在含有n个结点的二叉链表中有n+1个空链域
*
*@author小菜鸟
*创建时间：
2014-08-10
*/
publicclassBinaryTree<T>{
/**二叉树的根节点*/
privateNode<T>root;
publicBinaryTree（）{}
publicBinaryTree（Node<T>root）{
this.root=root;
}
/**先序遍历创建二叉树*/
/**input.txt:
-+a##*##/e##f##
*#代表空结点
*/
publicvoidcreateBiTree（）{
Scannerscn=null;
try{
scn=newScanner（newFile（"input.txt"））;
}catch（FileNotFoundExceptione）{
e.printStackTrace（）;
}
this.root=createBiTree（root,scn）;
}
privateNode<T>createBiTree（Node<T>node,Scannerscn）{
Stringtemp=scn.next（）;
if（temp.trim（）.equals（"#"））{
returnnull;
}
else{
node=newNode<T>（（T）temp）;
node.setLeft（createBiTree（node.getLeft（）,scn））;
node.setRight（createBiTree（node.getRight（）,scn））;
returnnode;
}
}
/**先序递归遍历二叉树*/
publicvoidpreOrderTraverse（）{
preOrderTraverse（root）;
}
privatevoidpreOrderTraverse（Node<T>node）{
if（node!
=null）{
System.out.println（node.getValue（））;
preOrderTraverse（node.getLeft（））;
preOrderTraverse（node.getRight（））;
}
}
/**先序非递归遍历二叉树*/
publicvoidnrPreOrderTraverse（）{
Stack<Node<T>>stack=newStack<Node<T>>（）;
Node<T>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（）;
}
}
/**中序递归遍历二叉树*/
publicvoidinOrderTraverse（）{
inOrderTraverse（root）;
}
privatevoidinOrderTraverse（Node<T>node）{
if（node!
=null）{
inOrderTraverse（node.getLeft（））;
System.out.println（node.getValue（））;
inOrderTraverse（node.getRight（））;
}
}
/**中序非递归遍历二叉树*/
publicvoidnrInOrderTraverse（）{
Stack<Node<T>>stack=newStack<Node<T>>（）;
Node<T>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（）;
}
}
/**后序递归遍历二叉树*/
publicvoidpostOrderTraverse（）{
postOrderTraverse（root）;
}
privatevoidpostOrderTraverse（Node<T>node）{
if（node!
=null）{
postOrderTraverse（node.getLeft（））;
postOrderTraverse（node.getRight（））;
System.out.println（node.getValue（））;
}
}
/**后序非递归遍历二叉树*/
publicvoidnrPostOrderTraverse（）{
Stack<Node<T>>stack=newStack<Node<T>>（）;
Node<T>node=root;
Node<T>preNode=null;//记录之前遍历的右结点
while（node!
=null||!
stack.isEmpty（））{
while（node!
=null）{
stack.push（node）;
node=node.getLeft（）;
}
node=stack.getTop（）;
/**如果右结点为空，或者右结点之前遍历过，打印根结点*/
if（node.getRight（）==null||node.getRight（）==preNode）{
System.out.println（node.getValue（））;
node=stack.pop（）;
preNode=node;
node=null;
}
else{
node=node.getRight（）;
}
}
}
/**层次遍历二叉树*/
publicvoidlevelTraverse（）{
levelTraverse（root）;
}
privatevoidlevelTraverse（Node<T>node）{
Queue<Node<T>>queue=newQueue<Node<T>>（）;
queue.push（node）;
while（!
queue.isEmpty（））{
node=queue.pop（）;
if（node!
=null）{
System.out.println（node.getValue（））;
queue.push（node.getLeft（））;
queue.push（node.getRight（））;
}
}
}
publicstaticvoidmain（String[]args）{
BinaryTree<String>bt=newBinaryTree<String>（）;
bt.createBiTree（）;
//bt.preOrderTraverse（）;
//bt.inOrderTraverse（）;
//bt.postOrderTraverse（）;
//bt.nrPreOrderTraverse（）;
//bt.nrInOrderTraverse（）;
//bt.nrPostOrderTraverse（）;
bt.levelTraverse（）;
}
}
升级会员 