数据结构4：实现二叉树

• 最后有实现的代码
• • 二叉树的前中后序遍历
  • • 前序遍历
    • 中序遍历
    • 后序遍历
  • 遍历求节点个数
  • 子问题求节点个数
  • 遍历求叶子节点个数
  • 子问题求叶子节点个数
  • 子问题思路-求第 k 层结点个数
  • 寻找是否有此节点1
  • 寻找是否有此节点2
• 你们要的代码
• • BinaryTree.java
  • TestDemo.java

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);
    }

    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);
    }

**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;
    }**

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

//定义一个节点
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;
    }

}

import java.util.Scanner;
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);
        //求k层节点数
        Scanner  sc = new Scanner(System.in);
        int  k = sc.nextInt();
        System.out.println(k+"层节点数为："+binaryTree.getKLevelSize(root, k));
        //求树高度
        System.out.println("此树的高度"+binaryTree.getHeight(root));
        
        Scanner fnb = new Scanner(System.in);
        char nd =fnb.next().charAt(0);//
        Node ret2 = binaryTree.find(root,nd);
        System.out.println(ret2.val);
        //寻找节点2
         System.out.println(binaryTree.find(root,'D'));        
    }
}