[数据结构与算法]数据结构4：实现二叉树

前言

最后有实现的代码

二叉树的前中后序遍历

前序遍历

void preOrderTraversal(Node root) {
        if(root == null) return;
        System.out.print(root.val+" ");
        preOrderTraversal(root.left);
        preOrderTraversal(root.right);
    } 

中序遍历

    void inOrderTraversal(Node root) {
        if(root == null) return;
        inOrderTraversal(root.left);
        System.out.print(root.val+" ");
        inOrderTraversal(root.right);
    }

后序遍历

 void postOrderTraversal(Node root) {
        if(root == null) return;
        postOrderTraversal(root.left);
        postOrderTraversal(root.right);
        System.out.print(root.val+" ");
    }

遍历求节点个数

 static int size = 0;
    void getSize1(Node root) {
        if(root == null) return;
        size++;
        getSize1(root.left);
        getSize1(root.right);
    }

子问题求节点个数

int getSize2(Node root) {
        if(root == null) return 0;
        return getSize2(root.left) + getSize2(root.right) + 1;
    }

遍历求叶子节点个数

static int leafSize = 0;
    void getLeafSize1(Node root) {
        if(root == null) return;
        if(root.left == null && root.right == null) {
            leafSize++;
        }
        getLeafSize1(root.left);
        getLeafSize1(root.right);
    }

子问题求叶子节点个数

int getLeafSize2(Node root) {
        if(root == null) {
            return 0;
        }
        if(root.left==null && root.right == null) {
            return 1;
        }
        return getLeafSize2(root.left) + getLeafSize2(root.right);
    }

你们要的代码

BinaryTree.java

//定义一个节点
class Node {
    public char val;
    public Node left;
    public Node right;

    public Node(char val) {
        this.val = val;
    }
}

public class BinaryTree {
    //public Node root;//二叉树的根
        //生成一个二叉树
    public Node createTree() {
        Node A = new Node('A');
        Node B = new Node('B');
        Node C = new Node('C');
        Node D = new Node('D');
        Node E = new Node('E');
        Node F = new Node('F');
        Node G = new Node('G');
        Node H = new Node('H');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
        return A;
    }

    // 前序遍历  
    void preOrderTraversal(Node root) {
        if(root == null) return;
        System.out.print(root.val+" ");
        preOrderTraversal(root.left);
        preOrderTraversal(root.right);
    }

    // 中序遍历
    void inOrderTraversal(Node root) {
        if(root == null) return;
        inOrderTraversal(root.left);
        System.out.print(root.val+" ");
        inOrderTraversal(root.right);
    }


    // 后序遍历
    void postOrderTraversal(Node root) {
        if(root == null) return;
        postOrderTraversal(root.left);
        postOrderTraversal(root.right);
        System.out.print(root.val+" ");
    }

    // 遍历思路-求结点个数
    static int size = 0;
    void getSize1(Node root) {
        if(root == null) return;
        size++;
        getSize1(root.left);
        getSize1(root.right);
    }

    // 子问题思路-求结点个数
    int getSize2(Node root) {
        if(root == null) return 0;
        return getSize2(root.left) + getSize2(root.right) + 1;
    }

    // 遍历思路-求叶子结点个数
    static int leafSize = 0;
    void getLeafSize1(Node root) {
        if(root == null) return;
        if(root.left == null && root.right == null) {
            leafSize++;
        }
        getLeafSize1(root.left);
        getLeafSize1(root.right);
    }

    // 子问题思路-求叶子结点个数
    int getLeafSize2(Node root) {
        if(root == null) {
            return 0;
        }
        if(root.left==null && root.right == null) {
            return 1;
        }
        return getLeafSize2(root.left) + getLeafSize2(root.right);
    }

    // 子问题思路-求第 k 层结点个数
    int getKLevelSize(Node root,int k) {
        if(root == null) return 0;
        if(k == 1) {
            return 1;
        }
        return getKLevelSize(root.left,k-1)
                + getKLevelSize(root.right,k-1);
    }

    // 获取二叉树的高度
    int getHeight(Node root) {
        if (root == null) return 0;

        int leftHight = getHeight(root.left);
        int rightHight = getHeight(root.right);


        return leftHight > rightHight ?
                leftHight+1:rightHight+1;
    }

    Node find(Node root, char val) {
        if(root == null) return null;
        if(root.val == val) return root;
        Node r = find(root.left,val);
        if(r != null) {
            return r;
        }
        r = find(root.right,val);
        if(r != null) {
            return r;
        }
        return null;
    }

}

TestDemo.java

public class TestDemo {
    public static void main(String[] args) {
        //new一个二叉树
        BinaryTree binaryTree = new BinaryTree();

        Node root = binaryTree.createTree();
        //前序遍历
        binaryTree.preOrderTraversal(root);
        System.out.println();
        //中序遍历
        binaryTree.inOrderTraversal(root);
        System.out.println();
        //后序遍历
        binaryTree.postOrderTraversal(root);
        System.out.println();
        //遍历获取节点数
        binaryTree.getSize1(root);
        System.out.println("节点的个数："+BinaryTree.size);
        //子问题获取节点数
        int ret = binaryTree.getSize2(root);
        System.out.println("节点的个数："+ret);
		//树的高度
        System.out.println(binaryTree.getHeight(root));
    }
}