二叉树NodeTree——Java实现

package com.zw.dataStructure;

/**
 * 链表实现二叉树
 */
public class NodeTree {

    static class Node {
        int index;
        int data;
        Node parent;
        Node left;
        Node right;

        public Node(int data) {
            this.data = data;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "index=" + index +
                    ", data=" + data +
                    '}';
        }
    }

    Node root;

    public NodeTree(Node root) {
        this.root = root;
        this.root.index = 0;
        this.root.parent = null;
        this.root.left = null;
        this.root.right = null;
    }

    public Node searchNode(int index) {
        return search(root, index);
    }

    private Node search(Node node, int targetIndex) {
        if (node.index == targetIndex) {
            return node;
        } else {
            if (node.left != null) {

                Node leftSearch = search(node.left, targetIndex);
                if (leftSearch != null) {
                    return leftSearch;
                }
            }
            if (node.right != null) {
                Node rightSearch = search(node.right, targetIndex);
                if (rightSearch != null) {
                    return rightSearch;
                }
            }
            return null;
        }
    }

    public boolean addNode(int index, int direction, Node newNode) {
        Node node = searchNode(index);
        if (node == null) {
            return false;
        }
        //插左边
        if (direction == 0) {
            node.left = newNode;
            newNode.index = node.index * 2 + 1;
        } else {
            //右边
            node.right = newNode;
            newNode.index = node.index * 2 + 2;
        }
        newNode.parent = node;
        return true;
    }

    public boolean deleteNode(int index) {
        Node node = searchNode(index);
        if (node == null) {
            return false;
        }
        Node parent = node.parent;
        if (parent != null) {
            if (parent.left == node) {
                parent.left = null;
            } else if (parent.right == node) {
                parent.right = null;
            }
            return true;
        }
        return true;
    }

    /**
     * 前序遍历    中 左 右
     */
    public void preOrderTraverse() {
        preOrder(root);
    }

    private void preOrder(Node node) {
        System.out.print(node.data + "  ");
        if (node.left != null) {
            preOrder(node.left);
        }
        if (node.right != null) {
            preOrder(node.right);
        }
    }

    /**
     * 中序遍历    左 中 右
     */
    public void inOrderTraverse() {
        inOrder(root);
    }

    private void inOrder(Node node) {
        if (node.left != null) {
            inOrder(node.left);
        }
        System.out.print(node.data + "  ");
        if (node.right != null) {
            inOrder(node.right);
        }
    }

    /**
     * 后序遍历   左右中
     */
    public void postOrderTraverse() {
        postOrder(root);
    }

    private void postOrder(Node node) {
        if (node.left != null) {
            postOrder(node.left);
        }
        if (node.right != null) {
            postOrder(node.right);
        }
        System.out.print(node.data+"  ");
    }

    public static void main(String[] args) {

        Node root = new Node(3);
        NodeTree tree = new NodeTree(root);

        tree.addNode(0, 0, new Node(5));
        tree.addNode(0, 1, new Node(8));

        tree.addNode(1, 0, new Node(2));
        tree.addNode(1, 1, new Node(6));

        tree.addNode(2, 0, new Node(9));
        tree.addNode(2, 1, new Node(7));

//        System.out.println("111");
//        System.out.println(tree.searchNode(0));
//        System.out.println(tree.searchNode(1));
//        System.out.println(tree.searchNode(2));
//        System.out.println(tree.searchNode(3));
//        System.out.println(tree.searchNode(4));
//        System.out.println(tree.searchNode(5));
//        System.out.println(tree.searchNode(6));
//        System.out.println(tree.searchNode(7));

        tree.deleteNode(3);

        System.out.println("3  5  8  2  6  9  7");
        System.out.println("\npreOrderTraverse:");
        tree.preOrderTraverse();
        System.out.println("\ninOrderTraverse:");
        tree.inOrderTraverse();
         System.out.println("\npostOrderTraverse:");
        tree.postOrderTraverse();
    }

}