java建立二叉树，递归/非递归先序遍历，递归/非递归中序遍历，层次遍历
2024-03-31 05:15:36
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Stack; //structure of binary tree
class BiTree {
BiTree lchild;
BiTree rchild;
String data;
} public class BiTreeTest {
static Scanner scanner = new Scanner(System.in); // test case: a b c # # d e # g # # f # # #
static BiTree createBiTree(BiTree root) {
String data = scanner.next();
if (data.equals("#")) {
return null;
} else {
root = new BiTree();
root.data = data;
root.lchild = createBiTree(root.lchild);
root.rchild = createBiTree(root.rchild);
return root;
}
} // preOrder recursive traverse
static void preOrderRecur(BiTree root) {
if (root != null) {
System.out.print(root.data + " ");
preOrderRecur(root.lchild);
preOrderRecur(root.rchild);
}
} // inOrder recursive traverse
static void inOrderRecur(BiTree root) {
if (root != null) {
inOrderRecur(root.lchild);
System.out.print(root.data + " ");
inOrderRecur(root.rchild);
}
} // preOrder in non-recursive
static void preOrder(BiTree root) {
Stack<BiTree> stack = new Stack<BiTree>();
BiTree cur;
stack.push(root);
while (!stack.empty()) {
while ((cur = stack.peek()) != null) {
System.out.print(cur.data + " ");
stack.push(cur.lchild);
}
cur = stack.pop();
if (!stack.empty() && (cur = stack.pop()) != null) {
stack.push(cur.rchild);
}
}
} // inOrder in non-recursive
static void inOrder(BiTree root) {
Stack<BiTree> stack = new Stack<BiTree>();
BiTree cur;
stack.push(root);
while (!stack.empty()) {
while ((cur = stack.peek()) != null) {
stack.push(cur.lchild);
}
stack.pop();
if (!stack.empty() && (cur = stack.pop()) != null) {
System.out.print(cur.data + " ");
stack.push(cur.rchild);
}
}
} // level traverse,use LinkedList instead of queue data structure
static void levelTraverse(BiTree root) {
LinkedList<BiTree> list = new LinkedList<BiTree>();
BiTree cur;
list.add(root);
while (list.size() != 0) {
cur = list.removeFirst();
if (cur != null) {
System.out.print(cur.data + " ");
}
if (cur.lchild != null) {
list.add(cur.lchild);
}
if (cur.rchild != null) {
list.add(cur.rchild);
}
}
} public static void main(String[] args) {
BiTree root = null;
root = createBiTree(root);
// preOrderRecur(root);
// inOrderRecur(root);
// inOrder(root);
levelTraverse(root);
}
}
最新文章
- Tomcat一个BUG造成CLOSE_WAIT
- Android Studio vs. Eclipse ADT Comparison
- linux一些常用配置
- 海量IT资料 + 各种平台下的Oracle安装文件 + 公开课录像 + 各种视频教程资料
- Intellij IDEA @Override 标红
- 数列F[19] + F[13]的值
- 制作东皇3.2的安装U盘-黑苹果之路
- [旧博客]Python 第一天总结
- Oracle 搜集统计信息
- JAVA中，JSON MAP LIST的相互转换
- Android Dependencies小差号引起的问题
- android-将系统和应用程序级的屏幕亮度
- Python自然语言处理学习笔记之选择正确的特征（错误分析 error analysis）
- Ngnix技术研究系列1-通过应用场景看Nginx的反向代理
- IIS ApplicationPoolIdentity(配置IIS讀寫網站文件)
- git rebase 合并多次提交.
- Js中常用知识点（typeof、instanceof、动态属性、变量作用域）
- windows环境下wamp安装redis拓展
- BZOJ1001 [BeiJing2006]狼抓兔子 最小割 对偶图 最短路
- 20165306 预备作业3 Linux安装及学习