二叉树【数据结构与算法java】

LeetCode

TreeNode

LeetCode的结点类

package leetcode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author CSDN@日星月云
 * @date 2022/10/28 00:25
 */
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    public TreeNode() {
        //无参数构造函数
    }
    public TreeNode(int val) {
        this.val = val;
    }
    public TreeNode(int val,TreeNode left,TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }


    @Override
    public String toString() {
        return "TreeNode{" +
                "val=" + val +
                ", left=" + left +
                ", right=" + right +
                '}';
    }


}

BiTree

二叉树的实现

package leetcode;

import java.util.*;

/**
 * @author CSDN@日星月云
 * @date 2022/10/25 23:09
 */
public class BiTree {
    TreeNode root;
    BiTree(){
            root=null;
    }

    //用扩展先序遍历序列创建二叉链表
    //依靠队列，当队首元素分配了左右孩子就出队
    public TreeNode setTree(Integer[] data)//data为传入的形参数组，如Integer[] nums = {1,2,null,4,null,5}
    {
        root = new TreeNode(data[0]);
        Queue<TreeNode> queue = new LinkedList<>();//先入先出，构造子树
        queue.offer(root);
        int i = 1;//从第二个元素开始入列
        while(i<data.length)
        {
            TreeNode node = queue.poll();//弹出队列中的树节点
            if(data[i] != null)//当实参的元素不为null时，添加左节点
            {
                node.left = new TreeNode(data[i]);
                queue.offer(node.left);
            }
            i++;//不管实参(传入Integer[] data的Integer数组)的元素是不是null，均需要后移一位
            if(data[i] != null)//当实参的元素不为null时，添加右节点
            {
                node.right = new TreeNode(data[i]);
                queue.offer(node.right);
            }
            i++;
        }
        return root;//返回根节点
    }


    //访问
    void visit(int n){
        System.out.print(n+" ");
    }

    // 递归 先序
    void preOrder(TreeNode root){
        //先序遍历二叉树，root为根节点的指针
        if (root!=null){
            visit(root.val);
            preOrder(root.left);
            preOrder(root.right);
        }
    }



    public static void main(String[] args) {
        BiTree biTree=new BiTree();
        Integer[] nodes=new Integer[]{
          1,2,3,null,null,null,null
        };
        biTree.setTree(nodes);
        System.out.println(biTree.root.toString());
        biTree.preOrder(biTree.root);
    }

}

完整源代码

Node 节点类

package tree;

/**
 * @author CSDN@日星月云
 * @date 2022/10/25 23:18
 * iData来判断插入到左还是右
 */
class Node{
        public int iData;// data item (key)  主键 用来实现二叉排序树
        public double dData;// data item     信息
        public Node leftChild;// this node's left child
        public Node rightChild;// this node 's right child
        public void displayNode(){// display ourself
                System.out.print ('{');
                System.out.print (iData) ;
                System.out.print(",");
                System.out.print (dData);
                System.out.print("}");
        }
}

Tree 树类

package tree;

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Stack;

/**
 * @author CSDN@日星月云
 * @date 2022/10/25 23:25
 * Tree 类
 * 还需要有一个表示树本身的类，由这个类实例化的对象含有所有的节点，这个类是Tree类。它. 只有一个数据字段：一个表示根的Node变量。它不需要包含其他节点的数据字段，因为其他节点 都可以从根开始访问到。
 * Tree类有很多方法。它们用来査询、插入和删除节点；进行各种不同的遍历；显示树。下面是 这个类的骨架：
 */
public class Tree {
    public Node root;//first node of tree

    // ---------------------------------------
    public Tree() { // constructor
        root = null;// no nodes in tree yet
    }

