Java中二叉树数据结构的实现示例
来看一个具体的习题实践：
题目
根据二叉树前序遍历序列例如：7,-7,8,#,#,-3,6,#,9,#,#,#,-5,#,#，构建二叉树，并且用前序、中序、后序进行遍历
代码
importjava.util.Scanner;
publicclassBinaryTree{
publicstaticString[]str;
publicstaticintcount;
/**
*静态内部类，定义二叉树节点
*/
staticclassTreeNode{
publicStringdata;
TreeNodelchild;
TreeNoderchild;
publicTreeNode(Stringx){
this.data=x;
}
}
/**
*根据前序序列递归构建二叉树
*
*@return
*/
publicstaticTreeNodecreateBtree(){
TreeNoderoot=null;
if(count>=str.length||str[count++].equals("#")){
root=null;
}else{
root=newTreeNode(str[count-1]);
root.lchild=createBtree();
root.rchild=createBtree();
}
returnroot;
}
/**
*前序遍历
*
*@paramroot
*/
publicstaticvoidpreTraverse(TreeNoderoot){
if(root!=null){
System.out.print(root.data+"");
preTraverse(root.lchild);
preTraverse(root.rchild);
}
}
/**
*中序遍历
*
*@paramroot
*/
publicstaticvoidinTraverse(TreeNoderoot){
if(root!=null){
inTraverse(root.lchild);
System.out.print(root.data+"");
inTraverse(root.rchild);
}
}
/**
*后序遍历
*
*@paramroot
*/
publicstaticvoidpostTraverse(TreeNoderoot){
if(root!=null){
postTraverse(root.lchild);
postTraverse(root.rchild);
System.out.print(root.data+"");
}
}
publicstaticvoidmain(Stringargs[]){
Scannercin=newScanner(System.in);
while(cin.hasNext()){
Strings=cin.nextLine();
str=s.split(",");
count=0;
TreeNoderoot=createBtree();
//前序遍历
preTraverse(root);
System.out.println();
//中序遍历
inTraverse(root);
System.out.println();
//后序遍历
postTraverse(root);
System.out.println();
}
}
}
二叉树的深度
下面是是实现二叉树的递归算法的实现，其思想就是，若为空，则其深度为0，否则，其深度等于左子树和右子树的深度的最大值加1：
classNode{
Stringname;
Nodeleft;
Noderight;
publicNode(Stringname){
this.name=name;
}
@Override
publicStringtoString(){
returnname;
}
}
//定义二叉树
classBinaryTree{
Noderoot;
publicBinaryTree(){
root=null;
}
//为了方便起见，我就直接写个初始化的二叉树，详细的可以见以前的日志
publicvoidinitTree(){
Nodenode1=newNode("a");
Nodenode2=newNode("b");
Nodenode3=newNode("c");
Nodenode4=newNode("d");
Nodenode5=newNode("e");
root=node1;
node1.left=node2;
node2.right=node3;
node1.right=node4;
node3.left=node5;
}
//求二叉树的深度
intlength(Noderoot){
intdepth1;
intdepth2;
if(root==null)return0;
//左子树的深度
depth1=length(root.right);
//右子树的深度
depth2=length(root.left);
if(depth1>depth2)
returndepth1+1;
else
returndepth2+1;
}
}
publicclassTestMatch{
publicstaticvoidmain(String[]args){
BinaryTreetree=newBinaryTree();
tree.initTree();
System.out.println(tree.length(tree.root));
}
}