目录
一、用接口实现二叉树的抽象数据类型
二、辅助类
栈（自己编辑的）
队列（自己编辑的）
ArrayList（JavaAPI的）
三、实现二叉树+先序遍历+中序遍历+后序遍历+用栈实现先序遍历+用栈实现中序遍历+用栈实现后序遍历+层次遍历+用队列实现层次遍历+用中序遍历和先序遍历确认二叉树
三、测试结果
一、用接口实现二叉树的抽象数据类型
import java.util.List;
public interface BinNode {
public Object getElement(); // 返回结点元素
public void setElement(Object ob); // 设置结点元素
public BinNode getLeft(); // 返回左孩子
public void setLeft(BinNode leftnode);// 设置左孩子
public BinNode getRight(); // 返回右孩子
public void setRight(BinNode rightnode); // 设置右孩子
public boolean isLeaf(); // 判断是否叶子结点
public void preordertraversal(BinNode root);// 先序遍历
public void preordertraversalwithStack(BinNode root);//栈实现非递归先序遍历
public void inordertraversal(BinNode node);// 中序遍历
public void inordertraversalwithStack(BinNode root);//栈实现非递归中序遍历
public void postordertraversal(BinNode node);// 后序遍历
public void postordertraversalwithStack(BinNode root);//栈实现非递归后续遍历
public void leveltraversalwithQueue(BinNode root);// 用队列实现层次遍历
// 用先序遍历和中序遍历序列创建二叉树。
public BinNodeImpl createBinTreebyPreandInOrder(List pre,List in);
}
二、辅助类
栈（自己编辑的）
// 把索引为0的位置作为栈尾,即栈中所有数据都是有效数据，属于不带头结点，即没有一个无效数据点
// 对于顺序栈而言，不会有线性表的插入删除操作需要花费O(n)的时间复杂度的问题，因为只会在栈顶插入
public class SStackwithoutHead implements SequentialStack{
private final static int DEFAULTSIZE = 10;
private int size; // 栈容量
private Object[] stack;
private int topIndex; // 栈顶位置，从0索引，同时topIndex+1表示栈大小
public SStackwithoutHead() {
setup(DEFAULTSIZE);
}
public SStackwithoutHead(int size) {
setup(size);
}
@Override
public void setup(int sz) { // 初始化链式表
size = sz;
topIndex = -1; // 不带头结点，所以初始化为topIndex为-1
stack = new Object[sz];
}
@Override
public void push(Object ob) {
if(topIndex
队列（自己编辑的）
// 带头结点的队列
// 这里用头结点来避免逻辑循环数组中队满和队空问题
public class SQueuewithHead implements SequentialQueue{
private static final int DEFAULTSIZE = 4;
private int front;// 队首
private int rear;// 队尾
private int size;// 队列容量
private Object listArray[];// 队列
public SQueuewithHead() {
setup(DEFAULTSIZE);
}
public SQueuewithHead(int sz) {
setup(sz);
}
@Override
public void setup(int sz) {
size = sz+1;// 带一个无效数据头结点
front = 0;
rear = 0;
listArray = new Object[size];
}
@Override
public void enQueue(Object ob) {
// 增加一个新元素到队尾,
// 如果队尾的当前索引是size-1,即数组最后一个元素，那么下一个元素应当是在索引为0这个位置，
// 那么可以用（++rear）%size
// System.out.println(front+" t "+rear);
if(front!=(rear+2)%size)// 判断非队满
listArray[(++rear)%size] = ob;
}
@Override
public Object deQueue() {
if(!isEmpty())return listArray[(++front)%size];// 出队一个队头元素
return null;
}
@Override
public Object frontObject() {
if(!isEmpty())return listArray[(front+1)%size];// 返回一个队头元素
return null;
}
public Object rearObject() {
if(!isEmpty())return listArray[rear];// 返回一个队尾元素
return null;
}
@Override
public boolean isEmpty() {
if(front == rear) return true;
return false;
}
}
ArrayList（JavaAPI的）
三、实现二叉树+先序遍历+中序遍历+后序遍历+用栈实现先序遍历+用栈实现中序遍历+用栈实现后序遍历+层次遍历+用队列实现层次遍历+用中序遍历和先序遍历确认二叉树
import java.util.List;
import com.zyx.queue.sequentialqueue.SQueuewithHead;
import com.zyx.stack.squentialstack.SStackwithoutHead;
public class BinNodeImpl implements BinNode{
private Object element;
private BinNode left;
private BinNode right;
public BinNodeImpl() {
element = null;
left = null;
right =null;
}
public BinNodeImpl(Object ob) {
element = ob;
left = null;
right = null;
}
public BinNodeImpl(Object ob,BinNode leftnode,BinNode rightnode) {
element = ob;
left = leftnode;
right = rightnode;
}
@Override
public Object getElement() {
return element;
}
@Override
public void setElement(Object ob) {
element = ob;
}
@Override
public BinNode getLeft() {
return left;
}
@Override
public void setLeft(BinNode leftnode) {
left = leftnode;
}
@Override
public BinNode getRight() {
return right;
}
@Override
public void setRight(BinNode rightnode) {
right = rightnode;
}
@Override
public boolean isLeaf() {
return (left==null)&&(right==null);
}
public void visit(Object ob) {
System.out.print(ob);
}
// 先序遍历，先访问根，再依次遍历左子树，再遍历右子树
public void preordertraversal(BinNode root) {
if(root!=null) {
visit(root.getElement());
preordertraversal(root.getLeft());
preordertraversal(root.getRight());
}
}
//栈实现非递归先序遍历
public void preordertraversalwithStack(BinNode root){
SStackwithoutHead stack = new SStackwithoutHead();
BinNode node = root;
// 当二叉树非空，压栈二叉树，并访问当前节点，开始遍历并访问左子树
while(node!=null || !stack.isEmpty()) {
if(node!=null) {
stack.push(node);// 压栈
visit(node.getElement());// 访问当前节点
node = node.getLeft();// 开始向左遍历
}
else {//当左子树为空，出栈当前节点，并遍历右子树，如果右子树非空，压栈并访问右子树
node = (BinNode) stack.pop();
node = node.getRight();
}
}
}
// 中序遍历，先遍历左子树，访问结点，再依次遍历右子树
public void inordertraversal(BinNode node) {
if(node!=null) {
inordertraversal(node.getLeft());
visit(node.getElement());
inordertraversal(node.getRight());
}
}
// 用栈实现非递归中序遍历。
public void inordertraversalwithStack(BinNode root) {
// 新建一个栈
SStackwithoutHead stack = new SStackwithoutHead(10);
BinNode node = root;// 指向下一个可能的栈顶元素
while(node!=null || !stack.isEmpty()) {
// 当二叉树非空，压栈二叉树，优先遍历左子树，即压栈左子树
if (node!=null) {
stack.push(node); // 压栈左子树
node = node.getLeft();
}
// 当左子树为空，出栈并访问当前节点，遍历右子树，如果右子树非空，压栈右子树
else {
// 出栈并访问该节点
node = (BinNode) stack.pop();// 当左子树为空,出栈该节点
visit(node.getElement());// 访问该节点
node = node.getRight();// 遍历右子树
}
}
}
// 后续遍历，先遍历左子树，再遍历右子树，最后访问根
public void postordertraversal(BinNode node) {
if(node!=null) {
postordertraversal(node.getLeft());
postordertraversal(node.getRight());
visit(node.getElement());
}
}
// 用栈实现非递归后续遍历
// 这个比较复杂，如何在遍历到右子树为空后，然后出栈，出栈的可能是其左子树，也可能是当前节点，
// 如何保证出栈以后，不会被再次压入？
// 只要确保，四种情形出栈：一左空或右空时；二：左空右已出栈；三右空左已出栈
// 对于栈而言，同一个元素不会被入栈两次。
// 1.当结点第一次入栈时，设定其值为0，
// 2.遍历左子树，
// 3.当左子树为空或遍历结束时，将栈顶（分叉点）值设为1；
// 4.遍历右子树，
// 5.若右子树根节点非空，跳到步骤1；
// 6.若右子树为空，栈顶值一定是1，开始进行出栈操作，直道最上层的分叉点,意味着这个分叉点的左子树遍历结束，
// 7.跳转到3
public void postordertraversalwithStack(BinNode root) {
SStackwithoutHead stack1 = new SStackwithoutHead();
SStackwithoutHead stack2 = new SStackwithoutHead();
BinNode node = root;
while(node != null || !stack1.isEmpty()) {
while(node!=null) {
stack1.push(node);
stack2.push(0);
node = node.getLeft();
}
while(!stack1.isEmpty() && (int)stack2.topValue()==1) {
visit(((BinNode) stack1.pop()).getElement());
stack2.pop();
}
if(!stack1.isEmpty()) {
stack2.pop();
stack2.push(1);
node =((BinNode) stack1.topValue()).getRight();
}
}
}
// 层次遍历：从第一层开始由左向右遍历，可以用一个队列来实现，将每一层的最左边作为队头，最右边作为队尾，队头先出队
// 第一层：既是队头又是队尾，入队又出队
// 1.如果
public void leveltraversalwithQueue(BinNode root) {
BinNode node = root;
SQueuewithHead queue = new SQueuewithHead();
queue.enQueue(node);
while(!queue.isEmpty()) {
node = (BinNode) queue.deQueue();
visit(node.getElement());
if(node.getLeft()!=null) {
queue.enQueue(node.getLeft());
}
if(node.getRight()!=null) {
queue.enQueue(node.getRight());
}
}
}
public BinNodeImpl createBinTreebyPreandInOrder(List pre,List in) {
// 当中序遍历序列为空时，结束遍历
if(in.isEmpty()) {
return null;
}
// 当中序遍历序列长度为1时，返回结果。
if(in.size()==1) {
return (new BinNodeImpl(in.get(0)));
}
BinNodeImpl node=new BinNodeImpl(pre.get(0));// 获取根节点
BinNodeImpl ltemp;
BinNodeImpl rtemp;
if(in.size()>1) {
int j = 0;
// 找到中序遍历根节点，索引为j，左子树：0->j-1,右子树j+1->in.size()-1
// 先序遍历，左子树：1->j,右子树:j+1->pre.size()-1
while (in.get(j)!=pre.get(0)) {
j++;
}
ltemp = createBinTreebyPreandInOrder(pre.subList(1,j+1),in.subList(0,j));
rtemp = createBinTreebyPreandInOrder(pre.subList(j+1,pre.size()),in.subList(j+1,in.size()));
node.setLeft(ltemp);
node.setRight(rtemp);
return node;
}
return null;
}
public BinNode createBinTreebyPostandInOrder(List pre,List list) {
return (new BinNodeImpl());
}
}
三、测试结果
import java.util.ArrayList;
public class TestBinNode{
public static void main(String[] args) {
BinNodeImpl root =new BinNodeImpl('A');
root.setLeft(new BinNodeImpl('B'));
root.getLeft().setRight(new BinNodeImpl('D'));
root.setRight(new BinNodeImpl('C'));
root.getRight().setLeft(new BinNodeImpl('E'));
root.getRight().setRight(new BinNodeImpl('F'));
root.getRight().getLeft().setLeft(new BinNodeImpl('G'));
root.getRight().getRight().setLeft(new BinNodeImpl('H'));
root.getRight().getRight().setRight(new BinNodeImpl('I'));
System.out.println("n中序遍历");
root.inordertraversal(root);
System.out.println("n用栈实现非递归中序遍历");
root.inordertraversalwithStack(root);
System.out.println("n后续遍历");
root.postordertraversal(root);
System.out.println("n用栈实现非递归后序遍历");
root.postordertraversalwithStack(root);
System.out.println("n先序遍历");
root.preordertraversal(root);
System.out.println("n用栈实现非递归中序遍历");
root.preordertraversalwithStack(root);
System.out.println("n用队列实现层次遍历");
root.leveltraversalwithQueue(root);
@SuppressWarnings("rawtypes")
ArrayList pre = new ArrayList();
ArrayList in = new ArrayList();
char pres[] = {'A','B','D','C','E','G','F','H','I'};
char ins[] = {'B','D','A','G','E','C','H','F','I'};
for(char c:pres) pre.add(c);
for(char c:ins) in.add(c);
System.out.println("n用先序遍历+中序遍历，确定二叉树。");
BinNodeImpl node = (new BinNodeImpl()).createBinTreebyPreandInOrder(pre, in);
System.out.println("n先序");
root.preordertraversal(node);
System.out.println("n中续");
root.inordertraversal(node);
System.out.println("n后续");
root.postordertraversal(node);
System.out.println("n层次");
root.leveltraversalwithQueue(node);
}
}
运行结果：
中序遍历
BDAGECHFI
用栈实现非递归中序遍历
BDAGECHFI
后续遍历
DBGEHIFCA
用栈实现非递归后序遍历
DBGEHIFCA
先序遍历
ABDCEGFHI
用栈实现非递归中序遍历
ABDCEGFHI
用队列实现层次遍历
ABCDEFGHI
用先序遍历+中序遍历，确定二叉树。
先序
ABDCEGFHI
中续
BDAGECHFI
后续
DBGEHIFCA
层次
ABCDEFGHI
栈（自己编辑的）
// 把索引为0的位置作为栈尾,即栈中所有数据都是有效数据，属于不带头结点，即没有一个无效数据点
// 对于顺序栈而言，不会有线性表的插入删除操作需要花费O(n)的时间复杂度的问题，因为只会在栈顶插入
public class SStackwithoutHead implements SequentialStack{
private final static int DEFAULTSIZE = 10;
private int size; // 栈容量
private Object[] stack;
private int topIndex; // 栈顶位置，从0索引，同时topIndex+1表示栈大小
public SStackwithoutHead() {
setup(DEFAULTSIZE);
}
public SStackwithoutHead(int size) {
setup(size);
}
@Override
public void setup(int sz) { // 初始化链式表
size = sz;
topIndex = -1; // 不带头结点，所以初始化为topIndex为-1
stack = new Object[sz];
}
@Override
public void push(Object ob) {
if(topIndex
队列（自己编辑的）
// 带头结点的队列
// 这里用头结点来避免逻辑循环数组中队满和队空问题
public class SQueuewithHead implements SequentialQueue{
private static final int DEFAULTSIZE = 4;
private int front;// 队首
private int rear;// 队尾
private int size;// 队列容量
private Object listArray[];// 队列
public SQueuewithHead() {
setup(DEFAULTSIZE);
}
public SQueuewithHead(int sz) {
setup(sz);
}
@Override
public void setup(int sz) {
size = sz+1;// 带一个无效数据头结点
front = 0;
rear = 0;
listArray = new Object[size];
}
@Override
public void enQueue(Object ob) {
// 增加一个新元素到队尾,
// 如果队尾的当前索引是size-1,即数组最后一个元素，那么下一个元素应当是在索引为0这个位置，
// 那么可以用（++rear）%size
// System.out.println(front+" t "+rear);
if(front!=(rear+2)%size)// 判断非队满
listArray[(++rear)%size] = ob;
}
@Override
public Object deQueue() {
if(!isEmpty())return listArray[(++front)%size];// 出队一个队头元素
return null;
}
@Override
public Object frontObject() {
if(!isEmpty())return listArray[(front+1)%size];// 返回一个队头元素
return null;
}
public Object rearObject() {
if(!isEmpty())return listArray[rear];// 返回一个队尾元素
return null;
}
@Override
public boolean isEmpty() {
if(front == rear) return true;
return false;
}
}
ArrayList（JavaAPI的）
三、实现二叉树+先序遍历+中序遍历+后序遍历+用栈实现先序遍历+用栈实现中序遍历+用栈实现后序遍历+层次遍历+用队列实现层次遍历+用中序遍历和先序遍历确认二叉树
import java.util.List;
import com.zyx.queue.sequentialqueue.SQueuewithHead;
import com.zyx.stack.squentialstack.SStackwithoutHead;
public class BinNodeImpl implements BinNode{
private Object element;
private BinNode left;
private BinNode right;
public BinNodeImpl() {
element = null;
left = null;
right =null;
}
public BinNodeImpl(Object ob) {
element = ob;
left = null;
right = null;
}
public BinNodeImpl(Object ob,BinNode leftnode,BinNode rightnode) {
element = ob;
left = leftnode;
right = rightnode;
}
@Override
public Object getElement() {
return element;
}
@Override
public void setElement(Object ob) {
element = ob;
}
@Override
public BinNode getLeft() {
return left;
}
@Override
public void setLeft(BinNode leftnode) {
left = leftnode;
}
@Override
public BinNode getRight() {
return right;
}
@Override
public void setRight(BinNode rightnode) {
right = rightnode;
}
@Override
public boolean isLeaf() {
return (left==null)&&(right==null);
}
public void visit(Object ob) {
System.out.print(ob);
}
// 先序遍历，先访问根，再依次遍历左子树，再遍历右子树
public void preordertraversal(BinNode root) {
if(root!=null) {
visit(root.getElement());
preordertraversal(root.getLeft());
preordertraversal(root.getRight());
}
}
//栈实现非递归先序遍历
public void preordertraversalwithStack(BinNode root){
SStackwithoutHead stack = new SStackwithoutHead();
BinNode node = root;
// 当二叉树非空，压栈二叉树，并访问当前节点，开始遍历并访问左子树
while(node!=null || !stack.isEmpty()) {
if(node!=null) {
stack.push(node);// 压栈
visit(node.getElement());// 访问当前节点
node = node.getLeft();// 开始向左遍历
}
else {//当左子树为空，出栈当前节点，并遍历右子树，如果右子树非空，压栈并访问右子树
node = (BinNode) stack.pop();
node = node.getRight();
}
}
}
// 中序遍历，先遍历左子树，访问结点，再依次遍历右子树
public void inordertraversal(BinNode node) {
if(node!=null) {
inordertraversal(node.getLeft());
visit(node.getElement());
inordertraversal(node.getRight());
}
}
// 用栈实现非递归中序遍历。
public void inordertraversalwithStack(BinNode root) {
// 新建一个栈
SStackwithoutHead stack = new SStackwithoutHead(10);
BinNode node = root;// 指向下一个可能的栈顶元素
while(node!=null || !stack.isEmpty()) {
// 当二叉树非空，压栈二叉树，优先遍历左子树，即压栈左子树
if (node!=null) {
stack.push(node); // 压栈左子树
node = node.getLeft();
}
// 当左子树为空，出栈并访问当前节点，遍历右子树，如果右子树非空，压栈右子树
else {
// 出栈并访问该节点
node = (BinNode) stack.pop();// 当左子树为空,出栈该节点
visit(node.getElement());// 访问该节点
node = node.getRight();// 遍历右子树
}
}
}
// 后续遍历，先遍历左子树，再遍历右子树，最后访问根
public void postordertraversal(BinNode node) {
if(node!=null) {
postordertraversal(node.getLeft());
postordertraversal(node.getRight());
visit(node.getElement());
}
}
// 用栈实现非递归后续遍历
// 这个比较复杂，如何在遍历到右子树为空后，然后出栈，出栈的可能是其左子树，也可能是当前节点，
// 如何保证出栈以后，不会被再次压入？
// 只要确保，四种情形出栈：一左空或右空时；二：左空右已出栈；三右空左已出栈
// 对于栈而言，同一个元素不会被入栈两次。
// 1.当结点第一次入栈时，设定其值为0，
// 2.遍历左子树，
// 3.当左子树为空或遍历结束时，将栈顶（分叉点）值设为1；
// 4.遍历右子树，
// 5.若右子树根节点非空，跳到步骤1；
// 6.若右子树为空，栈顶值一定是1，开始进行出栈操作，直道最上层的分叉点,意味着这个分叉点的左子树遍历结束，
// 7.跳转到3
public void postordertraversalwithStack(BinNode root) {
SStackwithoutHead stack1 = new SStackwithoutHead();
SStackwithoutHead stack2 = new SStackwithoutHead();
BinNode node = root;
while(node != null || !stack1.isEmpty()) {
while(node!=null) {
stack1.push(node);
stack2.push(0);
node = node.getLeft();
}
while(!stack1.isEmpty() && (int)stack2.topValue()==1) {
visit(((BinNode) stack1.pop()).getElement());
stack2.pop();
}
if(!stack1.isEmpty()) {
stack2.pop();
stack2.push(1);
node =((BinNode) stack1.topValue()).getRight();
}
}
}
// 层次遍历：从第一层开始由左向右遍历，可以用一个队列来实现，将每一层的最左边作为队头，最右边作为队尾，队头先出队
// 第一层：既是队头又是队尾，入队又出队
// 1.如果
public void leveltraversalwithQueue(BinNode root) {
BinNode node = root;
SQueuewithHead queue = new SQueuewithHead();
queue.enQueue(node);
while(!queue.isEmpty()) {
node = (BinNode) queue.deQueue();
visit(node.getElement());
if(node.getLeft()!=null) {
queue.enQueue(node.getLeft());
}
if(node.getRight()!=null) {
queue.enQueue(node.getRight());
}
}
}
public BinNodeImpl createBinTreebyPreandInOrder(List pre,List in) {
// 当中序遍历序列为空时，结束遍历
if(in.isEmpty()) {
return null;
}
// 当中序遍历序列长度为1时，返回结果。
if(in.size()==1) {
return (new BinNodeImpl(in.get(0)));
}
BinNodeImpl node=new BinNodeImpl(pre.get(0));// 获取根节点
BinNodeImpl ltemp;
BinNodeImpl rtemp;
if(in.size()>1) {
int j = 0;
// 找到中序遍历根节点，索引为j，左子树：0->j-1,右子树j+1->in.size()-1
// 先序遍历，左子树：1->j,右子树:j+1->pre.size()-1
while (in.get(j)!=pre.get(0)) {
j++;
}
ltemp = createBinTreebyPreandInOrder(pre.subList(1,j+1),in.subList(0,j));
rtemp = createBinTreebyPreandInOrder(pre.subList(j+1,pre.size()),in.subList(j+1,in.size()));
node.setLeft(ltemp);
node.setRight(rtemp);
return node;
}
return null;
}
public BinNode createBinTreebyPostandInOrder(List pre,List list) {
return (new BinNodeImpl());
}
}
三、测试结果
import java.util.ArrayList;
public class TestBinNode{
public static void main(String[] args) {
BinNodeImpl root =new BinNodeImpl('A');
root.setLeft(new BinNodeImpl('B'));
root.getLeft().setRight(new BinNodeImpl('D'));
root.setRight(new BinNodeImpl('C'));
root.getRight().setLeft(new BinNodeImpl('E'));
root.getRight().setRight(new BinNodeImpl('F'));
root.getRight().getLeft().setLeft(new BinNodeImpl('G'));
root.getRight().getRight().setLeft(new BinNodeImpl('H'));
root.getRight().getRight().setRight(new BinNodeImpl('I'));
System.out.println("n中序遍历");
root.inordertraversal(root);
System.out.println("n用栈实现非递归中序遍历");
root.inordertraversalwithStack(root);
System.out.println("n后续遍历");
root.postordertraversal(root);
System.out.println("n用栈实现非递归后序遍历");
root.postordertraversalwithStack(root);
System.out.println("n先序遍历");
root.preordertraversal(root);
System.out.println("n用栈实现非递归中序遍历");
root.preordertraversalwithStack(root);
System.out.println("n用队列实现层次遍历");
root.leveltraversalwithQueue(root);
@SuppressWarnings("rawtypes")
ArrayList pre = new ArrayList();
ArrayList in = new ArrayList();
char pres[] = {'A','B','D','C','E','G','F','H','I'};
char ins[] = {'B','D','A','G','E','C','H','F','I'};
for(char c:pres) pre.add(c);
for(char c:ins) in.add(c);
System.out.println("n用先序遍历+中序遍历，确定二叉树。");
BinNodeImpl node = (new BinNodeImpl()).createBinTreebyPreandInOrder(pre, in);
System.out.println("n先序");
root.preordertraversal(node);
System.out.println("n中续");
root.inordertraversal(node);
System.out.println("n后续");
root.postordertraversal(node);
System.out.println("n层次");
root.leveltraversalwithQueue(node);
}
}
运行结果：
中序遍历
BDAGECHFI
用栈实现非递归中序遍历
BDAGECHFI
后续遍历
DBGEHIFCA
用栈实现非递归后序遍历
DBGEHIFCA
先序遍历
ABDCEGFHI
用栈实现非递归中序遍历
ABDCEGFHI
用队列实现层次遍历
ABCDEFGHI
用先序遍历+中序遍历，确定二叉树。
先序
ABDCEGFHI
中续
BDAGECHFI
后续
DBGEHIFCA
层次
ABCDEFGHI
队列（自己编辑的）
// 带头结点的队列
// 这里用头结点来避免逻辑循环数组中队满和队空问题
public class SQueuewithHead implements SequentialQueue{
private static final int DEFAULTSIZE = 4;
private int front;// 队首
private int rear;// 队尾
private int size;// 队列容量
private Object listArray[];// 队列
public SQueuewithHead() {
setup(DEFAULTSIZE);
}
public SQueuewithHead(int sz) {
setup(sz);
}
@Override
public void setup(int sz) {
size = sz+1;// 带一个无效数据头结点
front = 0;
rear = 0;
listArray = new Object[size];
}
@Override
public void enQueue(Object ob) {
// 增加一个新元素到队尾,
// 如果队尾的当前索引是size-1,即数组最后一个元素，那么下一个元素应当是在索引为0这个位置，
// 那么可以用（++rear）%size
// System.out.println(front+" t "+rear);
if(front!=(rear+2)%size)// 判断非队满
listArray[(++rear)%size] = ob;
}
@Override
public Object deQueue() {
if(!isEmpty())return listArray[(++front)%size];// 出队一个队头元素
return null;
}
@Override
public Object frontObject() {
if(!isEmpty())return listArray[(front+1)%size];// 返回一个队头元素
return null;
}
public Object rearObject() {
if(!isEmpty())return listArray[rear];// 返回一个队尾元素
return null;
}
@Override
public boolean isEmpty() {
if(front == rear) return true;
return false;
}
}
ArrayList（JavaAPI的）
三、实现二叉树+先序遍历+中序遍历+后序遍历+用栈实现先序遍历+用栈实现中序遍历+用栈实现后序遍历+层次遍历+用队列实现层次遍历+用中序遍历和先序遍历确认二叉树
import java.util.List;
import com.zyx.queue.sequentialqueue.SQueuewithHead;
import com.zyx.stack.squentialstack.SStackwithoutHead;
public class BinNodeImpl implements BinNode{
private Object element;
private BinNode left;
private BinNode right;
public BinNodeImpl() {
element = null;
left = null;
right =null;
}
public BinNodeImpl(Object ob) {
element = ob;
left = null;
right = null;
}
public BinNodeImpl(Object ob,BinNode leftnode,BinNode rightnode) {
element = ob;
left = leftnode;
right = rightnode;
}
@Override
public Object getElement() {
return element;
}
@Override
public void setElement(Object ob) {
element = ob;
}
@Override
public BinNode getLeft() {
return left;
}
@Override
public void setLeft(BinNode leftnode) {
left = leftnode;
}
@Override
public BinNode getRight() {
return right;
}
@Override
public void setRight(BinNode rightnode) {
right = rightnode;
}
@Override
public boolean isLeaf() {
return (left==null)&&(right==null);
}
public void visit(Object ob) {
System.out.print(ob);
}
// 先序遍历，先访问根，再依次遍历左子树，再遍历右子树
public void preordertraversal(BinNode root) {
if(root!=null) {
visit(root.getElement());
preordertraversal(root.getLeft());
preordertraversal(root.getRight());
}
}
//栈实现非递归先序遍历
public void preordertraversalwithStack(BinNode root){
SStackwithoutHead stack = new SStackwithoutHead();
BinNode node = root;
// 当二叉树非空，压栈二叉树，并访问当前节点，开始遍历并访问左子树
while(node!=null || !stack.isEmpty()) {
if(node!=null) {
stack.push(node);// 压栈
visit(node.getElement());// 访问当前节点
node = node.getLeft();// 开始向左遍历
}
else {//当左子树为空，出栈当前节点，并遍历右子树，如果右子树非空，压栈并访问右子树
node = (BinNode) stack.pop();
node = node.getRight();
}
}
}
// 中序遍历，先遍历左子树，访问结点，再依次遍历右子树
public void inordertraversal(BinNode node) {
if(node!=null) {
inordertraversal(node.getLeft());
visit(node.getElement());
inordertraversal(node.getRight());
}
}
// 用栈实现非递归中序遍历。
public void inordertraversalwithStack(BinNode root) {
// 新建一个栈
SStackwithoutHead stack = new SStackwithoutHead(10);
BinNode node = root;// 指向下一个可能的栈顶元素
while(node!=null || !stack.isEmpty()) {
// 当二叉树非空，压栈二叉树，优先遍历左子树，即压栈左子树
if (node!=null) {
stack.push(node); // 压栈左子树
node = node.getLeft();
}
// 当左子树为空，出栈并访问当前节点，遍历右子树，如果右子树非空，压栈右子树
else {
// 出栈并访问该节点
node = (BinNode) stack.pop();// 当左子树为空,出栈该节点
visit(node.getElement());// 访问该节点
node = node.getRight();// 遍历右子树
}
}
}
// 后续遍历，先遍历左子树，再遍历右子树，最后访问根
public void postordertraversal(BinNode node) {
if(node!=null) {
postordertraversal(node.getLeft());
postordertraversal(node.getRight());
visit(node.getElement());
}
}
// 用栈实现非递归后续遍历
// 这个比较复杂，如何在遍历到右子树为空后，然后出栈，出栈的可能是其左子树，也可能是当前节点，
// 如何保证出栈以后，不会被再次压入？
// 只要确保，四种情形出栈：一左空或右空时；二：左空右已出栈；三右空左已出栈
// 对于栈而言，同一个元素不会被入栈两次。
// 1.当结点第一次入栈时，设定其值为0，
// 2.遍历左子树，
// 3.当左子树为空或遍历结束时，将栈顶（分叉点）值设为1；
// 4.遍历右子树，
// 5.若右子树根节点非空，跳到步骤1；
// 6.若右子树为空，栈顶值一定是1，开始进行出栈操作，直道最上层的分叉点,意味着这个分叉点的左子树遍历结束，
// 7.跳转到3
public void postordertraversalwithStack(BinNode root) {
SStackwithoutHead stack1 = new SStackwithoutHead();
SStackwithoutHead stack2 = new SStackwithoutHead();
BinNode node = root;
while(node != null || !stack1.isEmpty()) {
while(node!=null) {
stack1.push(node);
stack2.push(0);
node = node.getLeft();
}
while(!stack1.isEmpty() && (int)stack2.topValue()==1) {
visit(((BinNode) stack1.pop()).getElement());
stack2.pop();
}
if(!stack1.isEmpty()) {
stack2.pop();
stack2.push(1);
node =((BinNode) stack1.topValue()).getRight();
}
}
}
// 层次遍历：从第一层开始由左向右遍历，可以用一个队列来实现，将每一层的最左边作为队头，最右边作为队尾，队头先出队
// 第一层：既是队头又是队尾，入队又出队
// 1.如果
public void leveltraversalwithQueue(BinNode root) {
BinNode node = root;
SQueuewithHead queue = new SQueuewithHead();
queue.enQueue(node);
while(!queue.isEmpty()) {
node = (BinNode) queue.deQueue();
visit(node.getElement());
if(node.getLeft()!=null) {
queue.enQueue(node.getLeft());
}
if(node.getRight()!=null) {
queue.enQueue(node.getRight());
}
}
}
public BinNodeImpl createBinTreebyPreandInOrder(List pre,List in) {
// 当中序遍历序列为空时，结束遍历
if(in.isEmpty()) {
return null;
}
// 当中序遍历序列长度为1时，返回结果。
if(in.size()==1) {
return (new BinNodeImpl(in.get(0)));
}
BinNodeImpl node=new BinNodeImpl(pre.get(0));// 获取根节点
BinNodeImpl ltemp;
BinNodeImpl rtemp;
if(in.size()>1) {
int j = 0;
// 找到中序遍历根节点，索引为j，左子树：0->j-1,右子树j+1->in.size()-1
// 先序遍历，左子树：1->j,右子树:j+1->pre.size()-1
while (in.get(j)!=pre.get(0)) {
j++;
}
ltemp = createBinTreebyPreandInOrder(pre.subList(1,j+1),in.subList(0,j));
rtemp = createBinTreebyPreandInOrder(pre.subList(j+1,pre.size()),in.subList(j+1,in.size()));
node.setLeft(ltemp);
node.setRight(rtemp);
return node;
}
return null;
}
public BinNode createBinTreebyPostandInOrder(List pre,List list) {
return (new BinNodeImpl());
}
}
三、测试结果
三、实现二叉树+先序遍历+中序遍历+后序遍历+用栈实现先序遍历+用栈实现中序遍历+用栈实现后序遍历+层次遍历+用队列实现层次遍历+用中序遍历和先序遍历确认二叉树
import java.util.List;
import com.zyx.queue.sequentialqueue.SQueuewithHead;
import com.zyx.stack.squentialstack.SStackwithoutHead;
public class BinNodeImpl implements BinNode{
private Object element;
private BinNode left;
private BinNode right;
public BinNodeImpl() {
element = null;
left = null;
right =null;
}
public BinNodeImpl(Object ob) {
element = ob;
left = null;
right = null;
}
public BinNodeImpl(Object ob,BinNode leftnode,BinNode rightnode) {
element = ob;
left = leftnode;
right = rightnode;
}
@Override
public Object getElement() {
return element;
}
@Override
public void setElement(Object ob) {
element = ob;
}
@Override
public BinNode getLeft() {
return left;
}
@Override
public void setLeft(BinNode leftnode) {
left = leftnode;
}
@Override
public BinNode getRight() {
return right;
}
@Override
public void setRight(BinNode rightnode) {
right = rightnode;
}
@Override
public boolean isLeaf() {
return (left==null)&&(right==null);
}
public void visit(Object ob) {
System.out.print(ob);
}
// 先序遍历，先访问根，再依次遍历左子树，再遍历右子树
public void preordertraversal(BinNode root) {
if(root!=null) {
visit(root.getElement());
preordertraversal(root.getLeft());
preordertraversal(root.getRight());
}
}
//栈实现非递归先序遍历
public void preordertraversalwithStack(BinNode root){
SStackwithoutHead stack = new SStackwithoutHead();
BinNode node = root;
// 当二叉树非空，压栈二叉树，并访问当前节点，开始遍历并访问左子树
while(node!=null || !stack.isEmpty()) {
if(node!=null) {
stack.push(node);// 压栈
visit(node.getElement());// 访问当前节点
node = node.getLeft();// 开始向左遍历
}
else {//当左子树为空，出栈当前节点，并遍历右子树，如果右子树非空，压栈并访问右子树
node = (BinNode) stack.pop();
node = node.getRight();
}
}
}
// 中序遍历，先遍历左子树，访问结点，再依次遍历右子树
public void inordertraversal(BinNode node) {
if(node!=null) {
inordertraversal(node.getLeft());
visit(node.getElement());
inordertraversal(node.getRight());
}
}
// 用栈实现非递归中序遍历。
public void inordertraversalwithStack(BinNode root) {
// 新建一个栈
SStackwithoutHead stack = new SStackwithoutHead(10);
BinNode node = root;// 指向下一个可能的栈顶元素
while(node!=null || !stack.isEmpty()) {
// 当二叉树非空，压栈二叉树，优先遍历左子树，即压栈左子树
if (node!=null) {
stack.push(node); // 压栈左子树
node = node.getLeft();
}
// 当左子树为空，出栈并访问当前节点，遍历右子树，如果右子树非空，压栈右子树
else {
// 出栈并访问该节点
node = (BinNode) stack.pop();// 当左子树为空,出栈该节点
visit(node.getElement());// 访问该节点
node = node.getRight();// 遍历右子树
}
}
}
// 后续遍历，先遍历左子树，再遍历右子树，最后访问根
public void postordertraversal(BinNode node) {
if(node!=null) {
postordertraversal(node.getLeft());
postordertraversal(node.getRight());
visit(node.getElement());
}
}
// 用栈实现非递归后续遍历
// 这个比较复杂，如何在遍历到右子树为空后，然后出栈，出栈的可能是其左子树，也可能是当前节点，
// 如何保证出栈以后，不会被再次压入？
// 只要确保，四种情形出栈：一左空或右空时；二：左空右已出栈；三右空左已出栈
// 对于栈而言，同一个元素不会被入栈两次。
// 1.当结点第一次入栈时，设定其值为0，
// 2.遍历左子树，
// 3.当左子树为空或遍历结束时，将栈顶（分叉点）值设为1；
// 4.遍历右子树，
// 5.若右子树根节点非空，跳到步骤1；
// 6.若右子树为空，栈顶值一定是1，开始进行出栈操作，直道最上层的分叉点,意味着这个分叉点的左子树遍历结束，
// 7.跳转到3
public void postordertraversalwithStack(BinNode root) {
SStackwithoutHead stack1 = new SStackwithoutHead();
SStackwithoutHead stack2 = new SStackwithoutHead();
BinNode node = root;
while(node != null || !stack1.isEmpty()) {
while(node!=null) {
stack1.push(node);
stack2.push(0);
node = node.getLeft();
}
while(!stack1.isEmpty() && (int)stack2.topValue()==1) {
visit(((BinNode) stack1.pop()).getElement());
stack2.pop();
}
if(!stack1.isEmpty()) {
stack2.pop();
stack2.push(1);
node =((BinNode) stack1.topValue()).getRight();
}
}
}
// 层次遍历：从第一层开始由左向右遍历，可以用一个队列来实现，将每一层的最左边作为队头，最右边作为队尾，队头先出队
// 第一层：既是队头又是队尾，入队又出队
// 1.如果
public void leveltraversalwithQueue(BinNode root) {
BinNode node = root;
SQueuewithHead queue = new SQueuewithHead();
queue.enQueue(node);
while(!queue.isEmpty()) {
node = (BinNode) queue.deQueue();
visit(node.getElement());
if(node.getLeft()!=null) {
queue.enQueue(node.getLeft());
}
if(node.getRight()!=null) {
queue.enQueue(node.getRight());
}
}
}
public BinNodeImpl createBinTreebyPreandInOrder(List pre,List in) {
// 当中序遍历序列为空时，结束遍历
if(in.isEmpty()) {
return null;
}
// 当中序遍历序列长度为1时，返回结果。
if(in.size()==1) {
return (new BinNodeImpl(in.get(0)));
}
BinNodeImpl node=new BinNodeImpl(pre.get(0));// 获取根节点
BinNodeImpl ltemp;
BinNodeImpl rtemp;
if(in.size()>1) {
int j = 0;
// 找到中序遍历根节点，索引为j，左子树：0->j-1,右子树j+1->in.size()-1
// 先序遍历，左子树：1->j,右子树:j+1->pre.size()-1
while (in.get(j)!=pre.get(0)) {
j++;
}
ltemp = createBinTreebyPreandInOrder(pre.subList(1,j+1),in.subList(0,j));
rtemp = createBinTreebyPreandInOrder(pre.subList(j+1,pre.size()),in.subList(j+1,in.size()));
node.setLeft(ltemp);
node.setRight(rtemp);
return node;
}
return null;
}
public BinNode createBinTreebyPostandInOrder(List pre,List list) {
return (new BinNodeImpl());
}
}
三、测试结果
import java.util.ArrayList;
public class TestBinNode{
public static void main(String[] args) {
BinNodeImpl root =new BinNodeImpl('A');
root.setLeft(new BinNodeImpl('B'));
root.getLeft().setRight(new BinNodeImpl('D'));
root.setRight(new BinNodeImpl('C'));
root.getRight().setLeft(new BinNodeImpl('E'));
root.getRight().setRight(new BinNodeImpl('F'));
root.getRight().getLeft().setLeft(new BinNodeImpl('G'));
root.getRight().getRight().setLeft(new BinNodeImpl('H'));
root.getRight().getRight().setRight(new BinNodeImpl('I'));
System.out.println("n中序遍历");
root.inordertraversal(root);
System.out.println("n用栈实现非递归中序遍历");
root.inordertraversalwithStack(root);
System.out.println("n后续遍历");
root.postordertraversal(root);
System.out.println("n用栈实现非递归后序遍历");
root.postordertraversalwithStack(root);
System.out.println("n先序遍历");
root.preordertraversal(root);
System.out.println("n用栈实现非递归中序遍历");
root.preordertraversalwithStack(root);
System.out.println("n用队列实现层次遍历");
root.leveltraversalwithQueue(root);
@SuppressWarnings("rawtypes")
ArrayList pre = new ArrayList();
ArrayList in = new ArrayList();
char pres[] = {'A','B','D','C','E','G','F','H','I'};
char ins[] = {'B','D','A','G','E','C','H','F','I'};
for(char c:pres) pre.add(c);
for(char c:ins) in.add(c);
System.out.println("n用先序遍历+中序遍历，确定二叉树。");
BinNodeImpl node = (new BinNodeImpl()).createBinTreebyPreandInOrder(pre, in);
System.out.println("n先序");
root.preordertraversal(node);
System.out.println("n中续");
root.inordertraversal(node);
System.out.println("n后续");
root.postordertraversal(node);
System.out.println("n层次");
root.leveltraversalwithQueue(node);
}
}
运行结果：
中序遍历
BDAGECHFI
用栈实现非递归中序遍历
BDAGECHFI
后续遍历
DBGEHIFCA
用栈实现非递归后序遍历
DBGEHIFCA
先序遍历
ABDCEGFHI
用栈实现非递归中序遍历
ABDCEGFHI
用队列实现层次遍历
ABCDEFGHI
用先序遍历+中序遍历，确定二叉树。先序
ABDCEGFHI
中续
BDAGECHFI
后续
DBGEHIFCA
层次
ABCDEFGHI
