6、二叉树树（java实现）
2024-08-28 01:18:24
1、创建树的节点
public class Node {
public Object data; //存储数据
public Node leftChild; //左子树指针
public Node rightChild; //右字树指针
}
2、二叉树的实现
public class BinTree {
Node node;
public BinTree() {
}
public BinTree(Node node) {
node.leftChild = node.leftChild;
node.rightChild = node.rightChild;
}
/**
* 初始化二叉树头结点
*
* @param node ：头结点
*/
public void initBinTree(Node node) {
node.leftChild = null;
node.rightChild = null;
}
/**
* 左插入节点
*
* @param curr_node
* @param element
* @return
*/
public Node insertLeftChild(Node curr_node, Object element) {
if (curr_node == null) {
return null;
}
Node newnode = new Node(); //初始化新节点
newnode.data = element;
newnode.leftChild = curr_node.leftChild; //插入新节点左子树为原子树node的左子树（---> null）
newnode.rightChild = null;
curr_node.leftChild = newnode; //转换curr_node节点为当前插入后的左子树
return curr_node.leftChild;
}
/**
* 右插入节点
*
* @param curr_node
* @param element
* @return
*/
public Node insertRightChild(Node curr_node, Object element) {
if (curr_node == null) {
return null;
}
Node saveNode = curr_node.rightChild;
Node newNode = new Node();
newNode.data = element;
newNode.rightChild = newNode;
newNode.rightChild = null;
curr_node.rightChild = newNode;
return curr_node.rightChild;
}
/**
* 删除左子树
*
* @param currNode
* @return
*/
public Node deleteLeftChild(Node currNode) {
if (currNode == null || currNode.leftChild == null) {
return null;
}
currNode.leftChild = null;
return currNode;
}
/**
* 删除右节点
*
* @param currNode
* @return
*/
public Node deleteRightChild(Node currNode) {
if (currNode == null || currNode.rightChild == null) {
return null;
}
currNode.rightChild = null;
return currNode;
}
/**
* 前序遍历
*
* @param root
*/
public void preOrder(Node root) {
if (root != null) {
System.out.print(root.data + " ");
preOrder(root.leftChild);
preOrder(root.rightChild);
}
}
/**
* 中序遍历
*
* @param root
*/
public void inOrder(Node root) {
if (root != null) {
inOrder(root.leftChild);
System.out.print(root.data + " ");
inOrder(root.rightChild);
}
}
/**
* 后序遍历
*
* @param root
*/
public void postOrder(Node root) {
if (root != null) {
postOrder(root.leftChild);
postOrder(root.rightChild);
System.out.print(root.data + " ");
}
}
/**
* 打印二叉树
*
* @param root
* @param n
*/
public void printf(Node root, int n) {
if (root == null) { //为空判断
return;
}
printf(root.rightChild, n + 1); //遍历打印右子树
for (int i = 0; i < n - 1; i++) {
System.out.print("\t");
}
if (n > 0) {
System.out.println("----" + root.data);
}
printf(root.leftChild, n + 1);
}
/**
* 二叉树查找元素
* @param root
* @param x
* @return
*/
public Node search(Node root, Object x) {
Node findNode = null; //找到就返回该节点指针，找不到就返回空
if (root != null) {
if (root.data == x) {
findNode = root;
} else {
findNode = search(root.leftChild, x);
if (findNode == null) {
findNode = search(root.rightChild, x);
}
}
}
return findNode;
}
public static void main(String[] args) {
Node root = new Node();
root.leftChild = null;
root.rightChild = null;
BinTree binTree = new BinTree();
Node p = null;
p = binTree.insertLeftChild(root, 'A');
p = binTree.insertLeftChild(p, 'B');
p = binTree.insertLeftChild(p, 'D');
p = binTree.insertRightChild(p, 'G');
p = binTree.insertRightChild(root.leftChild, 'C');
binTree.insertLeftChild(p, 'E');
binTree.insertRightChild(p, 'F');
binTree.printf(root, 0);
System.out.print("前序遍历 ");
binTree.preOrder(root.leftChild);
System.out.println();
System.out.print("中序遍历 ");
binTree.inOrder(root.leftChild);
System.out.println();
System.out.print("后序遍历 ");
binTree.postOrder(root.leftChild);
System.out.println();
Node findNode = binTree.search(root,'E');
if (findNode == null){
System.out.println("没有找到E");
}else{
System.out.println("元素E在二叉树中");
}
System.out.println("删除元素E");
binTree.deleteLeftChild(p);
Node findE = binTree.search(root,'E');
if (findE == null){
System.out.println("没有找到E");
}else{
System.out.println("元素E在二叉树中");
}
}
}
3、实现结果
----F
----C
----E
----A
----B
----G
----D
前序遍历 A B D G C E F
中序遍历 D G B A E C F
后序遍历 G D B E F C A
元素E在二叉树中
删除元素E
没有找到E
最新文章
- 输入一个数组，求最小的K个数
- Java反射机制<1>
- js null和undefined
- hdu 4288 线段树 暴力 **
- linux 修改端口限制
- mysql由于外键关联无法删除数据
- 搜索和搜索形式（SEARCHING and its forms）
- JavaScript基础——变量、语句、注释
- 性能测试常用sql技巧_Oracle
- Android 主题theme说明 摘记
- 入门-什么是webshell？
- Java高级工程师进阶路线
- 个人笔记之json实现模糊查询
- Python系列之 - 上下文管理协议
- Hadoop源码分析(3): Hadoop的运行痕迹
- 解决SpringMVC中文乱码问题 -----这是服务器返回参数到前端中文乱码
- Perl正则表达式引用
- getQueryStringByName url参数/
- JAVA记录-SpringMVC scope属性的两种模式
- ctsc2018