TA的每日心情 | 开心
2021-3-12 23:18 |
|---|
签到天数: 2 天 [LV.1]初来乍到
|
|
构造树如下:
其中二叉树节点类
/** 二叉树节点 */
public
class
BTNode {
private
char
key;
private
BTNode left, right;
public
BTNode(
char
key) {
this
(key,
null
,
null
);
}
public
BTNode(
char
key, BTNode left, BTNode right) {
this
.key = key;
this
.left = left;
this
.right = right;
}
public
char
getKey() {
return
key;
}
public
void
setKey(
char
key) {
this
.key = key;
}
public
BTNode getLeft() {
return
left;
}
public
void
setLeft(BTNode left) {
this
.left = left;
}
public
BTNode getRight() {
return
right;
}
public
void
setRight(BTNode right) {
this
.right = right;
}
}
遍历二叉树
/** 二叉树遍历 */
public
class
BinTree {
protected
BTNode root;
public
BinTree(BTNode root) {
this
.root = root;
}
public
BTNode getRoot() {
return
root;
}
/** 构造树 */
public
static
BTNode init() {
BTNode a =
new
BTNode("A");
BTNode b =
new
BTNode("B",
null
, a);
BTNode c =
new
BTNode("C");
BTNode d =
new
BTNode("D", b, c);
BTNode e =
new
BTNode("E");
BTNode f =
new
BTNode("F", e,
null
);
BTNode g =
new
BTNode("G",
null
, f);
BTNode h =
new
BTNode("H", d, g);
return
h;
// root
}
/** 访问节点 */
public
static
void
visit(BTNode p) {
System.out.print(p.getKey() +
" "
);
}
/** 递归实现前序遍历 */
protected
static
void
preorder(BTNode p) {
if
(p !=
null
) {
visit(p);
preorder(p.getLeft());
preorder(p.getRight());
}
}
/** 递归实现中序遍历 */
protected
static
void
inorder(BTNode p) {
if
(p !=
null
) {
inorder(p.getLeft());
visit(p);
inorder(p.getRight());
}
}
/** 递归实现后序遍历 */
protected
static
void
postorder(BTNode p) {
if
(p !=
null
) {
postorder(p.getLeft());
postorder(p.getRight());
visit(p);
}
}
/** 非递归实现前序遍历 */
protected
static
void
iterativePreorder(BTNode p) {
Stack<BTNode> stack =
new
Stack<BTNode>();
if
(p !=
null
) {
stack.push(p);
while
(!stack.empty()) {
p = stack.pop();
visit(p);
if
(p.getRight() !=
null
)
stack.push(p.getRight());
if
(p.getLeft() !=
null
)
stack.push(p.getLeft());
}
}
}
/** 非递归实现后序遍历 */
protected
static
void
iterativePostorder(BTNode p) {
BTNode q = p;
Stack<BTNode> stack =
new
Stack<BTNode>();
while
(p !=
null
) {
// 左子树入栈
for
(; p.getLeft() !=
null
; p = p.getLeft())
stack.push(p);
// 当前节点无右子或右子已经输出
while
(p !=
null
&& (p.getRight() ==
null
|| p.getRight() == q)) {
visit(p);
q = p;
// 记录上一个已输出节点
if
(stack.empty())
return
;
p = stack.pop();
}
// 处理右子
stack.push(p);
p = p.getRight();
}
}
/** 非递归实现中序遍历 */
protected
static
void
iterativeInorder(BTNode p) {
Stack<BTNode> stack =
new
Stack<BTNode>();
while
(p !=
null
) {
while
(p !=
null
) {
if
(p.getRight() !=
null
)
stack.push(p.getRight());
// 当前节点右子入栈
stack.push(p);
// 当前节点入栈
p = p.getLeft();
}
p = stack.pop();
while
(!stack.empty() && p.getRight() ==
null
) {
visit(p);
p = stack.pop();
}
visit(p);
if
(!stack.empty())
p = stack.pop();
else
p =
null
;
}
}
public
static
void
main(String[] args) {
BinTree tree =
new
BinTree(init());
System.out.print(
" Pre-Order:"
);
preorder(tree.getRoot());
System.out.println();
System.out.print(
" In-Order:"
);
inorder(tree.getRoot());
System.out.println();
System.out.print(
"Post-Order:"
);
postorder(tree.getRoot());
System.out.println();
System.out.print(
" Pre-Order:"
);
iterativePreorder(tree.getRoot());
System.out.println();
System.out.print(
" In-Order:"
);
iterativeInorder(tree.getRoot());
System.out.println();
System.out.print(
"Post-Order:"
);
iterativePostorder(tree.getRoot());
System.out.println();
}
}
输出结果
Pre-Order:H D B A C G F E
In-Order:B A D C H G E F
Post-Order:A B C D E F G H
Pre-Order:H D B A C G F E
In-Order:B A D C H G E F
Post-Order:A B C D E F G H
本文出自 “子 孑” 博客，请务必保留此出处http://zhangjunhd.blog.51cto.com/113473/82616
源码下载：http://file.javaxxz.com/2014/11/14/000831578.zip |
|
|手机版|Java学习者论坛
( 声明：本站资料整理自互联网，用于Java学习者交流学习使用，对资料版权不负任何法律责任，若有侵权请及时联系客服屏蔽删除 )
发表于 2014-11-14 00:08:31