    /**
     * 从根开始。（它只能这样做，因为只有根节点可以直接访问。）因此，开始把current设为根。
     * 之后，在while循环中，将要查找的值，key与当前节点的iData字段的值（关键字字段）做比
     * 较。如果key小于这个数据域的值，current设为此节点的左子节点。如果key大于（或等于）节点
     * iData字段的值，current设为此节点的右子节点。
     * 找不到节点
     * 如果current等于null,在查找序列中找不到下一个子节点；到达序列的末端而没有找到要找的
     * 节点，表明了它不存在。返回null来指岀这个情况。
     * 找到节点
     * 如果while循环的条件不满足，从循环的末端退出来，current的iData字段和key相等：这就
     * 是说找到该节点了。返回这个节点，调用find。方法的程序可以访问节点的任何字段。
     * @param key
     * @return
     */
    //按主键找结点
    public Node find(int key) { //find node with given key (assumes non-empty tree)
        Node current = root;// start at root
        while (current.iData != key) {// while no match,
            if (key < current.iData)// go left
                current = current.leftChild;
            else// or go right?
                current = current.rightChild;
            if (current == null)// if no child
                return null; // didn't find it
        }
        return current;// found it
    }// end find( )

    // ---------------------------------------

    /**
     *
     * @param id
     * @param dd
     */
    //插入二叉排序树
    public void insert(int id, double dd) {
        Node newNode = new Node();
        //make new node
        newNode.iData = id;//insert data
        newNode.dData = dd;
        if (root == null)// no node in root
            root = newNode;
        else { // root occupied
            Node current = root; // start at root
            Node parent;
            //迭代 知道cur==null parent是上次循环也就是当前cur的父结点
            while (true) {//(exits internally)
                parent = current;
                if (id < current.iData) {// go left?
                    current = current.leftChild;
                    if (current == null) {// if end of the line,
                        // insert on left
                        parent.leftChild = newNode;
                        return;
                    }
                }// end if go left
                else {// or go right?
                    current = current.rightChild;
                    if (current == null) {// if end of the line
                        // insert on right
                        parent.rightChild = newNode;
                        return;
                    }
                } // end else go right
            } // end while
        }// end else not root
    }// end insert

    //删除结点
    //二叉排序树的删除
    public boolean delete(int key) {        //delete node with given key
        // (assumes non-empty list)
        Node current = root;
        Node parent = root;
        boolean isLeftChild = true;//待删结点是左孩子
        //情况1：删除没有子节点的节点
        //找不到该结点 返回false
        // delete()方法的第一部分和find()和insert()方法很像。它査找要删除的节点。和insert()一样，需
        // 要保存要删节点的父节点，这样就可以修改它的子字段的值了。如果找到节点了，就从while循环
        // 中跳出，parent保存要删除的节点。如果找不到要删除的节点，就从delete。方法返回false。
        while (current.iData != key) {// search for node
            parent = current;
            if (key < current.iData) { // go left?
                isLeftChild = true;
                current = current.leftChild;
            } else {
                // or go right?
                isLeftChild = false;
                current = current.rightChild;
            }
            if (current == null)// end of the line,
                return false; // didn't find it
        } // end while

        // 找到节点后，先要检查它是不是真的没有子节点。如果它没有子节点，还需要检査它是不是根。
        // 如果它是根的话，只需要把它置为null；这样就清空了整棵树。否则，就把父节点的leftChild或
        // rightChild字段置为null,断开父节点和那个要删除节点的连接。
        // 找到待删结点
        // found node to delete
        // if no children, simply delete it
        // 如果没有孩子，直接删掉
        if (current.leftChild == null && current.rightChild == null) {
            if (current == root)// if root,
                root = null;// tree is empty
            else if (isLeftChild)
                parent.leftChild = null;// disconnect
            else// from parent
                parent.rightChild = null;
        }
        //情况2：删除有一个子节点的节点
        // if no right child, replace with left subtree
        else if (current.rightChild == null) {
            if (current == root) root = current.leftChild;
            else if (isLeftChild)
                parent.leftChild = current.leftChild;
            else
                parent.rightChild = current.leftChild;
        }

        // if no left child, replace with right subtree
        else if (current.leftChild == null) {
            if (current == root)
                root = current.rightChild;
            else if (isLeftChild) parent.leftChild = current.rightChild;
            else
                parent.rightChild = current.rightChild;
        } else {// two children, so replace with inorder successor
            // get successor of node to delete (current)
            Node successor = getSuccessor(current);

            // connect parent of current to successor instead
            if (current == root)
                root = successor;
            else if (isLeftChild)
                parent.leftChild = successor;
            else
                parent.rightChild = successor;

            // connect successor to current's left child
            successor.leftChild = current.leftChild;
            // end else two children// (successor cannot have a left child)
        }
        return true; // success
    }// end delete()
    // returns node with next-highest value after delNode

