n: 表示二又树中的第几个元素(按0开始编号如图所示)

代码示例

public class ArrayBinaryTree {
    private int[] treeArray;
    private int size;

    public ArrayBinaryTree(int capacity) {
        treeArray = new int[capacity];
        size = 0;
    }

    public void insert(int data) {
        if (size >= treeArray.length) {
            System.out.println("The tree is full");
            return;
        }

        treeArray[size] = data;
        size++;
    }

    public void inorderTraversal(int index) {
        if (index >= size) {
            return;
        }
        
        inorderTraversal(index * 2 + 1); // 访问左子树
        System.out.print(treeArray[index] + " "); // 访问当前节点
        inorderTraversal(index * 2 + 2); // 访问右子树
    }

    public static void main(String[] args) {
        ArrayBinaryTree tree = new ArrayBinaryTree(10);
        tree.insert(1);
        tree.insert(2);
        tree.insert(3);
        tree.insert(4);
        tree.insert(5);

        System.out.print("Inorder Traversal: ");
        tree.inorderTraversal(0); // 输出: 4 2 5 1 3
    }
}

链式存储

用节点对象和指针来表示二叉树的结构。每个节点包含一个数据元素和左右子节点的指针。用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。这种存储结构可以灵活地表示任意形状的二叉树。

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

线索化二叉树

线索二叉树是对普通二叉树的一种扩展，它通过在空指针位置存储指向当前节点的前驱节点和后继节点的指针，使得二叉树的遍历更加方便。可以有效地减少遍历的次数，同时也可以避免空指针的浪费。

• n个结点的二又链表中含有n+1 [公式 2n-(n-1)=n+1] 个空指针域。利用二又链表中的空指针域，存放指向该结点在某种遍历次序下的前驱和后继结点的指针(这种附加的指针称为"线索")

• 这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索叉树、中序线索二叉树和后序线索二叉树三种

• 一个结点的前一个结点，称为前驱结点，一个结点的后一个结点，称为后继结点

代码实现

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    private int leftType; // 0:左子树  1：前驱节点

    private int rightType; // 0:右子树  1：后继节点

    public TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
    // 省略get set方法
}


class ThreadedBinaryTree {

    private TreeNode root;

    //为了实现线索化，需要创建要给指向当前结点的前驱结点的指针
    //在递归进行线索化时，pre 总是保留前一个结点
    private TreeNode pre = null;


    public void setRoot(TreeNode root) {
        this.root = root;
    }

    public void  threadedNodes(){
        this.threadedNodes(root);
    }

    // 线索化节点 中序线索化
    public void  threadedNodes(TreeNode node){

        if (node == null){
            return;
        }

        // 先线索化左子树
        threadedNodes(node.getLeft());

        // 线索化当前节点
        if (node.getLeft() == null){
            //让当前结点的左指针指向前驱结点
            node.setLeft(pre);
            node.setLeftType(1);
        }

        //处理后继结点
        if (pre != null && pre.getRight() == null) {
            //让前驱结点的右指针指向当前结点
            pre.setRight(node);
            //修改前驱结点的右指针类型
            pre.setRightType(1);
        }
        // 让当前结点是下一个结点的前驱结点
        pre = node;

        pre = node;

        // 线索化右子树
        threadedNodes(node.getRight());
    }
}

遍历线索化二叉树

因为线索化后，各个结点指向有变化，因此原来的遍历方式不能使用,这时需要使用新的方式遍历线索化二叉树，各个节点可以通过线型方式遍历,因此无需使用递归方式，这样也提高了遍历的效率。 遍历的次序应当和中序遍历保持一致。

代码实现

    // 遍历线索化二叉树
    public void threadedNodeList(){
        //定义一个变量，存储当前遍历的结点，从root开始
        TreeNode node = root;

        while (node != null){
            while (node.getLeftType() == 0){
                node = node.getLeft();
            }

            System.out.println(node);

            while (node.getRightType() == 1){
                node = node.getRight();
                System.out.println(node);
            }
            node = node.getRight();
        }

    }

以上面图中的例子，进行代码测试