Java数据结构之二叉树的构建与遍历
代码
本篇博客提供以下功能的代码：
-
用户输入字符序列，生成二叉树，并用二叉链表存储 二叉树的前序、中序、后序递归遍历 二叉树的前序、中序非递归遍历
二叉树结点类
public class BinaryNode<T> {
public T data;
public BinaryNode<T> left;
public BinaryNode<T> right;
public BinaryNode()
{
this.data=null;
this.left=null;
this.right=null;
}
public BinaryNode(T data)
{
this.data=data;
this.left=null;
this.right=null;
}
public BinaryNode(T data,BinaryNode<T> left,BinaryNode<T> right)
{
this.data=data;
this.left=left;
this.right=right;
}
}
二叉树实现类
public class BinaryTree<T> {
public BinaryNode<T> root;
static int i=0;
public BinaryTree(T[] arr)
{
this.root=CreateTree(arr);
System.out.println("创建成功");
}
//构造
private BinaryNode<T> CreateTree(T[] arr)
{
BinaryNode<T> p=null;
if(this.i<arr.length)
{
if(arr[this.i]!=(T)null)
{
p=new BinaryNode<T>(arr[i]);
this.i++;
p.left=CreateTree(arr);
p.right=CreateTree(arr);
}
else
{
this.i++;
}
}
return p;
}
//递归遍历
//先序遍历 根左右
public void PreOrder(BinaryNode<T> root)
{
if(root!=null)
{
System.out.println(root.data);
PreOrder(root.left);
PreOrder(root.right);
}
}
//中序遍历 左根右
public void InOrder(BinaryNode<T> root)
{
if(root!=null)
{
InOrder(root.left);
System.out.println(root.data);
InOrder(root.right);
}
}
//后序遍历 左右根
public void PostOrder(BinaryNode<T> root)
{
if(root!=null)
{
PostOrder(root.left);
PostOrder(root.right);
System.out.println(root.data);
}
}
//非递归遍历
public void preOrder(BinaryNode<T> root)
{
SeqStack<BinaryNode> st=new SeqStack<>();
BinaryNode<T> temp=root;
if(temp!=null)
st.push(temp);
while(!st.isEmpty())
{
temp=st.pop();
System.out.println(temp.data);
if(temp.right!=null)
st.push(temp.right);
if(temp.left!=null)
st.push(temp.left);
}
}
//
public void inOrder(BinaryNode<T> root)
{
SeqStack<BinaryNode> st=new SeqStack<>();
BinaryNode<T> temp=root;
while(!st.isEmpty()||temp!=null)
{
//从某节点出发边压栈边找到该结点的最左叶子结点
while(temp!=null)
{
st.push(temp);
temp=temp.left;
}
if(!st.isEmpty())
{
temp=st.pop();
System.out.println(temp.data);
temp=temp.right;
}
}
}
}
注意：本篇博客二叉树的前序、中序非递归遍历均是借助栈实现的。关于栈接口和栈的实现类在上篇博文中。请大家移步，嘻嘻嘻。
测试类
public class Test {
public static void main(String[] args)
{
String[] arr ={
"A","B","C",null,null,"D","E",null,"G",null,null,"F",null,null,null};
BinaryTree<String> tree=new BinaryTree<String>(arr);
Scanner input=new Scanner(System.in);
tree.inOrder(tree.root);
}
}