    //找到二叉排序树中序遍历的后继结点
    // goes to right child, then right child's left descendents
    private Node getSuccessor(Node delNode) {
        Node successorParent = delNode;
        Node successor = delNode;
        Node current = delNode.rightChild;// go to right child
        while (current != null) {// until no more
            // left children,
            successorParent = successor;
            successor = current;// go to left child
            current = current.leftChild;
        }
        // if successor not
        if (successor != delNode.rightChild) {// right child,
            // make connections
            successorParent.leftChild = successor.rightChild;
            successor.rightChild = delNode.rightChild;
        }
        return successor;
    }

    //------------------------------------------------
    //遍历的程序接口
    public void traverse(int traverseType) {
        switch (traverseType) {
            case 1:
                System.out.print("Preorder traversal: ");
                preOrder(root);
                break;

            case 2:
                System.out.print("Inorder traversal: ");
                inOrder(root);
                break;
            case 3:
                System.out.print("Postorder traversal: ");
                postOrder(root);
                break;
        }
        System.out.println();
    }

    //------------------------------------------------
    //递归的前序遍历
    public void preOrder(Node localRoot) {
        if (localRoot != null) {
            System.out.print(localRoot.iData + " ");
            preOrder(localRoot.leftChild);
            preOrder(localRoot.rightChild);
        }
    }

    //------------------------------------------------
    //递归的中序遍历
    public void inOrder(Node localRoot) {
        if (localRoot != null) {
            inOrder(localRoot.leftChild);
            System.out.print(localRoot.iData + " ");
            inOrder(localRoot.rightChild);
        }
    }

    //------------------------------------------------
    //递归的后序遍历
    public void postOrder(Node localRoot) {
        if (localRoot != null){
            postOrder(localRoot.leftChild);
            postOrder(localRoot.rightChild);
            System.out.print(localRoot.iData + " ");
        }
    }
    //------------------------------------------------

    //层次遍历 null显示--
    public void displayTree() {
        Stack globalStack = new Stack();
        globalStack.push(root);
        int nBlanks = 32;
        boolean isRowEmpty = false;
        System.out.println("---------------------------------------------" +
                "--------------------------------");
        while (isRowEmpty == false) {
            Stack localStack = new Stack();
            isRowEmpty = true;
            for (int j = 0; j < nBlanks; j++)
                System.out.print(' ');
            while (globalStack.isEmpty() == false) {
                Node temp = (Node) globalStack.pop();
                if (temp != null) {
                    System.out.print(temp.iData);
                    localStack.push(temp.leftChild);
                    localStack.push(temp.rightChild);
                    if (temp.leftChild != null || temp.rightChild != null)
                        isRowEmpty = false;
                } else {
                    System.out.print("--");
                    localStack.push(null);
                    localStack.push(null);
                }
                for (int j = 0; j < nBlanks * 2 - 2; j++) {
                    System.out.print(' ');
                }// end while globalStack not empty

            }
            System.out.println();
            nBlanks /= 2;
            while (localStack.isEmpty() == false) {
                globalStack.push(localStack.pop());
            } // end while isRowEmpty is false
            System.out.println("--------------------------------" +
                    "--------------------------------------------");
        }
    }// end displayTree()



