二叉树的创建和四种遍历(前序、先序、后序、层次、结点的层数、深度、叶子数等)—java描述

时间:2023-01-09 08:21:02

二叉树的创建和四种遍历(前序、先序、后序、层次、结点的层数、深度、叶子数等)—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==nullreturn 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));

}

 

}