数据结构与算法(十)树

树形结构的相关术语

  • 结点:树里面的元素
  • 父子关系:结点之间相连的边
  • 子树:当结点大于1时,其余结点分为的互不相交的集合
  • 度:一个结点拥有的子树数量称为结点的度
  • 叶子:度为0的结点
  • 孩子:结点的子树的根节点
  • 双亲:
  • 兄弟:同一个双亲结点
  • 森林:由N个互不相交的树构成深林
  • 结点的高度:结点到叶子结点的最长路径
  • 结点的深度:根结点到该结点的边的个数
  • 结点的层度:结点的深度+1
  • 树的高度:根节点的高度

二叉树.png

满二叉树:除叶子结点外,其他的结点都有两个子结点
完全二叉树:除去最后一层外,其余层为满二叉树状态,并且最后一层的叶子结点都往左排列
完全二叉树是满二叉树的一个子集

实现方式

  • 数组:推导公式,当前结点:i 两个子结点:i2 i2+1 ,适用于满二叉树和完全二叉树
  • 链表:left right

树的遍历

  • 前序遍历 根(输出) 左 右
  • 中序遍历 左 根(输出) 右
  • 后序遍历 左 右 根(输出)

根(输出):表示遇到根节点则输出

代码实现

public class MyTree<E> {

    public void print(TreeNode<E> treeNode) {
        System.out.print(treeNode.getData());
    }

    //前序遍历 根 左 右
    public void pre(TreeNode<E> treeNode) {
        print(treeNode);
        if (treeNode.getLeftNode() != null)
            pre(treeNode.getLeftNode());
        if (treeNode.getRightNode() != null)
            pre(treeNode.getRightNode());
    }

    //中序遍历 左 根 右
    public void mid(TreeNode<E> treeNode) {
        if (treeNode.getLeftNode() != null) {
            mid(treeNode.getLeftNode());
        }
        print(treeNode);
        if (treeNode.getRightNode() != null)
            mid(treeNode.getRightNode());
    }

    //后序遍历 左 右 根
    public void post(TreeNode<E> treeNode) {
        if (treeNode.getLeftNode() != null) {
            post(treeNode.getLeftNode());
        }
        if (treeNode.getRightNode() != null) {
            post(treeNode.getRightNode());
        }
        print(treeNode);
    }

    //层序遍历
    public void level(TreeNode<E> treeNode) {
        MyQueue<TreeNode<E>> queue = new MyQueue<>(20);
        levelRecursion(queue, treeNode);
    }

    private void levelRecursion(MyQueue<TreeNode<E>> queue, TreeNode<E> treeNode) {
        print(treeNode);
        if (treeNode.getLeftNode() != null) {
            queue.push(treeNode.getLeftNode());
        }
        if (treeNode.getRightNode() != null) {
            queue.push(treeNode.getRightNode());
        }
        while (!queue.isEmpty()) {
            levelRecursion(queue, queue.pop());
        }
    }
}
#  

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×