Wie implementiert man einen Thread-Binärbaum in einer Java-Datenstruktur?
- WBOYnach vorne
- 2023-05-09 08:05:43648Durchsuche
1. Einführung in Clued Binary Trees
Konstruieren Sie die Sequenz {1, 3, 6, 8, 10, 14} in einen Binärbaum.
Problemanalyse:
1 Baum Während der Durchquerung in der Reihenfolge ist das Array {8, 3, 10, 1, 6, 14}
2. Die linken und rechten Zeiger der Knoten 6, 8, 10, 14 werden jedoch nicht vollständig genutzt.
3. Was ist, wenn wir die linken und rechten Zeiger jedes Knotens vollständig nutzen möchten, damit jeder Knoten auf seinen eigenen vorherigen und nachfolgenden Knoten verweisen kann? Binär verknüpfte Liste als Speicherstruktur des Binärbaums. Es ist einfach, die linken und rechten untergeordneten Knoten eines Knotens zu finden, aber im Allgemeinen ist es nicht möglich, die Vorgänger- und Nachfolgerknoten des Knotens in einer bestimmten Durchlaufsequenz direkt zu finden . Daher wird Threading verwendet und das Nullzeigerfeld der verknüpften Liste der Binärbaumstruktur wird zum Threading verwendet.
2. Grundlegende Eigenschaften von Thread-Binärbäumen
Eine binär verknüpfte Liste von n Knoten enthält n+1 [Formel 2n-(n-1)=n+1] Nullzeigerfelder. Verwenden Sie das Nullzeigerfeld in der binär verknüpften Liste, um Zeiger auf die Vorgänger- und Nachfolgerknoten des Knotens in einer bestimmten Durchlaufreihenfolge zu speichern (solche zusätzlichen Zeiger werden als „Hinweise“ bezeichnet).
Diese Art von hinzugefügten Hinweisen wird als binär verknüpfte Liste bezeichnet eine mit Threads verknüpfte Liste, und der entsprechende Binärbaum wird als Thread-Binärbaum (Threaded BinaryTree) bezeichnet. Entsprechend der unterschiedlichen Art der Hinweise können Hinweis-Binärbäume in drei Typen unterteilt werden: Hinweis-Binärbäume vor der Bestellung, Hinweis-Binärbäume in der Reihenfolge und Hinweis-Binärbäume nach der Bestellung
3 Anwendungsfälle von Hinweis-Binärbäumen
In-Order-Clue-Binärbäume und Traversierung
Anwendungsfälle Beschreibung: Konvertieren Sie den folgenden Binärbaum in einen In-Order-Clue-Binärbaum. Die Zahlenfolge des Durchlaufs in der Reihenfolge ist {8, 3, 10, 1, 14, 6} 6}
Dann sind die linken und rechten Zeiger des Binärbaums nach dem Threading wie in der Abbildung oben gezeigt↑
Erklärung: Wenn der Binärbaum eingefädelt wird, haben die Attribute links und rechts vom Knotenknoten Folgendes Situationen:
Links zeigt auf den linken Teilbaum, auch Es kann sich um den Vorgängerknoten handeln, auf den beispielsweise der linke Teilbaum von Knoten ① zeigt und der linke Teilbaum von Knoten ⑩ auf den Vorgängerknoten zeigt
Rechts zeigt auf den rechten Teilbaum, oder es zeigt möglicherweise auf den Nachfolgeknoten, z. B. Knoten ① zeigt rechts auf den rechten Teilbaum und das Recht des Knotens ⑩ zeigt auf den Nachfolgeknoten.
Wir müssen uns also ändern die Knotenstruktur des ursprünglichen Binärbaums
package com.studySelf.tree.threadedBinaryTree;
/**
* @author wang
* @version 1.0
* @packageName com.studySelf.tree.tree01
* @className Node
* @date 2022/4/19 20:15
* @Description Node结点
*/
public class Node {
//唯一编号
private int num;
//结点的值
private String name;
//左结点
private Node left;
//右节点
private Node right;
//这个属性用来控制线索二叉树的结点的指向，0代表指向左结点，1代表指向前趋结点
private int leftType;
//这个属性用来控制线索二叉树的结点的指向，0代表指向右结点，1代表指向后继结点
private int rightType;
//构造方法
public Node(int num, String name) {
this.num = num;
this.name = name;
}
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 int getNum() {
return num;
}
public void setNum(int num) {
this.num = num;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
@Override
public String toString() {
return "Node{" +
"num=" + num +
", name='" + name +
'}';
}
/**
* 前序遍历
*/
public void preSelect() {
//首先输出根结点
System.out.println(this);
//其次判断是否有左结点
if (this.left != null) {
//没有左结点，就递归调用本方法输出该结点。
this.left.preSelect();
}
if (this.right != null) {
this.right.preSelect();
}
}
/**
* 中序遍历
*/
public void infixSelect() {
//首先判断左结点
if (this.left != null) {
//如果左结点不为空，递归向左子树调用
this.left.infixSelect();
}
//当左结点为空，再输出根结点。当他本身就是最后一个左结点的时候，会直接输出，且没有右节点
System.out.println(this);
if (this.right != null) {
//右节点同样如此，递归调用。直到没有结点为止。
this.right.infixSelect();
}
}
/**
* 设二叉树有三个结点，根结点，左结点，右节点。
* 后序遍历,解释，当一个二叉树的左结点不为空，那么他会进入下一个递归调用自己的后序遍历方法
* 此时，根结点就是左结点，这时判断左结点，右节点均为空，就会输出左结点
* 回退到根结点为this的时候，左结点已经判断完毕，接下来是右节点，右节点不为空，进入后续遍历递归，
* 此时的this就是右节点，进入递归后，判断，不存在左右结点，输出this，也就是整个二叉树的右节点
* 回退到this为根结点时，右节点也已经输出，走到最后一步，输出自己也就是this。
* 整个后序遍历就结束，那么该二叉树的遍历结果就是左，右，根
*/
public void afterSelect() {
if (this.left != null) {
this.left.afterSelect();
}
if (this.right != null) {
this.right.afterSelect();
}
System.out.println(this);
}
/**
* @param num
* @Date 2022/4/21 17:51
* @Param
* @Return Node
* @MetodName preSearchByNum
* @Author wang
* @Description 根据结点的编号来查询结点, 前序遍历查询，根，左，右
*/
public Node preSearchByNum(int num) {
//首先判断传进来的num与该结点的num是否相等
//如果相等，那该结点就是我们要找的结点。
if (this.num == num) {
return this;
}
//如果不相等，该结点就不是我们要找的结点
//那么我们就遍历该结点的左子节点，和右子结点
//定义一个结点用于接收最后的返回结果
Node resultNode = null;
//如果该结点的左子结点不为空，就递归调用前序遍历，继续查找，如果找到了，那么resultNode就是我们想要的值
if (this.left != null) {
resultNode = this.left.preSearchByNum(num);
}
//如果遍历完左子结点，已经找到了我们想要的结果，直接返回结果即可，
if (resultNode != null) {
return resultNode;
}
//如果左子结点为空，且没有找到我们想要的结点的情况下。那就判断右子结点
if (this.right != null) {
resultNode = this.right.preSearchByNum(num);
}
//最后，如果找到了，那么resultNode一定会被赋值，如果没找到，就会返回null
return resultNode;
}
/**
* @param num
* @Date 2022/4/21 17:58
* @Param
* @Return Node
* @MetodName infixSearchByNum
* @Author wang
* @Description 中序遍历查找，左，根，右进行查询即可。
*/
public Node infixSearchByNum(int num) {
//首先判断左子结点,如果存在左子结点，递归继续查询遍历即可即可。
Node resultNode = null;
if (this.left != null) {
resultNode = this.left.infixSearchByNum(num);
}
//如果左子结点已经找到了我们想要的结点，直接返回当前结点即可
if (resultNode != null) {
return resultNode;
}
//判断根结点
if (this.num == num) {
return this;
}
//判断右子结点，
if (this.right != null) {
resultNode = this.right.infixSearchByNum(num);
}
//最后返回我们的结果即可。
return resultNode;
}
/**
* @param num
* @Date 2022/4/21 19:15
* @Param
* @Return Node
* @MetodName afterSearchNum
* @Author wang
* @Description 后续遍历结点进行查找结点。左，右，根
*/
public Node afterSearchNum(int num) {
Node resultNode = null;
//首先遍历左结点
if (this.left != null) {
resultNode = this.left.afterSearchNum(num);
}
//判断左结点是否找到哦啊
if (resultNode != null) {
return resultNode;
}
//判断右节点是否为空
if (this.right != null) {
resultNode = this.right.afterSearchNum(num);
}
//判断右节点是否找到
if (resultNode != null) {
return resultNode;
}
//判断根结点是否为我们找的结点
if (this.num == num) {
return this;
}
//最后返回
return resultNode;
}
/**
* @param num
* @Date 2022/4/25 19:30
* @Param
* @Return void
* @MetodName delNodeByNum
* @Author wang
* @Description 根据结点的编号删除结点
*/
public void delNodeByNum(int num) {
//首先，判断当前结点的左结点是否为空，并且左结点的num是否与num相等
if (this.left != null && this.left.num == num) {
//如果相等，那就说明该结点就是我们要删除的结点,将其左结点置空即可
this.left = null;
return;
}
//如果左结点没有执行，说明左结点没有我们想要的结果，也就是要删除的结点不在左结点
//那么就对右节点进行判断
if (this.right != null && this.right.num == num) {
this.right = null;
return;
}
//如果左右结点均没有找到目标结点
//那么就对左子树进行递归删除操作
if (this.left != null) {
this.left.delNodeByNum(num);
}
//同理，如果左子树没有目标结点，向右子树进行递归删除操作
if (this.right != null) {
this.right.delNodeByNum(num);
}
}
}Sie können sehen, dass wir diese beiden zusätzlichen Attribute haben:
//这个属性用来控制线索二叉树的结点的指向，0代表指向左结点，1代表指向前趋结点
private int leftType;
//这个属性用来控制线索二叉树的结点的指向，0代表指向右结点，1代表指向后继结点
private int rightType; - In-Reihenfolge-Threaded-Binärbaum
/**中序线索化二叉树*/ /** * @param node 该结点为根结点，从根节点开始线索化二叉树，中序 */ public void infixThreadNodes(Node node) { /**首先判断二叉树的根节点上会否为空，如果根结点为空，不可以线索化，因为没有二叉树*/ if (node == null) { return; } /**接着对左子树进行线索化*/ infixThreadNodes(node.getLeft()); /**对当前结点进行线索化*/ /**首先判断当前结点的左子结点是否为空*/ if (node.getLeft() == null) { //如果左子结点为空，说明就找到了我们需要线索化的结点 //就可以将pre也就是一直在当前结点的前趋结点设置给当前结点的左子结点， //如果这是第一个结点，那么pre为空，正好第一个结点的前趋结点也为空 node.setLeft(pre); //并且将它的左子结点的类型设置为前趋结点。1代表前趋结点 node.setLeftType(1); } /**接着判断前趋结点的右子结点是否为空，前提是前趋结点不能为空，如果他为空，说明这是第一个结点还没走完*/ if (pre != null && pre.getRight() == null) { //如果条件满足，说明前趋结点现在已经走到了值，并且还没有线索到后继结点， // 也就是当前结点的上一个结点（这个上一个结点就是当前的前趋结点）还没有后继， //那么上一个结点的后继结点就是当前结点，因此赋值前趋结点（也就是上一个结点）的后继结点为当前结点。 //这样这条线索就连接上了,并且只有满足叶子结点的结点才可以进行线索化 pre.setRight(node); pre.setRightType(1); } //当前两步走完之后，就可以将pre结点赋值为当前结点， // 因为下一个结点一走，当前结点就是前趋结点了。直到走到全部线索化结束 //这步十分重要，这一步不写，整个线索化就连接不上 pre = node; /**对右子树进行线索化*/ infixThreadNodes(node.getRight()); }Idee eines Threaded-Binärbaums mittlerer Ordnung
Weil die Reihenfolge der Der in der richtigen Reihenfolge durchlaufene Binärbaum hat eine linke und eine rechte Wurzel. Daher wird zuerst der linke Teilbaum eingefädelt und dann rekursiv eingefädelt Dem Knoten wird der Wert pre zugewiesen (dem Vorknoten wird im letzten Schritt des Threading-Knotens der aktuelle Wert zugewiesen, damit die Rekursion fortgesetzt werden kann). Beachten Sie, dass der Typ des linken Knotens in 1 geändert werden muss, was bedeutet, dass dies der Fall ist der Vorgängerknoten. Der Vorgängerknoten hat seinen Hinweis verloren.
Die Verarbeitung des Nachfolgerknotens besteht darin, den Vorgängerknoten zu bestimmen. Wenn der aktuelle Trendknoten nicht leer ist und der rechte Knoten des Vorgängerknotens leer ist, wird der rechte Knoten des Vorgängerknotens als aktueller Knoten festgelegt . Das heißt, der rechte Knoten des vorherigen Knotens wurde nicht festgelegt, der Typ muss auch auf Nachfolger festgelegt werden
Der letzte Schritt besteht darin, dem Vorknoten, dem aktuellen Knoten, einen Wert zuzuweisen, da der Bei der nächsten Rekursion wird der aktuelle Knoten zum vorherigen Knoten, der hier der Vorknoten ist und schließlich den rechten untergeordneten Knoten des Binärbaums angibt.
- Durchqueren von Binärbäumen mit Threads in der richtigen Reihenfolge
- Beim Durchlaufen eines Binärbaums mit Threads in der richtigen Reihenfolge sollte zunächst klar sein, dass die Durchlaufreihenfolge mit dem Ergebnis des Durchlaufens der ursprünglichen Binärdatei in der richtigen Reihenfolge identisch sein muss Baum, dann ist die Durchquerung erfolgreich
- Dann sollte der erste Schritt darin bestehen, festzustellen, dass der Wurzelknoten nicht leer ist, was die Endbedingung der Schleife ist
- Dann machen wir eine Schleife, um den linken untergeordneten Knoten des Stroms zu finden Der Typ eines Knotens ist 0, d. h. ein Knoten ohne Thread-Punkt. Solange er 0 ist, weist der Knoten dem linken untergeordneten Knoten immer Werte zu. Bis wir den ersten Thread-Knoten finden und ihn ausgeben, ist er unser erster Thread-Knoten und der erste linke untergeordnete Knoten des Durchlaufs in der richtigen Reihenfolge.
- Bestimmen Sie nach der Ausgabe, ob der rechte untergeordnete Knoten mit einem Thread versehen ist. Wenn er mit einem Thread versehen ist, wird der aktuelle Knotenknoten als sein eigener rechter untergeordneter Knoten zugewiesen und ausgegeben, wenn der Knoten danach der Typ des rechten untergeordneten Knotens ist Knoten ist wieder 1, gehen Sie dann weiter zurück und weisen Sie Werte zu, um anzuzeigen, dass er einen Nachfolger hat
- , bis der Typ des rechten untergeordneten Knotens 0 ist. Nach dem Verlassen der Schleife sollten Sie auch rechts Werte zuweisen und fahren Sie mit der Post-Traversal-Code-Demonstration fort. Thread-Binärbaum vorbestellen, Traversal-Thread-Binärbaum
/**
* 前序线索化二叉树
*/
public void preThreadNodes(Node node) {
/**首先判断当前节点是否为空*/
if (node == null) {
return;
}
/**如果是前序遍历，那么先对当前结点进行判断，当前结点的前趋结点的操作*/
if (node.getLeft() == null) {
node.setLeft(pre);
node.setLeftType(1);
}
/**处理后继结点,定义的前趋结点不为空，说明他有值，就是已经存在了上一个结点的值，他的右子结点没有值的话，就可以
* 给他赋予后继结点为当前结点，这里赋予的也就是上一个结点*/
if (pre != null && pre.getRight() == null) {
pre.setRight(node);
pre.setRightType(1);
}
/**这里是关键的一步*/
pre = node;
/**对左子结点进行线索化,注意，这里需要排除已经被线索化掉的结点,因为这里要考虑一个情况，
* 比如这里已将到了最下面一个左子结点，由于是前序遍历，遍历到左子结点，他的前趋结点在上面就设置了
* 如果这里不判断左子结点的类型，那么就会进入递归，但是这个递归如果进去了，就是错误的递归，因为他传过去的结点
* 是我们刚刚给他赋值的前趋结点，也就是根结点。会发生错误。因此得判断类型*/
if (node.getLeftType() != 1) {
preThreadNodes(node.getLeft());
}
/**对右子结点进行递归线索化*/
if (node.getRightType() != 1) {
preThreadNodes(node.getRight());
}
}遍历线索化二叉树
/**
* 前序遍历线索二叉树*/
public void preThreadNodeSelect() {
Node node = root;
while(node !=null) {
while(node.getLeftType() == 0) {
/**前序遍历为根左右，先输出根结点,因为他每次进来循环肯定是先到根结点，所以一进该循环
* 就要输出根结点，当他的lefttype=1循环结束，说明遇到了被线索化的地方了。*/
System.out.println(node);
/**再最左子结点进行遍历*/
node = node.getLeft();
}
/**上面的循环结束之后就应该输出当前结点，也就是那个序列化的结点
* 之后结点向右移动继续遍历*/
System.out.println(node);
node = node.getRight();
}
}图解
5.后序线索化二叉树
后续线索化二叉树
/**
* 后序线索化二叉树的方法
*/
public void postThreadedBinaryTree(Node node) {
/**首先判断结店不能为空*/
if (node == null) {
return;
}
/**先后续线索化左子结点*/
postThreadedBinaryTree(node.getLeft());
/**在后续线索化右子结点*/
postThreadedBinaryTree(node.getRight());
/**处理当前结点的前趋结点*/
if (node.getLeft() == null) {
node.setLeft(pre);
node.setLeftType(1);
}
/**处理后继结点*/
if (pre != null && pre.getRight() == null) {
pre.setRight(node);
pre.setRightType(1);
}
pre = node;
}Das obige ist der detaillierte Inhalt vonWie implementiert man einen Thread-Binärbaum in einer Java-Datenstruktur?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!