java二叉排序树
2024-09-24 01:05:52
二叉排序树又称二叉查找树。它或者是一颗空树，或者是具有如下性质的二叉树：
1.如果左子树不空，那么左子树上的所有节点均小于它的根节点的值；
2.如果右子树不空，那么右子树上的所有节点均大于它的根节点的值；
3.左右字树也分别是二叉排序树。
关于二叉排序树的建立和遍历的代码实现如下：
class Node{
public int data;
public Node left;
public Node right;
public Node(int data){
this.data = data;
this.left = null;
this.right = null;
}
}
public class BinaryTree{
private Node root;
public BinaryTree(){
root = null;
}
//将date插入到排序二叉树中
public void insert(int data){
Node newNode = new Node(data);
if(root == null)
root = newNode;
else{
Node current = root;
Node parent;
while (true) { //寻找插入的位置
parent = current;
if(data < current.data){
current = current.left;
if(current == null){
parent.left = newNode;
return;
}
}
else{
current = current.right;
if(current == null){
parent.right = newNode;
return;
}
}
}
}
}
//输入数值，构建二叉树
public void buildTree(int[] data){
for (int i = 0; i<data.length; i++) {
insert(data[i]);
}
}
//中序遍历方法递归实现
public void inOrder(Node localRoot){
if (localRoot != null) {
inOrder(localRoot.left);
System.out.print(localRoot.data + " ");
inOrder(localRoot.right);
}
}
public void inOrder(){
this.inOrder(this.root);
}
//先序遍历方法递归实现
public void preOrder(Node localRoot){
if (localRoot != null) {
System.out.print(localRoot.data + " ");
preOrder(localRoot.left);
preOrder(localRoot.right);
}
}
public void preOrder(){
this.preOrder(this.root);
}
//后序遍历方法递归实现
public void postOrder(Node localRoot){
if (localRoot != null) {
postOrder(localRoot.left);
postOrder(localRoot.right);
System.out.print(localRoot.data + " ");
}
}
public void postOrder(){
this.postOrder(this.root);
}
//层次遍历（利用一个队列实现）
public static void levelOrder(Node localRoot){
if(localRoot == null)
return;
List<Node> queue = new LinkedList<Node>();
queue.add(localRoot);
while(!queue.isEmpty()){
Node temp = queue.poll(0);
System.out.print(temp.data + " ");
if(temp.left != null){
queue.add(temp.left);
}
if(temp.right != null){
queue.add(temp.right);
}
}
System.out.println();
}
public void levelOrder(){
this.levelOrder(this.root);
}
}
最新文章
- PHP笔记（PHP初级篇）
- sqlplus链接数据库报ORA-09925: Unable to create audit trail file
- < 独立项目 - 文本挖掘 > - 2016/10/25 第一更 - <Linux相关知识准备>
- MySQL双机热备份
- QQ第三方登录
- sqlplus 配置方法及相关命令
- iOS开发项目之三 [ 自定义tabBarCtrl]
- button的相关属性
- POJ 2455 Secret Milking Machine (二分 + 最大流)
- table指定位置添加行
- 详解Google Chrome浏览器（操作篇）（一）
- How do I get the lowest value of all the non zero value pixels?
- APICloud ajpush(极光推送) 6009
- 聚焦“云开发圆桌论坛”，大前端Serverless大佬们释放了这些讯号！
- [树莓派]启用root账户
- 自定义PlantUML和C4 Model样式
- Inno Setup 系列之先卸载之后再安装
- flask框架1
- c#中WMI 中的日期和时间转为本地时间
- JavaScript学习总结(十九)——使用js加载器动态加载外部Javascript文件