数据结构(三)树的入门

树

树是n(n>0)个结点的有限集合,n=0时称为空树,在任意的一棵非空树中.在任意一棵非空树中

1. 有且仅有一个特定的称为根(Root)的结点
2. 当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2...其中每一个集合本身又是一棵树,并称为根的子树 image

• 结点拥有的子树数称为结点的度
• 度为0的结点称为叶子结点或终端点
• 度不为0的结点称为非终端结点或分支结点
• 根结点以外,分支结点也称为内部结点
• 树的度是树内各结点的度的最大值 image
• 树的层次和深度 image

1. 树的存储结构

1. 双亲表示法(用处很少)

image

2. 孩子表示法(主要使用)

image

3. 双亲孩子表示法(用处很少)

把每个结点的孩子结点排列起来，以单链表作为存储结构，
则n个结点有n个孩子链表，如果是叶子结点则此单链表为空，
然后n个头指针又组成一个线性表，采用顺序存储结构，存放在一个一维数组中

image

4. 孩子兄弟表示法

孩子兄弟表示法为每个节点设计三个域：
一个数据域，一个该节点的第一个孩子节点域，一个该节点的下一个节点的兄弟指针域

image

3.二叉树

二叉树是n(n>0)个结点的有限集合,该集合或这为空集(称为空二叉树),或者由一个根节点和俩棵互不相交的,分别称为根结点的左子树和又子树的二叉树组成 image

1. 二叉树的存储结构

1. 顺序存储(用的很少)

   
   image

2. 链式存储

   
   image
   

   创建一个二叉树

public class BinarayTree {

    /**
     * 根结点
     */
    public Node<String> root;

    public BinarayTree(String data) {
        root = new Node<>(data, null, null);
    }

    /**
     * 生成二叉树
     */
    public void createTree() {
        Node<String> nodeB = new Node<>("B", null, null);
        Node<String> nodeC = new Node<>("C", null, null);
        Node<String> nodeD = new Node<>("D", null, null);
        Node<String> nodeE = new Node<>("E", null, null);
        Node<String> nodeF = new Node<>("F", null, null);
        Node<String> nodeG = new Node<>("G", null, null);
        Node<String> nodeH = new Node<>("H", null, null);
        Node<String> nodeI = new Node<>("I", null, null);
        Node<String> nodeJ = new Node<>("J", null, null);
        root.leftChild = nodeB;
        root.rightChild = nodeC;
        nodeB.leftChild = nodeD;
        nodeC.leftChild = nodeE;
        nodeC.rightChild = nodeF;
        nodeD.leftChild = nodeG;
        nodeD.rightChild = nodeH;
        nodeH.leftChild = nodeI;
        nodeE.rightChild = nodeJ;
    }
    
        /**
     * 结点
     *
     * @param <T>
     */
    public class Node<T> {
        T data;
        Node<T> leftChild;
        Node<T> rightChild;

        public Node(T data, Node<T> leftChild, Node<T> rightChild) {
            this.data = data;
            this.leftChild = leftChild;
            this.rightChild = rightChild;
        }
    }

2. 二叉树的遍历

1. 前序(DLR)
   规则是若二叉树为空，则空操作返回，否则先访问跟结点，然后前序遍历左子树，再前序遍历右子树

   
   image

        BinarayTree tree = new BinarayTree("A");
        tree.createTree();
        tree.preOrderTraverse(tree.root);

    /**
     * 前序访问树的所有结点
     *
     * @param root
     */
    public void preOrderTraverse(Node root) {
        if (root == null) {
            return;
        }
        System.out.println("mid:" + root.data);
        preOrderTraverse(root.leftChild);
        preOrderTraverse(root.rightChild);
    }

2. 中序(LDR)
   若树为空,则空操作返回,否则从根结点开始(注意并不是先访问根结点),中序便利根结点的左子树,然后是访问根结点,最后中序遍历右子树
   
   LDR(先取左边,再取中间,最后取右边) image

    /**
     * 中序访问树的所有结点
     *
     * @param root
     */
    public void midOrderTraverse(Node root) {
        if (root == null) {
            return;
        }
        midOrderTraverse(root.leftChild);
        System.out.println("mid:" + root.data);
        midOrderTraverse(root.rightChild);
    }

        BinarayTree tree = new BinarayTree("A");
        tree.createTree();
        tree.midOrderTraverse(tree.root);

取出后为GDHBAEICF

3. 后序(LRD)
   

   规则是若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点 image

    /**
     * 后序访问树的所有结点
     *
     * @param root
     */
    public void postOrderTraverse(Node root) {
        if (root == null) {
            return;
        }
        postOrderTraverse(root.leftChild);
        postOrderTraverse(root.rightChild);
        System.out.println("mid:" + root.data);
    }

        BinarayTree tree = new BinarayTree("A");
        tree.createTree();
        tree.postOrderTraverse(tree.root);