Chinaunix首页 | 论坛 | 博客
  • 博客访问: 3223040
  • 博文数量: 269
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1988
  • 用 户 组: 普通用户
  • 注册时间: 2019-10-28 13:40
文章分类

全部博文(269)

文章存档

2022年(42)

2021年(155)

2020年(50)

2019年(22)

我的朋友

分类: Java

2020-04-30 14:14:50

二叉树概念:
java二叉树的每个根节点最多有两颗字数,不存在子树大于2的节点,也就是说,二叉树是节点的最大度数为2的树,通常子树分为左子树和右子树,次序不能颠倒。
创建二叉树:
public void createTree(Object[] objs) {
datas = new ArrayList();
for (Object object : objs) {
datas.add(new BinTree(object));
}
root = datas.get(0);// 将第一个作为根节点
for (int i = 0; i < objs.length / 2; i++) {
datas.get(i).leftNode = datas.get(i * 2 + 1);
if (i * 2 + 2 < datas.size()) {// 避免偶数的时候 下标越界
datas.get(i).rightNode = datas.get(i * 2 + 2);
}
}
}
 
二叉树的遍历有三种:
先序遍历:
访问根节点 
按先序遍历访问左子树   
按先序遍历访问右子树
    // 先序遍历
public void preorder(BinTree root) {
if (root != null) {
visit(root.getData());
preorder(root.leftNode);
preorder(root.rightNode);
}
 
}
 


中序遍历:
按中序遍历左子树
访问根节点
按中序遍历访问右子树
// 中序遍历
public void inorder(BinTree root) {
if (root != null) {
inorder(root.leftNode);
visit(root.getData());
inorder(root.rightNode);
}
 
}
后序遍历:
按后序遍历访问左子树
按后序遍历访问右子树
访问根节点
// 人名币符号
// 后序遍历
public void afterorder(BinTree root) {
if (root != null) {
afterorder(root.leftNode);
afterorder(root.rightNode);
visit(root.getData());
}
 
}
运行代码:
public static void main(String[] args) {
Integer[] test = new Integer[] { 3, 1, 0, 2, 7, 5, 8, 9, 6 };
BinTree tree = new BinTree();
tree.createTree(test);
System.out.println("前序遍历:");
tree.preorder(tree.getRoot());
System.out.println();
System.out.println("中序遍历:");
tree.inorder(tree.getRoot());
System.out.println();
System.out.println("后序遍历:");
tree.afterorder(tree.getRoot());
 
}
阅读(1323) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~