    //--------------------------另外补充--------------------------
    //非递归遍历的程序接口
    public void traverseN(int traverseType) {
        switch (traverseType) {
            case 1:
                System.out.print("PreorderN traversal: ");
                preOrderN(root);
                break;

            case 2:
                System.out.println("InorderN traversal: ");
                System.out.print("inOrderN1 traversal: ");
                inOrderN1(root);
                System.out.print("inOrderN2 traversal: ");
                inOrderN2(root);
                break;
            case 3:
                System.out.print("PostorderN traversal: ");
                postOrderN(root);
                break;
        }
        System.out.println();
    }

    //先序非递归
    public void preOrderN(Node localRoot){
        Stack<Node> stack=new Stack<>();
        Node cur=localRoot;
        while (cur!=null||!stack.isEmpty()){//当前结点指针及栈均空,则结束
            while (cur!=null){//访问根结点,根指针进栈,进入左子树
                System.out.print(cur.iData+" ");
                stack.push(cur);
                cur=cur.leftChild;
            }
            if (!stack.isEmpty()){
                cur = stack.pop();
                cur=cur.rightChild;//根指针退栈,进入其右子树
            }
        }
        System.out.println();
    }


    //中序非递归1
    public void inOrderN1(Node localRoot){
        Stack<Node> stack=new Stack<>();
        Node cur=localRoot;
        while (cur!=null||!stack.isEmpty()){//当前结点指针及栈均空,则结束
            while (cur!=null){//访问根结点,根指针进栈,进入左子树
                stack.push(cur);
                cur=cur.leftChild;
            }
            if (!stack.isEmpty()){
                cur = stack.pop();
                System.out.print(cur.iData+" ");
                cur=cur.rightChild;//根指针退栈,进入其右子树
            }
        }
        System.out.println();
    }

    //中序非递归2
    public void inOrderN2(Node localRoot){
        Stack<Node> stack=new Stack<>();
        Node cur=localRoot;
        while (cur!=null||!stack.isEmpty()){//当前结点指针及栈均空,则结束
            if (cur!=null){//访问根结点,根指针进栈,进入左子树
                stack.push(cur);
                cur=cur.leftChild;
            } else{
                cur = stack.pop();
                System.out.print(cur.iData+" ");
                cur=cur.rightChild;//根指针退栈,进入其右子树
            }
        }
        System.out.println();
    }


    //非递归 后序
    void postOrderN(Node localRoot){
        Stack<Node> stack=new Stack<>();
        Node cur=localRoot,next=null;
        while (cur!=null||!stack.isEmpty()){//当前结点指针及栈均空,则结束
            while (cur!=null){//访问根结点,根指针进栈,进入左子树
                stack.push(cur);
                cur=cur.leftChild;
            }
            if (!stack.isEmpty()){
                cur=stack.peek();//先要进行判断符合以下条件，再进行弹出
                //判断栈顶结点的右子树是否为空，右子树是否刚访问过
                if (cur.rightChild==null||cur.rightChild==next) {
                    cur= stack.pop();
                    System.out.print(cur.iData+" ");
                    next=cur;
                    cur=null;
                }else {
                    cur=cur.rightChild;
                }
            }
        }

    }


    //层序遍历
    //借助队列
    void levelOrder(Node localRoot){
        Queue<Node> queue= new ArrayDeque<>();
        Node cur;
        queue.add(localRoot);
        while (!queue.isEmpty()){
            cur=queue.remove();
            System.out.print(cur.iData+" ");
            if (cur.leftChild!=null){
                queue.add(cur.leftChild);
            }
            if (cur.rightChild!=null){
                queue.add(cur.rightChild);
            }
        }

        System.out.println();

    }

