栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

算法树问题汇总

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

算法树问题汇总

二叉树 定义 二叉树定义
  1. 一个空节点是二叉树(即什么都没有)
  2. 一棵二叉树有一个根节点,可以有左、右子树,而子树本身也是二叉树
平衡二叉树

左右子树高度差不超过1的二叉树

遍历

前序遍历

先遍历根节点,再遍历左子树,再遍历右子树即:
A-B-D-F-G-H-I-E-C

中序遍历

先遍左子树,再遍历根节点,再遍历右子树:
A-B-D-F-G-H-I-E-C

后序遍历

先遍左子树,再遍历右子树,再遍历根节点:
F-H-I-G-D-E-B-C-A

层序遍历

一层一层的遍历:
A-B-C-D-E-F-G-H-I

遍历代码
public class Node {
    private String data;
    private Node leftNode;
    private Node rightNode;

    public Node(String data,Node leftNode,Node rightNode){
         this.data = data;
         this.leftNode = leftNode;
         this.rightNode = rightNode;
    }
    public String getData(){
        return this.data;
    }
    public Node getLeftNode(){
        return this.leftNode;
    }
    public Node getRightNode(){
        return this.rightNode;
    }

}

import java.util.Queue;
import java.util.concurrent.LinkedBlockingQueue;

public class TraverseTool {
    //前序遍历
    public void  preTraverse(Node node){
        System.out.print(node.getData());
        if(node.getLeftNode() != null){
            preTraverse(node.getLeftNode());
        }
        if(node.getRightNode() != null){
            preTraverse(node.getRightNode());
        }
    }
    //中序遍历
    public void midTraverse(Node node){
        if(node.getLeftNode() != null){
            midTraverse(node.getLeftNode());
        }
        System.out.print(node.getData());
        if(node.getRightNode() != null){
            midTraverse(node.getRightNode());
        }
    }
    //后续遍历
    public void postTraverse(Node node){
        if(node.getLeftNode() != null){
            postTraverse(node.getLeftNode());
        }
        if(node.getRightNode() != null){
            postTraverse(node.getRightNode());
        }
        System.out.print(node.getData());
    }
    //层序遍历,利用队列先进先出的功能,每一次都先遍历上一层的子节点
    public void seqTraverse(Node node){
        Queue queue  = new LinkedBlockingQueue<>();
        queue.add(node);
        Node nextNode;
        while (!queue.isEmpty()){
            nextNode = queue.remove();
            if(nextNode.getLeftNode() !=null){
                queue.add(nextNode.getLeftNode());
            }
            if(nextNode.getRightNode() !=null){
                queue.add(nextNode.getRightNode());
            }
            System.out.print(nextNode.getData());
        }
    }
}
把任意树转化为二叉树

用以下方法可以将任意树转化成二叉树,且可以恢复到之前的树

  1. 对每一个节点,将其的第一棵子树变为左子树,如图中的B
  2. 将上述产生的左子树节点右边的兄弟树变为该左子树节点的右子树如C,D
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/966760.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号