写出二叉树的先序遍历、中序遍历、后序遍历。

不会的别乱写了。我可不是一点都不懂的

2024-11-15 13:12:47

推荐回答（1个）

回答1：

//二叉树的节点结构
class TreeNode {
int Id=0;
String data=null;
boolean isVisted=false;
TreeNode leftChild=null;
TreeNode rightChild=null;
public TreeNode(){}
public TreeNode(int Id,String data){
this.Id=Id;
this.data=data;
this.leftChild=null;
this.rightChild=null;
}
}

[java] view plain copy

[java] view plain copy
import java.util.Stack;
public class firstBinaryTree {
private TreeNode root=null;
//构造方法
public firstBinaryTree(){
root=new TreeNode(1,"rootNode");
}
//创建二叉树
protected void createBT(TreeNode root){
TreeNode NodeB= new TreeNode(2,"B");
TreeNode NodeC= new TreeNode(3,"C");
TreeNode NodeD= new TreeNode(4,"D");
TreeNode NodeE= new TreeNode(5,"E");
TreeNode NodeF= new TreeNode(6,"F");
TreeNode NodeG= new TreeNode(7,"G");
TreeNode NodeH= new TreeNode(8,"H");
TreeNode NodeI= new TreeNode(9,"I");
root.leftChild=NodeB;
root.rightChild=NodeC;
NodeB.leftChild=NodeD;
NodeB.rightChild=NodeE;
NodeC.leftChild=NodeF;
NodeC.rightChild=NodeG;
NodeD.leftChild=NodeH;
NodeE.rightChild=NodeI;
}
//判断为空
public boolean isEmpty(){
return root==null;
}
//前序非递归遍历
private void preOrederNotR(TreeNode p){
Stack stack = new Stack();
TreeNode node=p;
while(node!=null || stack.size()>0){
while(node!=null){
visted(node);
stack.push(node);
node=node.leftChild;
}
if(stack.size()>0){
node=stack.peek();
node=node.rightChild;
stack.pop();
}
}
}
//中序非递归遍历
private void inOrederNotR(TreeNode p){
Stack stack = new Stack();
TreeNode node=p;
while(node!=null || stack.size()>0){
while(node!=null){
stack.push(node);
node=node.leftChild;
}
if(stack.size()>0){
node=stack.pop();
visted(node);
node=node.rightChild;
}
}
}
//后序非递归遍历
private void lastOrederNotR(TreeNode p){
Stack stack = new Stack();
TreeNode node=p;
while(p!=null){
//左子树入栈
while(p.leftChild!=null){
stack.push(p);
p=p.leftChild;
}
//当前结点无右子树或右子树已经输出
while(p.rightChild==null||p.rightChild==node){
visted(p);
node =p; //记录上一个已输出结点
if(stack.empty())
return;
p=stack.pop();
}
//右子树进栈
stack.push(p);
p=p.rightChild;
}
}
//前序遍历
private void preOrder(TreeNode subTree) {
// TODO Auto-generated method stub
if(subTree!=null){
visted(subTree);
preOrder(subTree.leftChild);
preOrder(subTree.rightChild);
}
}
//中序遍历
private void inOrder(TreeNode subTree) {
// TODO Auto-generated method stub
if(subTree!=null){
inOrder(subTree.leftChild);
visted(subTree);
inOrder(subTree.rightChild);
}
}
//后序遍历
private void lastOrder(TreeNode subTree) {
// TODO Auto-generated method stub
if(subTree!=null){
lastOrder(subTree.leftChild);
lastOrder(subTree.rightChild);
visted(subTree);
}
}
//访问该节点
private void visted(TreeNode subTree) {
// TODO Auto-generated method stub
subTree.isVisted=true;
System.out.println("ID:"+subTree.Id+"name:"+subTree.data);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
firstBinaryTree bt= new firstBinaryTree();
bt.createBT(bt.root);
bt.preOrder(bt.root);
bt.preOrederNotR(bt.root);
System.out.println("------------------------------");
bt.inOrder(bt.root);
bt.inOrederNotR(bt.root);
System.out.println("--------------------------------");
bt.lastOrder(bt.root);
bt.lastOrederNotR(bt.root);
}
}