    // 先序遍历统计二叉树的结点数
    int count=0;
    void countWithPreOrder(Node localRoot){
        //Count为统计结点数目的全局变量，调用前初始值为0
        if (localRoot!=null){
            count++;//统计结点数
            countWithPreOrder(localRoot.leftChild);//先序遍历左子树
            countWithPreOrder(localRoot.rightChild);//先序遍历右子树
        }
    }

    //  中序遍历输出二叉树的叶子结点
    void printTNWithInOrder(Node root){
        if(root!=null){
            printTNWithInOrder(root.leftChild);
            if(root.leftChild==null&&root.rightChild==null){
                System.out.print(root.iData+" ");
            }
            printTNWithInOrder(root.rightChild);
        }
//        System.out.println();
    }


    //  后序遍历输出二叉树的叶子结点数目
    int leaf(Node root){
        int nl,nr;
        if(root==null){
            return 0;
        }
        if((root.leftChild==null)&&(root.rightChild==null)){
            return 1;
        }
        nl=leaf(root.leftChild);//递归求左子树的叶子数
        nr=leaf(root.rightChild);//递归求右子树的叶子数
        return(nl+nr);
    }


    //全局变量法求二叉树的高度
    int depth=0;
    void treeDepth(Node root, int h){
        //h为root结点所在的层次，首次调用前初始值为1
        //depth为记录当前求得的最大层次的全局变量,调用前初始值为0

        if(root!=null){
            if(h>depth) {
                depth=h;//当前结点层大于depth,则更新
            }
            treeDepth(root.leftChild,h+1);//遍历左子树,子树根层次为h+1

            treeDepth(root.rightChild,h+1);//遍历右子树,子树根层次为h+1

        }
    }

    //求二叉树的高度
    int postTreeDepth(Node root){
        int hl,hr,h;
        if(root== null) return 0;
        else{
            hl = postTreeDepth(root.leftChild);//递归求左子树的高度
            hr= postTreeDepth(root.rightChild);//递归求右子树的高度
            h=(hl>hr? hl:hr)+1;				//计算树的高度
            return h;
        }
    }

    //求二叉树中某一结点的双亲
    Node parent( Node root, Node current){
        //在以root为根的二叉树中找结点current的双亲
        Node p;
        if(root == null) return null;
        if(root.leftChild== current||root.leftChild ==current)
            return root;		//root即为current的双亲

        p=parent(root.leftChild,current);//递归在左子树中找

        if (p!=null) return p;
        else return(parent (root.leftChild,current));//递归在右子树中找

    }

    //二叉树相似性判定
    int like(Node t1, Node t2){
        int like1, like2;
        if(t1==null && t2==null) return 1;//t1,t2均空,则相似
        if(t1==null||t2==null)return 0;//t1、t2仅一棵空,则不相似
        like1=like(t1.leftChild,t2.leftChild);//递归判左子树是否相似
        like2=like(t1.leftChild,t2.leftChild);//递归判右子树是否相似
        return (like1 * like2);
    }

    //按树状打印二叉树
    void printTree(Node root, int h){
        if(root == null) return;
        printTree(root.rightChild, h+8);  //先打印右子树
        int i;
        for(i=0;i<h;i++)
            System.out.print(" ");//层次决定结点的左右位置
        System.out.println(root.iData);//输出结点
        printTree(root.leftChild,h+8);  //后打印左子树
    }





}// end class Tree

TreeApp 测试类

package tree;
// tree.java
// demonstrates binary tree
// to run this program: C>java TreeApp
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @author CSDN@日星月云
 * @date 2022/10/25 23:51
 */
