精华内容
下载资源
问答
  • (1)图是由顶点集合以及顶点间的关系集合组成的一种数据结构。  Graph = (V,E) V是顶点的又穷非空集合;E是顶点之间关系的有穷集合,也叫边集合。 (2)有向图:顶点对是有序的;无向图:顶点对是无序的。 (3...

     转自   《大话数据结构》

    【1】图的基本概念

    (1)图是由顶点集合以及顶点间的关系集合组成的一种数据结构。

      Graph = (V,E)  V是顶点的又穷非空集合;E是顶点之间关系的有穷集合,也叫边集合。

    (2)有向图:顶点对<x,y>是有序的;无向图:顶点对<x,y>是无序的。

    (3)无向边:若顶点Vi到Vj之间的边没有方向,则称这条边为无向边,用无序偶对(Vi,Vj)来表示。

      如果图中任意两个顶点时间的边都是无向边,则称该图为无向图:

      由于是无向图,所以连接顶点A与D的边,可以表示为无序对(A,D),也可以写成(D,A)

      对于如上无向图来说,G=(V,{E}) 其中顶点集合V={A,B,C,D};边集合E={(A,B),(B,C),(C,D),(D,A),(A,C)}

      有向边:若从顶点Vi到Vj的边有方向,则称这条边为有向边,也称为弧。

      用有序偶<Vi,Vj>来表示,Vi称为弧尾,Vj称为弧头。

      如果图中任意两个顶点之间的边都是有向边,则称该图为有向图:

      连接顶点A到D的有向边就是弧,A是弧尾,D是弧头,<A,D>表示弧。注意不能写成<D,A>。

      对于如上有向图来说,G=(V,{E})其中顶点集合V={A,B,C,D};弧集合E={<A,D>,<B,A>,<C,A>,<B,C>}

    (4)完全无向图:若有n个顶点的无向图有n(n-1)/2 条边, 则此图为完全无向图。

      完全有向图:有n个顶点的有向图有n(n-1)条边, 则此图为完全有向图。

    (5)树中根节点到任意节点的路径是唯一的,但是图中顶点与顶点之间的路径却不是唯一的。

      路径的长度是路径上的边或弧的数目。

    (6)如果对于图中任意两个顶点都是连通的,则成G是连通图。

    (7)图按照边或弧的多少分稀疏图和稠密图。 如果任意两个顶点之间都存在边叫完全图,有向的叫有向图。

       若无重复的边或顶点到自身的边则叫简单图。

    (8)图中顶点之间有邻接点。无向图顶点的边数叫做度。有向图顶点分为入度和出度。

    (9)图上的边和弧上带权则称为网。

    (10)有向的连通图称为强连通图。

    【2】图的存储结构

    关于图的存储结构,可以分为以下五种:

    (1) 邻接矩阵

    图的邻接矩阵存储方式是用两个数组来表示图:

    一个一维数组存储图中顶点信息;

    一个二维数组(称为邻接矩阵)存储图中边或弧的信息

    (2) 邻接表

    邻接矩阵是一种不错的图存储结构。 但是:对于边树相对顶点较少的图,这种结构是存在存储空间的极大浪费的。

    因此我们考虑先进一步,使用邻接表存储,关于邻接表的处理办法是这样:

    下图是一个无向图的邻接表结构:

    对于有向图而言,为了更便于确定顶点的入度(或以顶点为弧头的弧)。

    我们可以建立一个有向图的逆邻接表。如下图所示:

    而对于有权值的网图,可以在边表节点定义中再增加一个weight的数据域,存储权值信息即可。 如下图所示:

    那么,有了这些结构的图,下面定义代码如下:

    (3) 十字链表

    对于有向图而言,邻接表也是有缺陷的。

    试想想哈,关心了出度问题,想了解入度问题就必须把整个图遍历才能知道。

    反之,逆邻接表解决了入度问题却不了解出度的情况。

    那是否可以将邻接表和逆邻接表结合起来呢?答案是肯定的。

    这就是所谓的存储结构:十字链表。其详解如下图:

    (4) 邻接多重表

    有向图的优化存储结构为十字链表。

    对于无向图的邻接表,有没有问题呢?如果我们要删除无向图中的某一条边时?

    那也就意味着必须找到这条边的两个边节点并进行操作。其实还是比较麻烦的。比如下图:

    欲删除上图中的(V0,V2)这条边,需要对邻接表结构中右边表的阴影两个节点进行删除。

    仿照十字链表的方式,对边表节点的结构进行改造如下:

    (5)边集数组

    边集数组侧重于对边依次进行处理的操作,而不适合对顶点相关的操作。

    关于边集数组详解如下:

    【3】图的遍历

    图的遍历图和树的遍历类似,那就是从图中某一顶点出发访遍图中其余顶点,且使每一个顶点仅被访问一次,这个过程就叫做图的遍历。

    对于图的遍历来说,如何避免因回路陷入死循环,就需要科学地设计遍历方案,通过有两种遍历次序方案:深度优先遍历和广度优先遍历。

    (1) 深度优先遍历

    深度优先遍历(Depth_First_Search),也称为深度优先搜索,简称DFS。

    为了更好的理解深度优先遍历。请看下面的图解:

    其实根据遍历过程转换为右图后,可以看到其实相当于一棵树的前序遍历。

    /* 
    对邻接矩阵表示的图进行深度遍历 
    */  
    typedef int Boolean;  
    Boolean visited[MAX];  
      
    void DFS(MGraph G,int i)  
    {  
        int j;  
          
        visited[i] = TRUE;  
        printf("%c",G.vexs[i]);  
        for(j=0;j<G.numVertexes;j++)  
        {  
            if(G.arc[i][j] == 1 && !visited[j])  
            {  
                DFS(G,j);  
            }  
        }  
    }  
      
    void DFSTraverse(MGraph G)  
    {  
        int i;  
        for(i=0;i<G.numVertexes;i++)  
        {  
            visited[i] = FALSE;  
        }  
        for(i=0;i<G.numVertexes;i++)  
        {  
            if(!visited[i])  
            {  
                DFS(G,i);  
            }  
        }  
    }  


    (2)广度优先遍历

    广度优先遍历(Breadth_First_Search),又称为广度优先搜索,简称BFS。

    深度遍历类似树的前序遍历,广度优先遍历类似于树的层序遍历。

    /* 
    图的邻接矩阵表示 
    */  
    typedef char VertexType;  
    typedef int EdgeType;  
    #define MAXVEX 100  
    #define INFINITY 65535  
      
    typedef struct   
    {  
        VertexType vexs[MAXVEX];  
        EdgeType arc[MAXVEX][MAXVEX];  
        int numVertexes,numEdges;  
    }MGraph; 

    /* 
    邻接矩阵广度优先遍历 
    */  
    void BFSTraverse(MGraph G)  
    {  
        int i,j;  
        Queue Q;  
        for(i=0;i<G.numVertexes;i++)  
        {  
            visited[i] = FALSE;  
        }  
        InitQueue(&Q);  
        for(i=0;i<G.numVertexes;i++)  
        {  
            if(!visited[i])  
            {  
                visited[i] = TRUE;  
                printf("%c",G.vexs[i]);  
                //将此点入队列  
                EnQueue(&Q,i);  
                while(!QueueEmpty(Q))  
                {  
                    //将队列中元素出队列,并赋值给i  
                    DeQueue(&Q,&i);  
                    for(j=0;j<G.numVertexes;j++)  
                    {  
                        if(G.arc[i][j] == 1 && !visited[j])  
                        {  
                            visited[j]=TRUE;  
                            printf("%c",G.vexs[j]);  
                            EnQueue(&Q,j);  
                        }  
                    }  
                }  
            }  
        }  
    }  


    展开全文
  • 数据结构算法】常见数据结构及基本操作

    万次阅读 多人点赞 2019-06-16 21:42:44
    数据结构及基本操作+排序算法+查找算法目录1.数据结构算法常见概念2.数据逻辑结构2.1线性结构2.2树形结构2.3图形结构2.4集合结构3.排序算法冒泡排序简单选择排序直接插入排序希尔排序堆排序归并排序快速排序4.查找...


    总结《大话数据结构》和《C++Primer》,文后附《大话数据结构》和《C++Primer》第五版下载链接,本文相关代码均由C++编写。

    1.数据结构与算法常见概念:

    数据:是描述客观事物的符号,是计算机中可以操作的对象,是能被计算机识别,并输入给计算机处理的符号集合。
    数据元素:是组成数据的,有一定意义的基本单位,在计算机中通常作为整体处理,也被称为记录。
    数据结构:是相互之间存在一种或多种特定关系的数据元素的集合。
    数据结构的逻辑结构:数据对象中数据元素之间的相互关系,分为线性结构、树形结构、图形结构以及集合结构。
    数据结构的物理结构:数据的逻辑结构在计算机中的存储形式,分为顺序存储和链式存储(不连续存储)。

    算法:解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表示一个或多个操作。
    算法五个基本特性:输入、输出、有穷性、确定性和可行性。
    算法时间复杂度O(n):常数阶、线性阶、平方阶、对数阶、立方阶、nlogn阶、指数阶。
    耗时排序:O(1)<O(logn)<O(n)<O(nlgn)<O(x2x^{2})<O(x3x^{3})<O(2n2^{n})<O(n!)<O(nnn^{n})

    2.数据结构:

    2.1线性结构:

    基本概念

    线性结构:数据元素之间是一对一的关系。
    在这里插入图片描述
    线性表:零个或多个数据元素的有限序列。
    区分数组长度与线性表的长度
            数组长度是指存放线性表的存储空间的长度,存储分配后这个值是不变的。
            线性表的长度是线性表中数据元素的个数,随着线性表的插入与删除,这个值是在变换的。
    在这里插入图片描述线性表的顺序存储:用一段连续的存储单元依次存储线性表的数据元素。(通常使用一维数组实现顺序存储结构)
    线性表的链式存储:除了存储本身的信息之外,还需存储一个指示后继的信息。
    顺序存储的插入步骤:
            a.线性表长度大于等于数组长度,抛出异常
            b.插入位置不合适,抛出异常(判断插入位置与0和最大值的大小)
            c.从最后一个元素开始向前变量,将它们都向后移动一位
            d.将要插入的元素填入指定位置
            e.表长加一
    顺序存储的删除步骤:
            a.线性表是否为空
            b.删除位置不合适,抛出异常(判断插入位置与0和最大值的大小)
            c.取出删除元素
            d.从删除元素的位置遍历到最后一个元素位置,将它们前移一位
            e.表长减一
    链式存储的插入与删除在链表中介绍
    顺序存储和链式存储使用场景:如果频繁使用查找,很少进行插入和删除,易采用顺序存储。如果需要频繁插入和删除,易采用链式存储。

    数组

    数组及基本操作

    字符串

    字符串及基本操作

    队列

    队列及基本操作

    栈及基本操作

    链表

    链表及基本操作

    2.2树形结构

    基本概念

    树形结构:数据元素之间存在一对多的层次关系
    在这里插入图片描述
    :结点拥有的子树数
    叶结点/终端结点:度为0的结点
    树的度:树内各结点的度的最大值
    在这里插入图片描述
    结点间关系图
    在这里插入图片描述
    树的深度/高度:树中结点的最大层次
    在这里插入图片描述
    二叉树:是N(N>=0)个结点的有限集合,该集合或为空集(空二叉树),或者由一个根结点和两颗互不相交的、分别称为根结点的左子树和右子树的二叉树组成。
    在这里插入图片描述
    满二叉树:所有分支结点都存在左子树和右子树,并且所有非叶子节点都在同一层上
    在这里插入图片描述
    完全二叉树:对一棵具有n个结点的二叉树按层序编号,如果编号i(1<= i <= n)的结点与同样深度的满二叉树中的编号i 的结点在二叉树的位置完全相同,则这棵二叉树称为完全二叉树
    在这里插入图片描述
    二叉树的特点

    1. 每个结点最多只有两颗子树
    2. 左右子树是有顺序的
    3. 即使某结点只有一颗子树,也要区分是右子树还是左子树

    二叉树的性质

    1. 在二叉树的第i层上至多有2i12^{i-1}个结点(i>=1)
    2. 深度为k的二叉树至多有2k2^{k}-1个结点(k>=1)
    3. 对任何一棵二叉树T,如果其终端结点数为n0n_{0},此二叉树至多有2k2^{k}-1个结点
    4. 具有n个结点的完全二叉树的深度为[log2log_{2}n]+1([x]表示不大于x的最大整数)
    5. n个结点的完全二叉树按层序编号(参考上图),对任意一个结点i有:
      a. 如果i=1,则i是二叉树的根,如果i>1,其双亲是[i/2]
      b. 如果2i>n,则结点i无左孩子
      c. 如果2i+1>n,则结点i无右孩子(否则其右孩子为2i+1)

    二叉树的递归遍历

    二叉树的遍历(递归)

    二叉树的非递归遍历

    未完待续……

    2.3图形结构

    图形结构:数据元素的多对多的关系
    在这里插入图片描述

    2.4集合结构

    集合结构:数据元素除了同属于一个集合外,它们之间没有其他关系。
    在这里插入图片描述

    3.资源链接

    《大话数据结构》+《C++Primer》PDF百度云盘链接
    提取码:6a7b

    展开全文
  • 树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点: 有一个特殊的结点叫根节点,...

    定义

    树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:
    有一个特殊的结点叫根节点,根节点没有 前驱节点。
    除根节点外,其余节点被分为M(M>0)个互不相交的集合T1,T2…Tm,其中每一个集合Ti(1<=i<=m)有是一颗与树类似的子树,每颗子树的根节点有且只有一个前驱,可以有0个或者多个后继。
    树是递归定义的。

    重要概念

    节点的度:一个节点含有的子树的个数称为该节点的度
    树的度:一棵树中,最大的节点的度称为树的度
    叶子节点或终端节点:度为0的节点称为叶节点
    双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点
    孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点
    根结点:一棵树中,没有双亲结点的结点
    节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推。
    树的高度或深度:树中节点的最大层次
    非终端节点或分支节点:度不为0的节点
    兄弟节点:具有相同父节点的节点互称为兄弟节点
    堂兄弟节点:双亲在同一层的节点互为堂兄弟
    节点的祖先:从根到该节点所经分支上的所有节点
    子孙:以某节点为根的子树中任一节点都称为该节点的子孙
    森林:由m(m>=0)棵互不相交的树的集合称为森林

    树的表示形式

    树有多种表示方式:双亲表示法、孩子表示法、孩子兄弟表示法等。
    孩子兄弟表示法:

    class Node{
    	int value; //树中存储的数据
    	Node firstChild;//第一个孩子引用
    	Node nextBrother;//下一个兄弟引用
    }
    

    在这里插入图片描述

    二叉树

    一棵二叉树是结点的一个有限集合,该集合或者为空,或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。
    二叉树的特点:
    每个结点最多有两棵子树,即二叉树不存在度大于 2 的结点
    二叉树的子树有左右之分,其子树的次序不能颠倒,因此二叉树是有序树

    二叉树的基本形态

    在这里插入图片描述
    从左往右依次是:空树、只有根节点的二叉树、节点只有左子树、节点只有右子树、节点的左右子树均存在,一般二叉树都是由上述基本形态结合而形成的。

    满二叉树

    满二叉树: 一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为K,且结点总数是2k12^k-1 ,则它就是满二叉树。
    在这里插入图片描述

    完全二叉树

    完全二叉树: 完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
    在这里插入图片描述

    二叉树的性质

    若规定根节点的层数为1,则一棵非空二叉树的第i层上最多有2i12^{i-1}(i>0)个结点
    若规定只有根节点的二叉树的深度为1,则深度为K的二叉树的最大结点数是2k12^k-1(k>=0)

    二叉树的基础面试题

    1. 二叉树的前序遍历题目链接
      前中后序的二叉树遍历采用递归的方式来写有一个模板,只需要改变几行代码的顺序就好。
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
     import java.util.LinkedList;
    import java.util.List;
    class Solution {
        static List<Integer> list = new LinkedList();
        public List<Integer> preorderTraversal(TreeNode root) {
    
            if (root == null){
                return new ArrayList<>();
            }
            List<Integer> left = preorderTraversal(root.left);
            List<Integer> right = preorderTraversal(root.right);
    
            List<Integer> list = new ArrayList<>();
             list.add(root.val);
            list.addAll(left);
            list.addAll(right);
           
            return list;
        }
    }
    

    方法二:

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
    
        List<Integer> result;
    
        public void traversalNode(TreeNode node) {
            if(node != null) {
                result.add(node.val);
                if(node.left != null) traversalNode(node.left);
                if(node.right != null) traversalNode(node.right);
            }
            return;
        }
    
        public List<Integer> preorderTraversal(TreeNode root) {
            result = new ArrayList<Integer>(); 
            traversalNode(root);
            return result;    
        }
    }
    
    1. 二叉树的中序遍历题目链接
    
    class Solution {
        public List<Integer> inorderTraversal(TreeNode root) {
    
            if (root == null){
                return new ArrayList<>();
            }
            List<Integer> left = inorderTraversal(root.left);
            List<Integer> right = inorderTraversal(root.right);
    
            List<Integer> list = new ArrayList<>();
            list.addAll(left);
             list.add(root.val);
            list.addAll(right);
           return list;
        }
    }
    
    1. 二叉树的后序遍历题目链接
    class Solution {
        public List<Integer> postorderTraversal(TreeNode root) {
    
           
            if (root == null){
                return new ArrayList<>();
            }
            List<Integer> left = postorderTraversal(root.left);
            List<Integer> right = postorderTraversal(root.right);
    
            List<Integer> list = new ArrayList<>();
            list.addAll(left);
             
            list.addAll(right);
            list.add(root.val);
           return list;
       
        }
    }
    
    1. 检查两棵树是否相同题目链接
    class Solution {
        public boolean isSameTree(TreeNode p, TreeNode q) {
            if (p == null && q == null){
                return true;
            }else if(p == null || q == null){
                return false;
            }else if(p.val != q.val){
                return false;
            }else{
                return p.val == q.val && isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
            }
            
        }
    }
    

    方法二:

     public static boolean isSameTree(TreeNode p, TreeNode q) {
            if (p == null && q == null) {
                return true;
            }
    
            if (p == null || q == null) {
                return false;
            }
    
            return p.val == q.val
                    && isSameTree(p.left, q.left)
                    && isSameTree(p.right, q.right);
        }
    
    1. 另一棵树的子树题目链接
    class Solution {
        
        public static boolean isSameTree(TreeNode p, TreeNode q) {
            if (p == null && q == null) {
                return true;
            }
    
            if (p == null || q == null) {
                return false;
            }
    
            return p.val == q.val
                    && isSameTree(p.left, q.left)
                    && isSameTree(p.right, q.right);
        }
    
        public boolean isSubtree(TreeNode s, TreeNode t) {
            if (s == null) {
                return false;
            }
    
            if (isSameTree(s, t)) {
                return true;
            }
    
            if (isSubtree(s.left, t)) {
                return true;
            }
    
            return isSubtree(s.right, t);
        }
    }
    
    1. 二叉树最大深度题目链接
    class Solution {
         public static int maxDepth(TreeNode root){
              if (root == null){
                //根不存在
                return 0;
            }
    
            int left = maxDepth(root.left);
            int right = maxDepth(root.right);
            return Math.max(left,right)+1;
         }
    }
    
    class Solution {
         public static int maxDepth(TreeNode root){
            if (root == null) {
                return 0;
            }
    
            return Integer.max(maxDepth(root.left),maxDepth(root.right)) + 1;
         }
    }
    
    1. 判断一颗二叉树是否是平衡二叉树题目链接
    class Solution {
       public static int getHeight(TreeNode root) {
            if (root == null) {
                return 0;
            }
    
            return Integer.max(getHeight(root.left), getHeight(root.right)) + 1;
        }
    
        public boolean isBalanced(TreeNode root) {
            if (root == null) {
                return true;
            }
    
            boolean isLeftBalance = isBalanced(root.left);
            if (!isLeftBalance) {
                return false;
            }
    
            boolean isRightBalance = isBalanced(root.right);
            if (!isRightBalance) {
                return false;
            }
    
            int leftHeight = getHeight(root.left);
            int rightHeight = getHeight(root.right);
            int diff = leftHeight - rightHeight;
            return diff >= -1 && diff <= 1;
        }
    }
    
    1. 对称二叉树 题目链接
    class Solution {
        private static boolean isMirror(TreeNode p, TreeNode q) {
            if (p == null && q == null) {
                return true;
            }
    
            if (p == null || q == null) {
                return false;
            }
    
            return p.val == q.val
                    && isMirror(p.left, q.right)
                    && isMirror(p.right, q.left);
        }
    
        public boolean isSymmetric(TreeNode root) {
            if (root == null) {
                return true;
            }
            return isMirror(root.left, root.right);
        }
    }
    

    二叉树的进阶面试题

    1. 二叉树的构建及遍历题目链接
    
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    import java.util.Scanner;
    public class Main {
        static class TreeNode {
            char val;
            TreeNode left;
            TreeNode right;
    
            public TreeNode(char rootValue) {
                this.val = rootValue;
            }
    
            @Override
            public String toString() {
                return "TreeNode{" +
                        "val=" + val +
                        '}';
            }
        }
    
        private static int index;
        private static TreeNode buildTree3(char[] preorder) {
            if (index >= preorder.length) {
                return null;
            }
    
            char rootValue = preorder[index++];
            if ( rootValue == '#') {
                return null;
            }
    
            TreeNode root = new TreeNode(rootValue);
            root.left = buildTree3(preorder);
            root.right = buildTree3(preorder);
    
            return root;
        }
    
        private static TreeNode buildTree2(List<Character> preorder) {
            if (preorder.isEmpty()) {
                return null;
            }
    
            char rootValue = preorder.remove(0);
            if (rootValue == '#') {
                return null;
            }
    
            TreeNode root = new TreeNode(rootValue);
            root.left = buildTree2(preorder);
            root.right = buildTree2(preorder);
    
            return root;
        }
    
        static class ReturnType {
            TreeNode builtRoot;
            int used;
        }
    
        private static ReturnType buildTree(List<Character> preorder) {
            if (preorder.isEmpty()) {
                ReturnType rt = new ReturnType();
                rt.builtRoot = null;
                rt.used = 0;
                return rt;
            }
    
            // 1. 获取根的值
            char rootValue = preorder.get(0);
            if (rootValue == '#') {
                ReturnType rt = new ReturnType();
                rt.builtRoot = null;
                rt.used = 1;
                return rt;
    
            }
            TreeNode root = new TreeNode(rootValue);
    
            // 2. 构建左子树
            List<Character> leftSubTreePreorder = preorder.subList(1, preorder.size());
            ReturnType leftReturn = buildTree(leftSubTreePreorder);
            root.left = leftReturn.builtRoot;
    
            // 3. 构建右子树
            List<Character> rightSubTreePreorder = preorder.subList(1 + leftReturn.used, preorder.size());
            ReturnType rightReturn = buildTree(rightSubTreePreorder);
            root.right = rightReturn.builtRoot;
    
            // 4. 返回我们的两个信息
            ReturnType rt = new ReturnType();
            rt.builtRoot = root;
            rt.used = 1 + leftReturn.used + rightReturn.used;
            return rt;
        }
    
        private static void inorder(TreeNode root) {
            if (root == null) {
                return;
            }
    
            inorder(root.left);
            System.out.print(root.val + " ");
            inorder(root.right);
        }
    
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            while (scanner.hasNextLine()) {
                String s = scanner.nextLine();
                char[] chars = s.toCharArray();
    
                index = 0;
                TreeNode root = buildTree3(chars);
    
                inorder(root);
    
                System.out.println();
            }
        }
    }
    
    
    1. 二叉树的分层遍历题目链接
     public static void levelOrder(TreeNode root) {
    
            if (root == null) {
                return;
            }
    
            Queue<TreeNode> queue = new LinkedList<>();
            Queue<Integer> levelQueue = new LinkedList<>();
            queue.add(root);
            levelQueue.add(0);
    
            while (!queue.isEmpty()) {
                TreeNode node = queue.remove();
                int level = levelQueue.remove();
                System.out.println(level + ": " + node.val);
    
                if (node.left != null) {
                    queue.add(node.left);
                    levelQueue.add(level + 1);
                }
    
                if (node.right != null) {
                    queue.add(node.right);
                    levelQueue.add(level + 1);
                }
            }
        }
    
    public List<List<Integer>> levelOrder(TreeNode root) {
            List<List<Integer>> list = new ArrayList<>();
    
            if (root == null) {
                return null;
            }
    
            Queue<TreeNode> queue = new LinkedList<>();
            Queue<Integer> levelQueue = new LinkedList<>();
            queue.add(root);
            levelQueue.add(0);
    
            int lastLevel = -1;
            while (!queue.isEmpty()) {
                TreeNode node = queue.remove();
                int level = levelQueue.remove();
                if (lastLevel != level){
                    list.add(new ArrayList<>());
                }
                lastLevel  = level;
                List<Integer> rowList = list.get(level);
    
                rowList.add(node.val);
                if (node.left != null) {
                    queue.add(node.left);
                    levelQueue.add(level + 1);
                }
    
                if (node.right != null) {
                    queue.add(node.right);
                    levelQueue.add(level + 1);
                }
            }
            return list;
        }
    
    1. 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先题目链接
    class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if (p == root || q == root) {
                return root;
            }
    
            boolean pInLeft = containsNode(root.left, p);
            boolean qInLeft = containsNode(root.left, q);
    
            if (pInLeft && !qInLeft) {
                return root;
            }
    
            if (!pInLeft && qInLeft) {
                return root;
            }
    
            if (pInLeft) {
                return lowestCommonAncestor(root.left, p, q);
            } else {
                return lowestCommonAncestor(root.right, p, q);
            }
        }
    
        private static boolean containsNode(TreeNode root, TreeNode p) {
            if (root == null) {
                return false;
            }
    
            if (root == p) {
                return true;
            }
    
            if (containsNode(root.left, p)) {
                return true;
            }
    
            return containsNode(root.right, p);
        }
    }
    
    1. 二叉树搜索树转换成排序双向链表题目链接
    import java.util.ArrayList;
    public class Solution {
        public TreeNode Convert(TreeNode pRootOfTree) {
            if (pRootOfTree==null)
                return null;
           ArrayList&lt;TreeNode&gt; list=new ArrayList&lt;&gt;();
           Convert(list,pRootOfTree);
           return Convert(list);
        }
    
        public void Convert(ArrayList&lt;TreeNode&gt;list,TreeNode root){
            if (root!=null){
                Convert(list,root.left);
                list.add(root);
                Convert(list,root.right);
            }
        }
    
        public TreeNode Convert(ArrayList&lt;TreeNode&gt; list){
            TreeNode head=list.get(0);
            TreeNode cur=head;
            for (int i=1;i&lt;list.size();++i){
                TreeNode node=list.get(i);
                node.left=cur;
                cur.right=node;
                cur=node;
            }
            return head;
        }
    }
    
    1. 根据一棵树的前序遍历与中序遍历构造二叉树题目链接
    public TreeNode buildTree(int[] preorder, int[] inorder) {
            if (preorder.length == 0) {
                return null;
            }
            int rootValue = preorder[0];
            TreeNode root = new TreeNode(rootValue);
    
            int leftSize = 0;
            for (int i = 0; i < inorder.length; i++) {
                if (inorder[i] == rootValue) {
                    leftSize = i;
                }
            }
    
            int[] leftPreorder = Arrays.copyOfRange(preorder, 1, 1 + leftSize);
            int[] leftInorder = Arrays.copyOfRange(inorder, 0, leftSize);
            root.left = buildTree(leftPreorder, leftInorder);
    
            int[] rightPreorder = Arrays.copyOfRange(preorder, 1 + leftSize, preorder.length);
            int[] rightInorder = Arrays.copyOfRange(inorder, leftSize + 1, inorder.length);
            root.right = buildTree(rightPreorder, rightInorder);
    
            return root;
        }
    
    
    1. 从中序和后序序列构建二叉树题目链接
     public TreeNode buildTree(int[] inorder, int[] postorder) {
            if( inorder.length == 0 && postorder.length == 0){
                return null;
            }
            int rootValue = postorder[postorder.length - 1];
            TreeNode root = new TreeNode(rootValue);
            int leftSize = 0;
            for(int i = 0 ;i < inorder.length;i++){
                if(inorder[i] == rootValue){
                    leftSize = i;
                }
            }
            int []leftInorder = Arrays.copyOfRange(inorder,0,leftSize);
            int []leftPostOrder = Arrays.copyOfRange(postorder,0,leftSize);
            root.left = buildTree1(leftInorder,leftPostOrder);
    
            int []rightInorder = Arrays.copyOfRange(inorder,1+leftSize,inorder.length);
            int []rightPostOrder = Arrays.copyOfRange(postorder,leftSize,postorder.length-1);
            root.right = buildTree1(rightInorder,rightPostOrder);
            return root;
    
    
        }
    
    1. 根据二叉树创建字符串题目链接
    class Solution {
        private StringBuilder sb;
        private void preorder(TreeNode root) {
            if (root == null) {
                sb.append("()");
                return;
            }
            sb.append("(");
            sb.append(root.val);
            if(root.left == null && root.right == null){
    
            }
            else if(root.right == null){
               
                preorder(root.left);
               
            }else{
                preorder(root.left);
                preorder(root.right);
            }
            sb.append(")");
        }
        public String tree2str(TreeNode t) {
            sb = new StringBuilder();
            preorder(t);
            sb.delete(0, 1);
            sb.delete(sb.length() - 1, sb.length());
            return sb.toString();
        }
    }
    

    前中后序的非递归遍历

    由于递归遍历会不断调用栈,时间复杂度高
    前序遍历

    public static void preorder(TreeNode root) {
            TreeNode cur = root;
            Stack<TreeNode> stack = new Stack<>();
    
            while (cur != null || !stack.isEmpty()) {
                while (cur != null) {
                    System.out.println(cur.val);
                    stack.push(cur);
                    cur = cur.left;
                }
    
                TreeNode pop = stack.pop();
    
                cur = pop.right;
            }
        }
    

    中序遍历

    public static void inorder(TreeNode root) {
            TreeNode cur = root;
            Stack<TreeNode> stack = new Stack<>();
    
            while (cur != null || !stack.isEmpty()) {
                while (cur != null) {
                    stack.push(cur);
                    cur = cur.left;
                }
    
                TreeNode pop = stack.pop();
                System.out.println(pop.val);
    
                cur = pop.right;
            }
        }
    

    后序遍历

     public static void postorder(TreeNode root) {
            TreeNode cur = root;
            TreeNode last = null;   // 记录上次刚刚后序遍历过的结点
            Stack<TreeNode> stack = new Stack<>();
            //int height = -1;
            List<TreeNode> pathOf8 = null;
            List<TreeNode> pathOf4 = null;
    
            while (cur != null || !stack.isEmpty()) {
                while (cur != null) {
                    // 第一次经过结点
                    stack.push(cur);
                    cur = cur.left;
                }
    
                TreeNode pop = stack.peek();
                //height = Integer.max(height, stack.size());
    
                if (pop.right == null) {
    
                    if (pop.val == 4) {
                        pathOf4 = new ArrayList<>(stack);
                    } else if (pop.val == 8) {
                        pathOf8 = new ArrayList<>(stack);
                    }
    
                    // 第二次经过结点,但同时看作第三次经过结点
                    stack.pop();
                    //System.out.println(pop.val);
                    last = pop;
                } else if (pop.right == last) {
    
                    if (pop.val == 4) {
                        pathOf4 = new ArrayList<>(stack);
                    } else if (pop.val == 8) {
                        pathOf8 = new ArrayList<>(stack);
                    }
    
                    // 第三次经过结点
                    stack.pop();
                    //System.out.println(pop.val);
                    last = pop;
                } else {
                    // 第二次经过结点
                    cur = pop.right;
                }
            }
    
            //System.out.println(height);
            System.out.println(pathOf4);
            System.out.println(pathOf8);
        }
    

    验证demo:

    
    import java.util.Arrays;
    
    public class TestDemo {
    
        public static TreeNode buildTree(int[] preorder, int[] inorder) {
            if (preorder.length == 0) {
                return null;
            }
            int rootValue = preorder[0];
            TreeNode root = new TreeNode(rootValue);
    
            int leftSize = 0;
                    for (int i = 0; i < inorder.length; i++) {
                if (inorder[i] == rootValue) {
                    leftSize = i;
                }
            }
    
            int[] leftPreorder = Arrays.copyOfRange(preorder, 1, 1 + leftSize);
            int[] leftInorder = Arrays.copyOfRange(inorder, 0, leftSize);
            root.left = buildTree(leftPreorder, leftInorder);
    
            int[] rightPreorder = Arrays.copyOfRange(preorder, 1 + leftSize, preorder.length);
            int[] rightInorder = Arrays.copyOfRange(inorder, leftSize + 1, inorder.length);
            root.right = buildTree(rightPreorder, rightInorder);
    
            return root;
        }
        public static void main(String[] args) {
            int[] preorder = {1, 2, 4, 5, 8, 3, 6, 7};
            int[] inorder = {4, 2, 5, 8, 1, 6, 3, 7};
            TreeNode root = buildTree(preorder, inorder);
            //调用遍历方法
        }
    }
    
    展开全文
  • 树状图是一种数据结构,它是由n(n&gt;=1)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。   每个节点有零个或多个子节点;没有父...

    一、树

    树状图是一种数据结构,它是由n(n>=1)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。

     

    每个节点有零个或多个子节点;没有父节点的节点称为根节点;每一个非根节点有且只有一个父节点;除了根节点外,每个子节点可以分为多个不相交的子树

     

    相关概念

    度数:一个节点的子树的个数称为该节点的度数,一棵树的度数是指该树中节点的最大度数。

    节点:度数为零的节点称为树叶或终端节点,度数不为零的节点称为分支节点,除根节点外的分支节点称为内部节点。

    父子节点:一个节点的子树之根节点称为该节点的子节点,该节点称为它们的父节点,同一节点的各个子节点之间称为兄弟节点。一棵树的根节点没有父节点,叶节点没有子节点。

    树的路径:一个节点系列k1,k2, ……,ki,ki+1, ……,kj,并满足ki是ki+1的父节点,就称为一条从k1到kj的路径,

    树的边数:路径的长度为j-1,即路径中的边数。路径中前面的节点是后面节点的祖先,后面节点是前面节点的子孙。

    树的深度:节点的层数等于父节点的层数加一,根节点的层数定义为一。树中节点层数的最大值称为该树的高度或深度。

    有序树:若树中每个节点的各个子树的排列为从左到右,不能交换,即兄弟之间是有序的,则该树称为有序树。一般的树是有序树。

    森林:m(m≥0)棵互不相交的树的集合称为森林。树去掉根节点就成为森林,森林加上一个新的根节点就成为树。


    结点A的度:3
    结点B的度:2
    结点M的度:0
    树的度:3

    结点A的层次:1
    结点M的层次:4
    树的深度:4

    A的子节点:B,C,D
    I的父节点:D
    F,G为兄弟结点

     

     

    树的逻辑结构 :树中任何节点都可以有零个或多个直接后继节点(子节点),但至多只有一个直接前趋节点(父节点),根节点没有前趋节点,叶节点没有后继节点。

     

    二、二叉树

    在计算机科学中,二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。

     

    二叉树是有序树,与普通有序树不同,二叉树严格区分左孩子和右孩子,即使只有一个子节点也要区分左右。

     

    满二叉树:深度为k(k≥1)时有2k-1个节点的二叉树。

    完全二叉树:只有最下面两层有度数小于2的节点,且最下面一层的叶节点集中在最左边的若干位置上。

     

    二叉树性质

    • 二叉树第i(i≥1)层上的节点最多为2^(i-1)个。
    • 深度为k(k≥1)的二叉树最多有2^k-1个节点。
    • 在任意一棵二叉树中,树叶的数目比度数为2的节点的数目多一。

     

    二叉树存储结构

    1.顺序存储结构

     
    若二叉树不是完全二叉树,通过补虚节点,将其补成完全二叉树。
    按从上到下,从左到右的顺序编号,根节点为1
    按编号一次存储在连续空间中,虚节点用特殊符号标识即可。

     

     

    2.链式存储结构

    btree_pnode指向根节点,通过btree_pnode->lchild指向左子树的根结点,btree_pnode->rchild 指向右子树的根结点!

    typedef char dataype_bt;
    
    typedef struct btreenode{
    	dataype_bt data;
    	struct btreenode *lchild,*rchild;
    }btree_node,*btree_pnode;

     

    展开全文
  • 本书详纽讲述了线性结构、树结构和图结构中的数据表示数据处理的方法,对查找和排序两种重要的数据... 本书可作为计算机和信息类相关专业本(专)科“数据结构”课程的教材或学习参考书,也可供有关工程技术人员参考。
  • 数据结构相关概念

    2019-07-07 19:01:57
    文章目录基本概念及术语数据定义数据结构逻辑结构与物理结构逻辑结构物理结构 基本概念及术语 数据结构是一门研究非数值计算的程序设计问题中的操作对象,以及他们之间的关系和操作等相关问题的学科。 其重要性...
  • 数据结构线性表相关算法 线性表的概念及顺序存储 定义:线性表是由n个类型相同的数据元素组成的有限序列。 数据元素之间是一对一的关系,即每个数据元素最多有一个直接前驱和一个直接后继。 逻辑结构图 线性表的...
  • 图Graph的概念 图Graph是比树更为一般的结构, 也是由节点和边构成 实际上树是一种具有特殊性质的图 图可以用来表示现实世界中很多事物 道路交通系统、航班线路、互联网连接、或者是大学中课程的先修次序 ...
  • 数据的逻辑结构算法及其概念算法:解决问题的步骤的描述, 在计算机中表现为指令的有限序列算法的特性: I/O:算法有0个或者多个输入, 至少有一个输出 有穷性:无死循环, 能在可以接受的时间内完成 确定性:算法的
  • 树的相关概念、性质总结 树是一种非常重要且应用非常广泛的数据结构,也是我们进行算法类研究工作的基础。因此我在这里总结了一下浙大著名的公开课:数据结构算法国家精品课中的一些重点和思想,以方便大家更加...
  • 文章目录数据结构基础概念相关抽象数据的理解两种视角,两种结构数据结构的意义生活中的逻辑接口和物理接口(加深理解)算法基础概念相关算法的意义算法特征好算法的基本要求算法效率的考量大O表示法概念及理解计算...
  • 1、建立数学模型——构造求解方法——选择存储结构——编写程序——测试2、数据结构+算法=程序3、主要用于非数值型数据处理4、数据结构相关概念:数据:数值型(整数+实数等)、非数值型(声音、图像、文字)数据...
  • 本书在简要回顾了基本的C++程序设计概念的基础上,全面系统地介绍了队列、堆栈、树、图等基本数据结构,以及贪婪算法、分而治之算法、分枝定界算法等多种算法设计方法,为数据结构算法的继续学习和研究奠定了一个...
  •  数据结构是一门与程序设计密切相关的课程,而程序设计就是算法+数据结构算法即是处理数据的策略,而数据结构就是表达程序设计的模型,可以说任何一个程序设计问题,我们都可以从算法和模型出发。概而言之,数据...
  • 数据及相关概念

    2021-04-11 21:26:44
    数据:数据是客观事物的符号,表示在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素:数据元素是数据的基本单位,在...数据和数据结构,数据的逻辑结构和存储结构,数据类型,算法
  • 数据结构主要研究数据的组织、存储运算方法。 数据结构算法的研究设计构筑计算机求解问题过程的两个重要方面:刻画实际问题中信息及其关系的数据结构和描述问题解决方案的逻辑抽象算法数据结构相关术语: ...
  • 第*页 * * 数据结构是计算机及相关专业中一门重要的专业基础课程当用计算机来解决实际问题时就要涉及到数据的表示及数据的处理而数据表示及数据处理正是数据结构课程的主要研究对象通过这两方面内容的学习为后续课程...
  • 数据结构课程是计算机类专业的专业基础课程,在IT人才培养中,起着重要的...系列课程包含11个部分,本课为第1部分,介绍与数据结构、程序、算法相关概念,训练初步的数据逻辑结构表达能力,和初步的算法分析能力。...
  • 第六章数据结构算法 考情分析 本章要求了解数据结构算法的基本概念相关术语重点掌握线性表栈 队列数 组树和图等数据结构概念 存储方式和相关算法熟悉排序和查找的基本方法对于在 招聘计算机专业单独考试中是...
  • 一、BST相关概念 BST(二叉搜索树)可以实现增加、删除、搜索的时间复杂度都为log2n(以2为底,并非2n)。关于树的基础概念根据图中数据解释以便理解: 58是根节点root;23是58的左孩子;82是58的右孩子; 23是12和...
  • 为什么要学习数据结构算法?...还有一些人也只听说过数组、链表、快排这些最最基本的数据结构算法,稍微复杂一点的就完全没概念。 当然,也有很多同学说,自己实际工作中根本用不到数据结构算法...
  • 20180911 课程概念入门及算法相关 声明:此为老师上课笔记相关整理,如有错误之处请指出 ¦ 引言 现在学的这门数据结构,是为了给大三的大数据打基础,是使用java语言来学习 Java分为:JavaSE ...
  • 数据结构算法

    2019-01-21 20:37:28
    数据结构是一门研究非数值计算的程序设计问题中的操作对象,以及他们之间的关系和操作等相关问题的学科。程序设计=数据结构+算法 基本概念和术语 数据是描述客观事物的符号,是计算机中可以操作的对象,事能被计算机...
  • 数据结构算法绪论

    2020-04-21 22:56:11
    1.1数据结构中数据相关的基本概念 数据(Data):数据是信息的载体,是描述事务客观属性的数,字符所有能输入到计算机中并被计算机程序识别和处理的符号的集合。如数学计算中用到的整数和实数,文本编辑中用到...
  • Java数据结构算法

    2012-06-01 14:16:03
    《Java数据结构算法》(第2版)介绍了计算机编程中使用的数据结构算法,对于在计算机应用中如何操作和管理数据以取得最优性能提供了深入浅出的讲解。全书共分为15章,分别讲述了基本概念、数组、简单排序、堆和...
  • 试题类型 本课程为考试科目 闭卷笔试试题类型包括 概念填空题 10 % 是非判断题 10 % 单项选择题 40 % 算法填空题 10% 算法应用题 20 ) 算法设计题 10 % 第一章 绪论 重点内容要求 1 了解与数据结构相关概念 ...
  • 主要介绍了Python数据结构算法之图结构(Graph),结合实例形式分析了图结构的概念、原理、使用方法及相关操作技巧,需要的朋友可以参考下

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 837
精华内容 334
关键字:

数据结构算法及相关概念

数据结构 订阅