這篇文章主要講解了“如何理解Java數據結構二叉樹難點”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“如何理解Java數據結構二叉樹難點”吧！
首先我們來了解一下什么是線索二叉樹？
定義：一個二叉樹通過如下的方法“穿起來”：所有原本為空的右(孩子)指針改為指向該節點在中序序列中的后繼，所有原本為空的左(孩子)指針改為指向該節點的中序序列的前驅。
再看一下為什么要有線索二叉樹？
顧名思義，線索二叉樹，肯定是根據線索查找，查找速度肯定更快。
線索二叉樹能線性地遍歷二叉樹，從而比遞歸的中序遍歷更快。使用線索二叉樹也能夠方便的找到一個節點的父節點，這比顯式地使用父親節點指針或者棧效率更高。這在?？臻g有限，或者無法使用存儲父節點的棧時很有作用（對于通過深度優先搜索來查找父節點而言)。
那線索僅僅是這樣嗎？當然不，我們都是懶的，能等待解決的問題，為什么會去想新的辦法。我們要解決的是:
為了解決無法直接找到該結點在某種遍歷序列中的前驅和后繼結點的問題
但是同時出現了二叉鏈表找左、右孩子困難的問題，即在構建線索二叉樹之后，鏈表的原來遍歷方式會出問題。
最后看一下什么線索二叉樹的圖解
在我們的線索二叉樹的書上，基本上都有以下這張圖：
大家看到上面這張圖還是有點懵的叭，我們一起看一下我下面手畫的圖
哦！在著之前獻給大家提一下，二叉樹的遍歷方式，有這樣的幾種
前序遍歷二叉樹的遞歸定義(根左右)
中序遍歷二叉樹的遞歸定義(左根右)
后續遍歷二叉樹的遞歸意義(左右根)
本博文主要討論的是中序遍歷
它的中序遍歷結果就是ABCDE F GHI
它的中序線索二叉樹遍歷如下
先畫線索二叉樹
虛線箭頭為線索指針，對于所有左指針指向空的節點：將該節點的左指針指向該節點在中序遍歷中的上一節點；對于所有右指針指向空的節點，將該節點的右指針指向該節點在中序遍歷中的下一結點。最后一個末尾結點除外。
中序圖解線索二叉樹
即形成了一個特殊的雙向鏈表，之所以特殊，以F–>E為例，F–>E并不是直接到達，而是通過F–>B–>D–>E間接到達。
我們嘗試用Java去構建一顆線索二叉樹叭
先申明，我從未使用Java構建過樹，二叉樹都沒有，若有錯誤，請指出
數據結點類
package com.testtree;
/**
* @author pier
*/
public class TreeNode {
/**數據域**/
private int data;
/**左指針**/
private TreeNode left;
/** 左孩子是否為線索，采用布爾類型主要是判斷是否未null足以**/
private boolean leftIsThread;
/**右指針**/
private TreeNode right;
/** 右孩子是否為線索**/
private boolean rightIsThread;
/**根據數據域來確定所在的指針對應位置**/
public TreeNode(int data)
{
this.data = data;
this.left = null;
this.leftIsThread = false;
this.right = null;
this.rightIsThread = false;
}
public int getData()
{
return data;
}
public void setData(int data)
{
this.data = data;
}
public TreeNode getLeft()
{
return left;
}
public void setLeft(TreeNode left)
{
this.left = left;
}
public boolean isLeftIsThread()
{
return leftIsThread;
}
public void setLeftIsThread(boolean leftIsThread)
{
this.leftIsThread = leftIsThread;
}
public TreeNode getRight()
{
return right;
}
public void setRight(TreeNode right)
{
this.right = right;
}
public boolean isRightIsThread()
{
return rightIsThread;
}
public void setRightIsThread(boolean rightIsThread)
{
this.rightIsThread = rightIsThread;
}
@Override
public boolean equals(Object obj)
{
if (obj instanceof TreeNode )
{
TreeNode temp = (TreeNode) obj;
if (temp.getData() == this.data)
{
return true;
}
}
return false;
}
@Override
public int hashCode()
{
return super.hashCode() + this.data;
}
}二叉樹類
package com.testtree;
/*author:pier
2021/10/12
*/
public class BiTree {
/** 根節點 **/
private TreeNode root;
/** 大小 **/
private int size;
/** 線索化的時候保存前驅 **/
private TreeNode pre = null;
public BiTree()
{
this.root = null;
this.size = 0;
this.pre = null;
}
public BiTree(int[] data)
{
this.pre = null;
this.size = data.length;
// 創建二叉樹
this.root = createTree(data, 1);
}
/**
* 創建二叉樹
*
*/
public TreeNode createTree(int[] data, int index)
{
if (index > data.length)
{
return null;
}
TreeNode node = new TreeNode(data[index - 1]);
TreeNode left = createTree(data, 2 * index);
TreeNode right = createTree(data, 2 * index + 1);
node.setLeft(left);
node.setRight(right);
return node;
}
/**中序遍歷**/
public void inList(TreeNode root)
{
if (root != null)
{
inList(root.getLeft());
System.out.print(root.getData() + ",");
inList(root.getRight());
}
}
public TreeNode getRoot()
{
return root;
}
public void setRoot(TreeNode root)
{
this.root = root;
}
public int getSize()
{
return size;
}
public void setSize(int size)
{
this.size = size;
}
/**線索化二叉樹**/
public void inThread(TreeNode root) {
if ( root != null ) {
// 線索化左孩子
inThread(root.getLeft());
// 左孩子為空
if ( null == root.getLeft() )
{
// 將左孩子設置為線索
root.setLeftIsThread(true);
root.setLeft(pre);
}
// 右孩子為空
if ( pre != null && null == pre.getRight() )
{
pre.setRightIsThread(true);
pre.setRight(root);
}
pre = root;
// 線索化右孩子
inThread(root.getRight());
}
}
/**
* 中序遍歷線索二叉樹
*
*/
public void inThreadList(TreeNode root)
{
if (root != null)
{
// 如果左孩子不是線索
while (root != null && !root.isLeftIsThread())
{
root = root.getLeft();
}
do
{
// 如果右孩子是線索
System.out.print(root.getData() + ",");
if (root.isRightIsThread())
{
root = root.getRight();
}
// 有右孩子
else
{
root = root.getRight();
while (root != null && !root.isLeftIsThread())
{
root = root.getLeft();
}
}
} while (root != null);
}
}
}測試類
package com.testtree;
/**
* @author pier
*/
public class Test {
public static void main(String[] args) {
//不要問我為什么設置這么大，結尾看我效果截圖
int[] arr = new int[10000];
for (int i = 0; i < arr.length; i++) {
arr[i]=i+1;
}
//創建一顆二叉樹
BiTree biTree = new BiTree(arr);
//中序遍歷二叉樹
System.out.println("中序遍歷結果如下:");
long start1 = System.currentTimeMillis();
biTree.inList(biTree.getRoot());
long end1 = System.currentTimeMillis();
System.out.println();
System.out.println("普通遍歷時間為:"+(end1-start1)+"毫秒");
System.out.println("\n");
//中序遍歷將二叉樹線索化
biTree.inThread(biTree.getRoot());
System.out.println("線索二叉樹中序遍歷如下:");
long start2 = System.currentTimeMillis();
biTree.inThreadList(biTree.getRoot());
long end2 = System.currentTimeMillis();
System.out.println();
System.out.println("線索二叉樹的遍歷時間為:"+(end2-start2)+"毫秒");
}
}運行結果
當我使用1-10的時候效果截圖
感謝各位的閱讀，以上就是“如何理解Java數據結構二叉樹難點”的內容了，經過本文的學習后，相信大家對如何理解Java數據結構二叉樹難點這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