public class TreeApp {
    public static void main(String[] args) throws IOException {
        int value;
        Tree theTree = new Tree();
        theTree.insert(50, 1.5);
        theTree.insert(25, 1.2);
        theTree.insert(75, 1.7);
        theTree.insert(12, 1.5);
        theTree.insert(37, 1.2);
        theTree.insert(43, 1.7);
        theTree.insert(30, 1.5);
        theTree.insert(33, 1.2);
        theTree.insert(87, 1.7);
        theTree.insert(93, 1.5);
        theTree.insert(97, 1.5);

        while (true) {
            System.out.print("Enter 0 1 2: ");
            int choice = getInt();
            switch (choice){
                case 1:
                    app1(theTree);
                    break;
                case 2:
                    app2(theTree);
                    break;
                case 0:
                    return;
            }
        }



    }// end main()

    private static void app2(Tree theTree) throws IOException  {
        int value;
        while (true) {
            System.out.print("Enter first letter of ");
            System.out.println("traverseN,levelOrder,countWithPreOrder,printTNWithInOrder(f), break: ");
            System.out.println("leaf(n),treeDepth(d),postTreeDepth(h),parent,like(e),printTree(r) break: ");
            int choice = getChar();
            switch (choice) {
                case 't':
                    System.out.print("Enter type 1, 2 or 3: ");
                    value = getInt();
                    theTree.traverseN(value);
                    break;
                case 'l':
                    theTree.levelOrder(theTree.root);
                    break;
                case 'c':
                    theTree.countWithPreOrder(theTree.root);
                    System.out.println(theTree.count);
                    break;
                case 'f':
                    theTree.printTNWithInOrder(theTree.root);
                    System.out.println();
                    break;
                case 'n':
                    int leafNum = theTree.leaf(theTree.root);
                    System.out.println(leafNum);
                    break;
                case 'd':
                    int depth=1;//初始root的层次
                    theTree.treeDepth(theTree.root,depth);
                    System.out.println(theTree.depth);
                    break;
                case 'h':
                    int height = theTree.postTreeDepth(theTree.root);
                    System.out.println(height);
                    break;
                case 'p':
                    Node parent = theTree.parent(theTree.root, theTree.find(12));
                    System.out.println(parent.iData);
                    break;
                case 'e':
                    int like = theTree.like(theTree.root, theTree.root);
                    System.out.println(like);
                    break;
                case 'r':
                    theTree.printTree(theTree.root,8);
                    break;
                case 'b':
                    return;
                default:
                    System.out.print("Invalid entry\n");
            }
        }




    }

    private static void app1(Tree theTree) throws IOException {
        int value;
        while (true) {
            System.out.print("Enter first letter of ");
            System.out.print("show,insert, find, delete, or traverse, break: ");
            int choice = getChar();
            switch (choice) {
                case 's':
                    theTree.displayTree();
                    break;
                case 'i':
                    System.out.print("Enter value to insert:");
                    value = getInt();
                    theTree.insert(value, value + 0.9);
                    break;

                case 'f':
                    System.out.print("Enter value to find:");
                    value = getInt();
                    Node found = theTree.find(value);
                    if (found != null) {
                        System.out.print("Found: ");
                        found.displayNode();
                        System.out.print("\n");
                    } else
                        System.out.print("Could not find ");
                    System.out.print(value + '\n');
                    break;
                case 'd':
                    System.out.print("Enter value to delete: ");
                    value = getInt();
                    boolean didDelete = theTree.delete(value);
                    if (didDelete) {
                        System.out.print("Deleted " + value + '\n');
                    } else
                        System.out.print("Could not delete ");
                    System.out.print(value + '\n');
                    break;
                case 't':
                    System.out.print("Enter type 1, 2 or 3: ");
                    value = getInt();
                    theTree.traverse(value);
                    break;
                case 'b':
                    return;
                default:
                    System.out.print("Invalid entry\n");
            }// end switch

        }// end while
    }


    public static String getString() throws IOException {
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(isr);
        String s = br.readLine();
        return s;


    }

    public static char getChar() throws IOException {
        String s = getString();
        return s.charAt(0);
    }

    public static int getInt() throws IOException {
        String s = getString();
        return Integer.parseInt(s);
    }

}// end class TreeApp