Java二叉树链表的建立及四种遍历方法
2023-09-11 14:15:13 时间
package Test;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
//二叉树树类
public class BinaryTree {
public TreeNode root; //有一个根节点
public static int index;
public TreeNode CreateBTree(char[] a) {
TreeNode root = null;
if (index==a.length ) {
index=index-1;
}
if (a[index] != '#') {
root = new TreeNode(a[index]);
index++;
root.setLChild(CreateBTree(a));
index++;
root.setRChild(CreateBTree(a));
}
return root;
}
//先序遍历
public void prevOrder(TreeNode root) {
if (root == null) {
return;
}
System.out.print(root.getData() + ",");
prevOrder(root.getLChild());
prevOrder(root.getRChild());
}
// 中序遍历
public void midOrder(TreeNode root) {
if (root == null) {
return;
}
midOrder(root.getLChild());
System.out.print(root.getData() + ",");
midOrder(root.getRChild());
}
// 后序遍历
public void postOrder(TreeNode root) {
if (root == null) {
return;
}
postOrder(root.getLChild());
postOrder(root.getRChild());
System.out.print(root.getData() + ",");
}
// 获取树大小
private int getSize(TreeNode node) {
if (node == null) {
return 0;
} else {
return 1 + getSize(node.leftChild) + getSize(node.rightChild);
}
}
/*求二叉树的高*/
public int getHeight() {
return getHeight(this.root);
}
private int getHeight(TreeNode node) {
if (node != null) { //左子树和右子树中谁大返回谁
int i = getHeight(node.leftChild);
int j = getHeight(node.rightChild);
return (i > j) ? i + 1 : j + 1;
} else {
return 0;
}
}
//获得叶子数
public int getLeaf(TreeNode node) {
if (node == null) {
return 0;
}
if (node.leftChild == null && node.rightChild == null) {
System.out.println("Leaf node: " + node.getData());
return 1;
} else {
return getLeaf(node.leftChild) + getLeaf(node.rightChild);
}
}
//获得第K层节点数
public int getNodeKNum(TreeNode node, int k) {
if (k == 1) {
if (node == null)
return 0;
System.out.println("K Node:" + node.getData());
return 1;
}
return getNodeKNum(node.getLChild(), k - 1) + getNodeKNum(node.getRChild(), k - 1);
}
//查找某个节点
public TreeNode findNode(int data) {
return findNode(this.root, data);
}
public TreeNode findNode(TreeNode node, int data) {
if (node == null) {
return null;
} else if (node.getData() == data) {
return node;
}
TreeNode leftNode = findNode(node.getLChild(), data);
if (null != leftNode)
return leftNode;
TreeNode rightNode = findNode(node.getRChild(), data);
if (null != rightNode)
return rightNode;
return null;
}
//返回某节点的父节点
public TreeNode getParent(int data) {
return getParent(this.root, data);
}
public TreeNode getParent(TreeNode node, int data) {
if (node == null)
return null;
TreeNode childL = node.getLChild();
TreeNode childR = node.getRChild();
if ((childL != null && childL.getData() == data) || childR != null && childR.getData() == data)
return node;
TreeNode parentL = getParent(node.getLChild(), data);
if (parentL != null)
return parentL;
TreeNode parentR = getParent(node.getRChild(), data);
if (parentR != null)
return parentR;
return null;
}
//层次遍历,用到队列
public void BTreeLevelOrder() {
TreeNode root = this.root;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
LinkedList<TreeNode> list = new LinkedList<TreeNode>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode pre = queue.poll();
list.add(pre);
if (pre.getLChild() != null)
queue.offer(pre.getLChild());
if (pre.getRChild() != null)
queue.offer(pre.getRChild());
}
Iterator<TreeNode> it = list.iterator();
while (it.hasNext()) {
TreeNode cur = it.next();
System.out.print(cur.getData() + ", ");
}
}
//判断一棵树是否是完全二叉树(层次遍历的变形)
public boolean isCompleteBTree() {
TreeNode root = this.root;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node == null)
break;
queue.offer(node.getLChild());
queue.offer(node.getRChild());
}
while (!queue.isEmpty()) {
TreeNode cur = queue.poll();
if (cur != null)
return false;
}
return true;
}
class TreeNode {
private TreeNode leftChild;
private TreeNode rightChild;
private char data;
public TreeNode(char data) {
this.data = data;
}
public void setLChild(TreeNode left) {
this.leftChild = left;
}
public void setRChild(TreeNode right) {
this.rightChild = right;
}
public void setData(char data) {
this.data = data;
}
public char getData() {
return this.data;
}
public TreeNode getLChild() {
return this.leftChild;
}
public TreeNode getRChild() {
return this.rightChild;
}
}
public static void main(String[] agrs) {
BinaryTree tree = new BinaryTree();
char[] a = new char[]{'A','B','D','G','#','#','H','K','#','#','#','#','C','E','#','I','L','#','#','M','#','#','F','#','J','N','#','#','#'};
// int[] a = new int[]{1,2,3,4,'#','#',5,'#','#',6,7,'#','#',8,'#','#',9,10,11,'#','#',12,'#','#','#'};
//int[] a = new int[]{1,2,3,4,'#','#',5,6,'#','#','#','#',7,8,'#',9,10,'#','#',11,'#','#',12,'#',13,14,'#','#','#'};
// 1
// / \
// 2 5
// / \ / \
// 3 4 6 #
// / \ / \ / \
// # # # # # #
// 1
// / \
// 2 9
// / \ / \
// 3 6 10 #
// / \ / \ / \
// 4 5 7 8 11 12
// / \ / \ / \ / \ / \ / \
// # # # # # # # # # # # #
tree.root = tree.CreateBTree(a);
System.out.print("前序遍历:");
tree.prevOrder(tree.root);
System.out.print("\n中序遍历:");
tree.midOrder(tree.root);
System.out.print("\n后序遍历:");
tree.postOrder(tree.root);
System.out.println();
System.out.print("层序遍历:");
tree.BTreeLevelOrder();
System.out.println();
}
}
二叉树模型图:
程序执行效果
相关文章
- [Java基础] java多线程关于消费者和生产者
- [Java基础] java的守护线程与非守护线程
- MySQL_(Java)【连接池】简单在JDBCUtils.java中创建连接池
- Java 开发环境配置--eclipse工具进行java开发
- 链表面试题Java实现【重要】
- JAVA学习(四):Java流程控制语句(顺序结构、if条件语句、switch条件语句、循环语句与跳转语句)
- Java实现 LeetCode 823 带因子的二叉树(DP)
- Java实现 LeetCode 729 我的日程安排表 I(二叉树)
- Java实现 LeetCode 671 二叉树中第二小的节点(遍历树)
- Java实现 LeetCode 236 二叉树的最近公共祖先
- Java实现 LeetCode 222 完全二叉树的节点个数
- Java实现蓝桥杯3n+1问题
- Java实现 LeetCode 145 二叉树的后序遍历
- Java实现 LeetCode 114 二叉树展开为链表
- Java实现 LeetCode 107 二叉树的层次遍历 II(二)
- java实现指数问题
- java实现第六届蓝桥杯显示二叉树
- java实现第七届蓝桥杯打靶
- Java实现 蓝桥杯 历届试题 横向打印二叉树
- Java 蓝桥杯 算法训练 字符串的展开 (JAVA语言实现)
- 【JAVA】 02-Java对象细节
- 【JAVA】MacBook安装Java环境及eclipse
- Java超类-java.lang.object
- Atitit.swift 的新特性 以及与java的对比 改进方向attilax 总结
- atitit groovy 总结java 提升效率
- paip.操作符重载的缺失 Java 的一个大缺点
- 华为OD机试 - 寻找相似单词(Java & JS & Python)
- Effective java读书札记第一条之 考虑用静态工厂方法取代构造器
- JAVA运行java程序
- 在java类中,是先执行类的构造函数还是先执行类的私有非静态变量
- Java Swing JFileChooser和JColorChooser:文件选择器和颜色选择器