第四次实验二叉树遍历_二叉树遍历实验

2020-02-27 其他范文下载本文

第四次实验二叉树遍历由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“二叉树遍历实验”。

一、二叉链表的声明.BinaryNode public cla BinaryNode //二叉树的二叉链表结点类，泛型T指//定结点的元素类型 {

public T data;

//数据域，存储数据元素

public BinaryNode left, right;

//链域，分别指向左、右孩子结点

//构造结点，参数分别指定元素和左、右孩子结点

publicBinaryNode(T data, BinaryNode left, BinaryNode right)

{ this.data = data;this.left = left;this.right = right;

}

public BinaryNode(T data)

//构造指定值的叶子结点

{ this(data, null, null);

} publicBinaryNode()

{ this(null, null, null);

}

//可声明以下方法 public String toString()

{ returnthis.data.toString();

}

public boolean equals(Object obj)

//比较两个结点值是否相等，覆盖Object

//类的equals(obj)方法

{ returnobj==this || objinstanceofBinaryNode&&this.data.equals(((BinaryNode)obj).data);

}

public booleanisLeaf()

//判断是否叶子结点

{ returnthis.left==null &&this.right==null;

} }

二、二叉树中的遍历方法的声明.BinaryTree public cla BinaryTree {

public BinaryNode root;

//根结点，结点结构为二叉链表

public BinaryTree()

//构造空二叉树

{ this.root=null;

}

public booleanisEmpty()

//判断二叉树是否空

{ returnthis.root==null;

}

//二叉树的先根、中根和后根次序遍历算法

public void preOrder()

//先根次序遍历二叉树

{ System.out.print(“先根次序遍历二叉树：

”);preOrder(root);//调用先根次序遍历二叉树的递归方法 System.out.println();

}

public void preOrder(BinaryNode p)

//先根次序遍历以p结点为根的子二叉

//递归方法

{ if(p!=null)

//若二叉树不空

{ System.out.print(p.data.toString()+“ ”);//访问当前结点

preOrder(p.left);

//按先根次序遍历当前结点的左子树，//递归调用 preOrder(p.right);

//按先根次序遍历当前结点的右子树

//递归调用

}

public String toString()

//返回先根次序遍历二叉树所有结点的描述字符串

{ returntoString(root);

}

private String toString(BinaryNode p)

//返回先根次序遍历以p为根的子树描述字

//符串，递归算法

{ if(p==null)return “”;

return p.data.toString()+“ ” + toString(p.left)+ toString(p.right);//递归调用

}

public void inOrder()

//中根次序遍历二叉树

{ System.out.print(“中根次序遍历二叉树：

”);inOrder(root);System.out.println();

}

public void inOrder(BinaryNode p)

//中根次序遍历以p结点为根的子二叉

//递归方法

{ if(p!=null)

{ inOrder(p.left);

//中根次序遍历左子树，递归调用 System.out.print(p.data.toString()+“ ”);inOrder(p.right);

//中根次序遍历右子树，递归调用

}

public void postOrder()

//后根次序遍历二叉树

{ System.out.print(“后根次序遍历二叉树：

”);postOrder(root);System.out.println();

}

public void postOrder(BinaryNode p)

//后根次序遍历以p结点为根的子二叉树，//递归方法

{ if(p!=null)

{ postOrder(p.left);postOrder(p.right);System.out.print(p.data.toString()+“ ”);

}

public BinaryTree(T[] prelist, T[] inlist)

//以先根和中根序列构造二叉树

{ this.root = create(prelist, inlist, 0, 0, prelist.length);

} //以先根和中根序列创建一棵子树，子树根结点值是prelist[preStart]，n指定子序列长度.//返回所创建子树的根结点

privateBinaryNode create(T[] prelist, T[] inlist, intpreStart, intinStart, int n)

{ System.out.print(“prelist:”);print(prelist, preStart, n);System.out.print(“，inlist:”);print(inlist, inStart, n);System.out.println();

if(n

T elem=prelist[preStart];

//根结点值 BinaryNode p=new BinaryNode(elem);

//创建叶子结点 inti=0;while(i

//在中根序列中查找根值所在位置 i++;p.left = create(prelist, inlist, preStart+1, inStart, i);

//创建左子树 p.right = create(prelist, inlist, preStart+i+1, inStart+i+1, n-1-i);//创建右子树 return p;

} private void print(T[] table, int start, int n)

{ for(inti=0;i

}

public BinaryTree(T[] prelist)

//以标明空子树的先根序列构造二叉树

{ this.root = create(prelist);

}

//以标明空子树的先根序列构造一棵子二叉树，子树的根值是prelist[i]，返回所创建子树的根结点 privateinti=0;privateBinaryNode create(T[] prelist)

{ BinaryNode p = null;if(i

{

T elem=prelist[i];i++;if(elem!=null)//不能elem!=“^”，因为T不一定是String

{

p = new BinaryNode(elem);

//创建叶子结点 p.left = create(prelist);

//创建p的左子树 p.right = create(prelist);

//创建p的右子树

}

} return p;

}

三、运行程序

.BinaryTree_make //运用二叉链表及先根和中根遍历确立并构造二叉树

public cla BinaryTree_make {

public static BinaryTree make()

//构造给定的一棵二叉树

{ BinaryTreebitree=new BinaryTree();//创建空二叉树

BinaryNodechild_f, child_d, child_b, child_c;//创建4个二叉链表域 child_d = new BinaryNode(“D”, null, new BinaryNode(“G”));child_b = new BinaryNode(“B”, child_d, null);child_f = new BinaryNode(“F”, new BinaryNode(“H”), null);child_c = new BinaryNode(“C”, new BinaryNode(“E”), child_f);bitree.root = new BinaryNode(“小唐”, child_b, child_c);//创建根结点 returnbitree;

} public static void main(String args[])

{ BinaryTreebitree = make();bitree.preOrder();

//先根次序遍历二叉树 bitree.inOrder();//中根遍历 bitree.postOrder();

//后根遍历

String[] prelist = {“A”,“B”,“D”,“G”,“C”,“E”,“F”,“H”};//采用先根中根两种遍历

String[] inlist = {“D”,“G”,“B”,“A”,“E”,“C”,“H”,“F”};

//确定一颗二叉树 BinaryTree bitree1 = new BinaryTree(prelist, inlist);

bitree1.preOrder();// 先根遍历

bitree1.inOrder();//中根遍历

bitree1.postOrder();

} }

//后根遍历