中序线索二叉树
程序员文章站
2024-03-12 15:50:20
...
package com.datastructure.tree.binaryTree.cluebinarytree;
/**
* 线索二叉树
*/
public class ClueBinaryTree {
public static void main(String[] args) {
ClueBinaryTre clueBinaryTre = new ClueBinaryTre();
Node node1 = new Node(1);
Node node8 = new Node(8);
Node node3 = new Node(3);
Node node14 = new Node(14);
Node node10 = new Node(10);
Node node6 = new Node(6);
node1.setLeftNode(node3);
node1.setRightNlde(node6);
node3.setLeftNode(node8);
node3.setRightNlde(node10);
node6.setLeftNode(node14);
clueBinaryTre.setRoot(node1);
clueBinaryTre.clueNode();
System.out.println("10的前驱");
System.out.println(node10.getLeftNode());
System.out.println("10的后继");
System.out.println(node10.getRightNlde());
System.out.println("中序");
clueBinaryTre.middleClueBinaryTree();
}
}
//创建线索二叉树
class ClueBinaryTre{
//根节点
private Node root;
//为了实现线索话,我们需要一个指向当前节点的前驱节点
private Node pre = null;
public Node getRoot() {
return root;
}
public void setRoot(Node root) {
this.root = root;
}
//重写方法
public void clueNode(){
this.clueNode(root);
}
//对二叉树进行中序线索化的方法
public void clueNode(Node node){
if (node==null){
//节点为空,不能线索话
return;
}
//1.线索话左子树
clueNode(node.getLeftNode());
//2.线索话当前节点
if (node.getLeftNode()==null){
//让他的左指针指向前驱
node.setLeftNode(pre);
//修改当前节点的左指针类型
node.setLeftType(1);
}
//处理后继节点
if (pre!=null && pre.getRightNlde()==null){
pre.setRightNlde(node);
pre.setRightType(1);
}
//让pre永远指向node的前驱
pre = node;
//3.线索话右子树
clueNode(node.getRightNlde());
}
//中序线索二叉树的遍历
public void middleClueBinaryTree(){
//定义一个变量,用来指向当前的节点,从root开始
Node node = root;
while (node!=null){
//找到中序线索二叉树的中序的第一个数据
//也就是,第一个leftType==1的节点
while (node.getLeftType()!=1){
node = node.getLeftNode();
}
//找到之后输出
System.out.println(node);
//如果当前节点的右指针指向的是后继节点就一直输出
while (node.getRightType()==1){
node = node.getRightNlde();
System.out.println(node);
}
//如果不是指向的后继
node = node.getRightNlde();
}
}
}
//二叉树节点
class Node{
private int number;
private Node leftNode;
private Node RightNlde;
//添加两个节点类型
//如果leftType==0表示指向左子树,leftType==1表示指向前驱节点
//如果rightType==0表示指向右子树,rightType==1表示指向后继节点
private int leftType;
private int rightType;
public int getLeftType() {
return leftType;
}
public void setLeftType(int leftType) {
this.leftType = leftType;
}
public int getRightType() {
return rightType;
}
public void setRightType(int rightType) {
this.rightType = rightType;
}
public Node(int number){
this.number = number;
}
public int getNumber() {
return number;
}
public void setNumber(int number) {
this.number = number;
}
public Node getLeftNode() {
return leftNode;
}
public void setLeftNode(Node leftNode) {
this.leftNode = leftNode;
}
public Node getRightNlde() {
return RightNlde;
}
public void setRightNlde(Node rightNlde) {
RightNlde = rightNlde;
}
@Override
public String toString() {
return "Node{" +
"number=" + number +
'}';
}
}
上一篇: 1254. 统计封闭岛屿的数目
下一篇: hashMap底层实现