首页 > 代码库 > 二叉树的创建和四种遍历（前序、先序、后序、层次、结点的层数、深度、叶子数等）—java描述
二叉树的创建和四种遍历（前序、先序、后序、层次、结点的层数、深度、叶子数等）—java描述
二叉树的创建和四种遍历（前序、先序、后序、层次、结点的层数、深度、叶子数等）—java描述
package javab;
//树的结点类
public class TreeNode {
String data;
TreeNode leftChild,rightChild,next;
public TreeNode(String data){
this.data=data;
}
public TreeNode(String data,TreeNode left,TreeNode right){
leftChild=left;
rightChild=right;
}
public String getdata(){
return data;
}
public void setleftChild(TreeNode left){
leftChild=left;
}
public void setrightChild(TreeNode right){
rightChild=right;
}
}
package javab;
//二叉树结构
public class BinaryTree {
TreeNode root;
public BinaryTree(String data){
setTree(data);
}
public BinaryTree(String data,BinaryTree left,BinaryTree right){
setTree(data,left,right);
}
void setTree(String data){
root=new TreeNode(data);
}
void setTree(String data,BinaryTree left,BinaryTree right){
root=new TreeNode(data);
if(left!=null){
root.setleftChild(left.root);
}
if(right!=null){
root.setrightChild(right.root);
}
}
}
package javab;
//遍历
public class Tree {
static BinaryTree create(){
BinaryTree tree7=new BinaryTree("7");
BinaryTree tree8=new BinaryTree("8");
BinaryTree tree9=new BinaryTree("9");
BinaryTree tree10=new BinaryTree("10");
BinaryTree tree11=new BinaryTree("11");
BinaryTree tree12=new BinaryTree("12");
BinaryTree tree4=new BinaryTree("4",tree8,tree9);
BinaryTree tree5=new BinaryTree("5",tree10,tree11);
BinaryTree tree6=new BinaryTree("6",tree12,null);
BinaryTree tree3=new BinaryTree("3",tree6,tree7);
BinaryTree tree2=new BinaryTree("2",tree4,tree5);
BinaryTree tree1=new BinaryTree("1",tree2,tree3);
return tree1;
}
static void preorder(TreeNode t){
if(t!=null){
System.out.print(t.data+" ");
preorder(t.leftChild);
preorder(t.rightChild);
}
}
static void inorder(TreeNode t){
if(t!=null){
inorder(t.leftChild);
System.out.print(t.data+" ");
inorder(t.rightChild);
}
}
static void postorder(TreeNode t){
if(t!=null){
postorder(t.leftChild);
postorder(t.rightChild);
System.out.print(t.data+" ");
}
}
static void levelorder(TreeNode t){
TreeNode head=t;
TreeNode tail=head;
while(head.leftChild!=null&&head.rightChild!=null){
tail.next=head.leftChild;
tail=tail.next;
tail.next=head.rightChild;
tail=tail.next;
System.out.print(head.data+" ");
head=head.next;
}
while(head!=null){
System.out.print(head.data+" ");
head=head.next;
}
}
//二叉树的非递归先序遍历
static void preorder2(TreeNode root){
TreeNode stack[]=new TreeNode[13];
int top=0;
do{
while(root!=null){
System.out.print(root.data+" ");
top++;
stack[top]=root;
root=root.leftChild;
}
if(top!=0){
root=stack[top];
top--;
root=root.rightChild;
}
}while(top!=0||root!=null);
}
//求树的深度的递归算法
static int depth(TreeNode root){
int m,n;
if(root==null) return 0;
else{
m=depth(root.leftChild);
n=depth(root.rightChild);
return (m>n?m:n)+1;
}
}
//求树中以值为x的节点为根的子树深度
static void Subdepth(TreeNode root,String x){
if(root.data==x)
System.out.println(depth(root));
else{
if(root.leftChild!=null)
Subdepth(root.leftChild,x);
if(root.rightChild!=null)
Subdepth(root.rightChild,x);
}
}
//在二叉树root中求值为ch的结点所在的层数
static int floor(TreeNode root,String ch){
int lev,m,n;
if(root==null)
lev=0;
else if(root.data==ch)
lev=1;
else{
m=floor(root.leftChild,ch);
n=floor(root.rightChild,ch);
if(m==0&&n==0) lev=0;
else lev=((m>n)?m:n)+1;
}
return (lev);
}
//求树的叶子数
static int countleaf(TreeNode root){
int i;
if(root==null)
i=0;
else if((root.leftChild==null)&&(root.rightChild==null))
i=1;
else i=countleaf(root.leftChild)+countleaf(root.rightChild);
return (i);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
BinaryTree tree1=create();
System.out.println("对从1到12按层次顺序建立的二叉树先序遍历的结果为：");
preorder(tree1.root);
System.out.println();
System.out.println("二叉树的非递归先序遍历的结果为：");
preorder2(tree1.root);
System.out.println();
System.out.println("中序遍历的结果为：");
inorder(tree1.root);
System.out.println();
System.out.println("后序遍历的结果为：");
postorder(tree1.root);
System.out.println();
System.out.println("层次遍历的结果为：");
levelorder(tree1.root);
System.out.println();
System.out.println("该树的深度为："+depth(tree1.root));
System.out.println("值为3的结点为根的子树的深度为：");
Subdepth(tree1.root,"3");
System.out.println("值为3的结点所在的层数为："+floor(tree1.root,"3"));
System.out.println("此树的叶子数为："+countleaf(tree1.root));
}
}