简单的排序二叉树
package com.wz.util.tree;
import java.util.ArrayList;
import java.util.Iterator;
/**
* 排序二叉树
*
* @author NumbCoder
*
*/
// 节点
class BinaryNode {
private int data;
BinaryNode lChild;
BinaryNode rChild;
BinaryNode(int t) {
setData(t);
lChild = null;
rChild = null;
}
// 是否为叶子节点
public boolean isLeaf() {
if (lChild == null && rChild == null)
return true;
else
return false;
}
public void setData(int data) {
this.data = data;
}
public int getData() {
return data;
}
}
// 树
public class BinaryTree {
private BinaryNode root;
BinaryTree(BinaryNode root) {
this.root = root;
root.lChild = null;
root.rChild = null;
}
// 向二叉树中插入一个节点
public void insert(BinaryNode n) {
// 树是空的
if (root == null)
root = n;
else {
BinaryNode current = root;
BinaryNode parentNode;
boolean flag = true;
while (flag) {
parentNode = current;
if (n.getData() > current.getData()) {
// 要插入的节点为右孩子节点
current = current.rChild;
if (current == null) {
parentNode.rChild = n;
flag = false;
}
} else if (n.getData() < current.getData()) {
current = current.lChild;
// 要插入的节点为左孩子节点
if (current == null) {
parentNode.lChild = n;
flag = false;
}
}
}
}
}
// 传入一个裝有节点的ArrayList便可自动生成一棵排序二叉树
public void creatBinaryTree(BinaryNode root, ArrayList<BinaryNode> aList) {
Iterator<BinaryNode> it = aList.iterator();
while (it.hasNext()) {
insert(it.next());
}
}
// 先序遍历
public void preOrder(BinaryNode t) {
if (t != null) {
System.out.println(t.getData());
preOrder(t.lChild);
preOrder(t.rChild);
}
}
// 中序遍历
public void inOrder(BinaryNode t) {
if (t != null) {
inOrder(t.lChild);
System.out.println(t.getData());
inOrder(t.rChild);
}
}
// 后序遍历
public void postOrder(BinaryNode t) {
if (t != null) {
postOrder(t.lChild);
postOrder(t.rChild);
System.out.println(t.getData());
}
}
}
泛型的排序二叉树(因为是排序的,所以节点必须具有可比性,但具体的比较规则自己定)
package com.wz.util;
import java.util.ArrayList;
import java.util.Iterator;
/**
* 带泛型的排序二叉树
*
* @author NumbCoder
*
*/
class BinaryNode<T> implements Comparable<T> {
private T data;
BinaryNode<T> lChild;
BinaryNode<T> rChild;
BinaryNode(T t) {
setData(t);
lChild = null;
rChild = null;
}
/**
* 根据T的类型自定义比较方法小于、等于或大于n分别返回负-1、0或1
* 必须实现具体compareTo方法
*/
@Override
public int compareTo(T t) {
return 0;
}
public void setData(T data) {
this.data = data;
}
public T getData() {
return data;
}
//是否为叶子节点
public boolean isLeaf() {
if (lChild == null && rChild == null)
return true;
else
return false;
}
}
//树
public class BinaryTree<T> {
private BinaryNode<T> root;
BinaryTree(BinaryNode<T> root) {
this.root = root;
root.lChild = null;
root.rChild = null;
}
// 向二叉树中插入一个节点
public void insert(BinaryNode<T> n) {
// 树是空的
if (root == null)
root = n;
else {
BinaryNode<T> current = root;
BinaryNode<T> parentNode;
boolean flag = true;
while (flag) {
parentNode = current;
if (n.compareTo(current.getData()) == 1) {
// 要插入的节点为右孩子节点
current = current.rChild;
if (current == null) {
parentNode.rChild = n;
flag = false;
}
} else if( n.compareTo(current.getData()) == -1){
current = current.lChild;
// 要插入的节点为左孩子节点
if (current == null) {
parentNode.lChild = n;
flag = false;
}
}
}
}
}
// 生成一棵排序二叉树
public void creatBinaryTree(BinaryNode<T> root,
ArrayList<BinaryNode<T>> aList) {
Iterator<BinaryNode<T>> it = aList.iterator();
while (it.hasNext()) {
insert(it.next());
}
}
// 先序遍历
private void preOrder(BinaryNode<T> t, ArrayList<T> list) {
if (t != null) {
list.add(t.getData());
preOrder(t.lChild, list);
preOrder(t.rChild, list);
}
}
public Iterator<T> itPreOrder() {
ArrayList<T> list = new ArrayList<T>();
preOrder(root, list);
return list.iterator();
}
// 中序遍历
private void inOrder(BinaryNode<T> t, ArrayList<T> list) {
if (t != null) {
inOrder(t.lChild, list);
list.add(t.getData());
inOrder(t.rChild, list);
}
}
public Iterator<T> itInOrder() {
ArrayList<T> list = new ArrayList<T>();
inOrder(root, list);
return list.iterator();
}
// 后序遍历
private void postOrder(BinaryNode<T> t, ArrayList<T> list) {
if (t != null) {
postOrder(t.lChild, list);
postOrder(t.rChild, list);
list.add(t.getData());
}
}
public Iterator<T> itPostOrder() {
ArrayList<T> list = new ArrayList<T>();
postOrder(root, list);
return list.iterator();
}
}
分享到:
相关推荐
java基础笔记数据结构-排序二叉树,详细描述了排序二叉树的原理及其实现方式,基础数据结构。
java基础笔记数据结构-二叉树,详细描述了二叉树的原理及其实现方式,基础数据结构。
java数据结构面试题-数据结构试题全文共4页,当前为第1页。java数据结构面试题-数据结构试题全文共4页,当前为第1页。《java数据结构面试题 数据结构试题》 java数据结构面试题-数据结构试题全文共4页,当前为第1页...
Java版的源码,可应用于数据结构的课程设计,非常完美的源码
Java基础复习笔记08数据结构-二叉树和二叉树的遍历。
使用教程:http://blog.csdn.net/z740852294/article/details/78250911
广工数据结构课程设计大作业-平衡二叉树-Java实现(数据结构期末)
【数据结构(Java)】树 - 二叉树(csdn)————程序
java实现二叉树数据结构,简单明了,免费下载
编程实现如下功能: 1、假设二叉树的结点值是字符...2、对二叉树进行先根、中根和后根遍历操作,并输出遍历序列,同时观察输出序列是否与逻辑上的序列一致。 3、统计二叉树的结点个数和叶子结点个数,并分别输出其值。
Java基础复习笔记10数据结构-排序二叉树。
java数据结构二叉树的打印,通过队列,栈等,最后前序中序后序和层次四种遍历。。。
java 数据结构 完美的 java 数据结构 二叉树
数据结构二叉树专题java代码实现
包括 add delete find 等方法,适用于搞java/android开发的同学学习和了解二叉树的结构以及实现。
java实现数据结构二叉树
内容涵盖二叉树的各种操作 包括新建二叉树后以多种方式输出 插入结点 删除结点等等
数据结构java树与二叉树PPT课件.pptx
算法与数据结构它们分别涵盖了以下主要内容: 数据结构(Data Structures): 逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树)、图结构(有向图、无向图等)...