精华内容
下载资源
问答
  • 二叉树遍历(图解)

    万次阅读 多人点赞 2018-08-14 16:55:09
    二叉树的顺序存储结构就是用一维数组存储二叉树中的节点,并且节点的存储位置,也就是数组的下标要能体现节点之间的逻辑关系。—–>一般只用于完全二叉树 链式存储—–>二叉链表  定义: lchild | ...

    二叉树的顺序存储结构就是用一维数组存储二叉树中的节点,并且节点的存储位置,也就是数组的下标要能体现节点之间的逻辑关系。—–>一般只用于完全二叉树 
    链式存储—–>二叉链表 
    定义: lchild | data | rchild(两个指针域,一个数据域)

    typedef struct Node {
         ElemType data;
         struct Node *lchild, *rchild;
    }BiTnode,* BiTree;

    注意点: 
    1)已知 前序遍历序列 和 中序遍历序列可以唯一确定一颗二叉树 
    2)已知 中序遍历序列和 后序遍历序列可以唯一确定一颗二叉树 
    而已知 前序和后序 是不能确定一颗二叉树的

    二叉树的遍历:是指从根节点出发,按照某种次序依次访问二叉树中的所有节点,使得每个节点被访问一次且仅被访问一次。

    1、前序遍历:根-左-右 
    这里写图片描述

    代码:

    void PreOrder(BiTree T) /*先序遍历: 根-左-右*/
    {
        if(T != NULL)
        {
            Visit(T);   /*访问根节点*/
            PreOrder(T->lchild);  /*访问左子节点*/
            PreOrder(T->rchild);  /*访问右子节点*/
        }
    }

    2、中序遍历:左-根-右 
    这里写图片描述

    代码:

    void InOrder(BiTree T)/*中序遍历:左-根-右*/
    {
        if(T != NULL)
        {
            InOrder(T->lchild);  //左
            Visit(T);            //根
            InOrder(T->rchild);  //右
        }
    }

    3、后序遍历:左-右-根 
    这里写图片描述

    代码:

    void PostOrder(BiTree T)/*后序遍历:左-右-根*/
    {
        if(T != NULL)
        {
            PostOrder(T->lchild);  //左
            PostOrder(T->rchild);  //右
            Visit(T);              //根
        }
    }

    4、层序遍历:从根节点出发,依次访问左右孩子结点,再从左右孩子出发,依次它们的孩子结点,直到节点访问完毕 
    这里写图片描述

    代码:该程序用到了队列的思想,可以参考下图理解 
    (该图为展示的是 图的广度优先遍历示意图,应用的就是层序遍历的思想

    /*层序遍历 思路:按从左至右的顺序来逐层访问每个节点,层序遍历的过程需要队列*/
    void LevelOrder(BiTree T)
    {
        BiTree p = T;
    
        queue<BiTree> queue;         /*队列*/
        queue.push(p);               /*根节点入队*/
    
        while(!queue.empty())        /*队列不空循环 */
        {
            p = queue.front();       /*对头元素出队*/
            //printf("%c ",p->data); /*访问p指向的结点*/
            cout << p->data << " ";
    
            queue.pop();             /*退出队列*/
            if(p->lchild != NULL){   /*左子树不空,将左子树入队*/
                queue.push(p->lchild);
            }
            if(p->rchild != NULL){   /*右子树不空,将右子树入队*/
                queue.push(p->rchild);
            }
        }
    }

    这里写图片描述

    展开全文
  • 一、什么是二叉树的遍历 所谓遍历(Traversal)是指沿着某条搜索路线,依次对树中每个...二、二叉树遍历分类 遍历:前序遍历(Preorder):根节点----->左节点---->右节点 中序遍历(Inordef): 左节点----->根节点---->右节

    一、什么是二叉树的遍历

           所谓遍历(Traversal)是指沿着某条搜索路线,依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问 题。 遍历是二叉树上最重要的运算之一,是二叉树上进行其它运算之基础。

    二、二叉树遍历分类

    遍历:前序遍历(Preorder):根节点----->左节点---->右节点

              中序遍历(Inordef): 左节点----->根节点---->右节点

              后序遍历(Postorder): 左节点----->右节点---->根节点

               层次遍历(Levelorder): 每一层每一层的访问

            以前序为例:以A为根节点是先访问A,再访问A的左子树B,此时B又是根节点,以B为根节点访问B的左子树C,再以C为根节点时,按照前序遍历,先根再左最后右的原则,又因为C的左右子树为NULL所以C节点访问完毕,此时B的左子树访问完毕,B作为根节点也访问完毕,这个时候就应该去访问B的右子树。。。以此类推便可得到二叉树前序。

    三、二叉树的遍历实现

    二叉树的遍历分为递归遍历和非递归遍历

    本节介绍递归实现二叉树的前、中、后序遍历,非递归下节介绍

    前序遍历:

    中序遍历:

    后序遍历:

     

    展开全文
  • 【图解数据结构】 二叉树遍历 目录 扯一扯 二叉树遍历原理 二叉树的创建 二叉树遍历方法 前序遍历 中序遍历 后序遍历 层序遍历 扯一扯 昨天在看《极客时间》严嘉伟老师的《如何做出好的职业选择——认识你...

    【图解数据结构】 二叉树遍历

    目录

    扯一扯
    二叉树遍历原理 
    二叉树的创建
    二叉树遍历方法
            前序遍历
            中序遍历
            后序遍历
          层序遍历

    扯一扯

    mark

    昨天在看《极客时间》严嘉伟老师的《如何做出好的职业选择——认识你的职业锚》专题直播时,严老师讲到了关于选择的一些问题,我认为其中的一些点讲的非常好,总结一下分享给大家。

    人为什么难做选择?

    选择意味着放弃

    你选择一方,也就意味着放弃了另一方。摆在你面前的选择项越接近,你的选择就会越困难,因为放弃其中任何一个选择项都不容易。如果摆在你面前的选择项对比明显,那么选择起来就会轻松许多,大家几乎都会毫不犹豫的选择“好”的选择项,放弃掉“差”的选择项。

    选择永远都不是完美的

    选择永远都不可能十全十美,只可能满足尽量多的侧重点。选择的时候想满足越多的侧重点,可能就会越难做出选择。所以在选择上不要过于追求完美。

    警惕逃避性选择——不知道自己要去哪儿,还要选择离开。

    有一种选择是对现状不满,想逃离这种现状,但是却不知道去哪里。举个例子,可能目前的公司有各种问题,比如开发流程不规范等,如果因为这些问题离开,可能就会从一个坑跳到另外一个更大的坑。当决定离开的时候,一定是自己有明确的目标,很清楚自己想要什么。

    二叉树遍历原理

    二叉树的遍历是指从根结点出发,按照某种次序依次访问二叉树中所有结点,使得每个结点被访问一次且仅被访问一次。

    为什么研究二叉树的遍历?

    因为计算机只会处理线性序列,而我们研究遍历,就是把树中的结点变成某种意义的线性序列,这给程序的实现带来了好处。

    二叉树的创建

    遍历二叉树之前,首先我们要有一个二叉树。要创建一个如下图的二叉树,就要先进行二叉树的扩展,也就是将二叉树每个结点的空指针引出一个虚结点,其值为一个特定值,比如'#'。处理后的二叉树称为原二叉树的扩展二叉树。扩展二叉树的每个遍历序列可以确定一个一颗二叉树,我们采用前序遍历创建二叉树。前序遍历序列:124##5##36##7##。

    mark

    mark

    定义二叉链表结点:

    /// <summary>
    /// 二叉链表结点类
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public class TreeNode<T>
    {
        /// <summary>
        /// 数据域
        /// </summary>
        public T Data { get; set; }
        /// <summary>
        /// 左孩子   
        /// </summary>
        public TreeNode<T> LChild { get; set; } 
        /// <summary>
        /// 右孩子
        /// </summary>
        public TreeNode<T> RChild { get; set; } 
    
        public TreeNode(T val, TreeNode<T> lp, TreeNode<T> rp)
        {
            Data = val;
            LChild = lp;
            RChild = rp;
        }
    
        public TreeNode(TreeNode<T> lp, TreeNode<T> rp)
        {
            Data = default(T);
            LChild = lp;
            RChild = rp;
        }
    
        public TreeNode(T val)
        {
            Data = val;
            LChild = null;
            RChild = null;
        }
    
        public TreeNode()
        {
            Data = default(T);
            LChild = null;
            RChild = null;
        }
    }

    先序递归创建二叉树:

    /// <summary>
    /// 先序创建二叉树
    /// </summary>
    /// <param name="node"></param>
    public static void CreateTree(TreeNode<char> node)
    {
        node.Data = Console.ReadKey().KeyChar;
    
        if (node.Data == '#')
        {
            return;
        }
    
        node.LChild = new TreeNode<char>();
    
        CreateTree(node.LChild);
    
        if (node.LChild.Data == '#')
        {
            node.LChild = null;
        }
    
        node.RChild = new TreeNode<char>();
    
        CreateTree(node.RChild);
    
        if (node.RChild.Data == '#')
        {
            node.RChild = null;
        }
    }

    二叉树遍历方法

    mark

    mark

    前序遍历

    mark

    递归方式实现前序遍历

    具体过程:

    1. 先访问根节点
    2. 再序遍历左子树
    3. 最后序遍历右子树

    代码实现:

    public static void PreOrderRecur(TreeNode<char> treeNode)
     {
         if (treeNode == null)
         {
             return;
         }
         Console.Write(treeNode.Data); 
         PreOrderRecur(treeNode.LChild);
         PreOrderRecur(treeNode.RChild);
     }

    非递归方式实现前序遍历

    具体过程:

    1. 首先申请一个新的栈,记为stack;
    2. 将头结点head压入stack中;
    3. 每次从stack中弹出栈顶节点,记为cur,然后打印cur值,如果cur右孩子不为空,则将右孩子压入栈中;如果cur的左孩子不为空,将其压入stack中;
    4. 重复步骤3,直到stack为空.

    代码实现:

     public static void PreOrder(TreeNode<char> head)
    {
        if (head == null)
        {
            return;
        }
        Stack<TreeNode<char>> stack = new Stack<TreeNode<char>>();
        stack.Push(head);
        while (!(stack.Count == 0))
        {
            TreeNode<char> cur = stack.Pop();
            Console.Write(cur.Data);
    
            if (cur.RChild != null)
            {
                stack.Push(cur.RChild);
            }
            if (cur.LChild != null)
            {
                stack.Push(cur.LChild);
            }
        }
    }

    过程模拟:

    执行结果:mark

    中序遍历

    mark

    递归方式实现中序遍历

    具体过程:

    1. 先中序遍历左子树
    2. 再访问根节点
    3. 最后中序遍历右子树

    代码实现:

    public static void InOrderRecur(TreeNode<char> treeNode)
    {
        if (treeNode == null)
        {
            return;
        }  
        InOrderRecur(treeNode.LChild);
        Console.Write(treeNode.Data); 
        InOrderRecur(treeNode.RChild);
    }

    非递归方式实现中序遍历

    具体过程:

    1. 申请一个新栈,记为stack,申请一个变量cur,初始时令cur为头节点;
    2. 先把cur节点压入栈中,对以cur节点为头的整棵子树来说,依次把整棵树的左子树压入栈中,即不断令cur=cur.left,然后重复步骤2;
    3. 不断重复步骤2,直到发现cur为空,此时从stack中弹出一个节点记为node,打印node的值,并让cur = node.right,然后继续重复步骤2;
    4. 当stack为空并且cur为空时结束。

    代码实现:

    public static void InOrder(TreeNode<char> treeNode)
    {
        if (treeNode == null)
        {
            return;
        }
        Stack<TreeNode<char>> stack = new Stack<TreeNode<char>>();
    
        TreeNode<char> cur = treeNode;
    
        while (!(stack.Count == 0) || cur != null)
        {
            while (cur != null)
            {
                stack.Push(cur);
                cur = cur.LChild;
            }
            TreeNode<char> node = stack.Pop();
            Console.WriteLine(node.Data);
            cur = node.RChild;
        }
    }

    过程模拟:

    执行结果:mark

    后序遍历

    mark

    递归方式实现后序遍历

    1. 先后序遍历左子树
    2. 再后序遍历右子树
    3. 最后访问根节点

    代码实现:

    public static void PosOrderRecur(TreeNode<char> treeNode)
    {
        if (treeNode == null)
        {
            return;
        }
        PosOrderRecur(treeNode.LChild);
        PosOrderRecur(treeNode.RChild);
        Console.Write(treeNode.Data); 
    }

    非递归方式实现后序遍历一

    具体过程:

    使用两个栈实现

    1. 申请两个栈stack1,stack2,然后将头结点压入stack1中;
    2. 从stack1中弹出的节点记为cur,然后先把cur的左孩子压入stack1中,再把cur的右孩子压入stack1中;
    3. 在整个过程中,每一个从stack1中弹出的节点都放在第二个栈stack2中;
    4. 不断重复步骤2和步骤3,直到stack1为空,过程停止;
    5. 从stack2中依次弹出节点并打印,打印的顺序就是后序遍历的顺序;

    代码实现:

    public static void PosOrderOne(TreeNode<char> treeNode)
    {
        if (treeNode == null)
        {
            return;
        }
    
        Stack<TreeNode<char>> stack1 = new Stack<TreeNode<char>>();
        Stack<TreeNode<char>> stack2 = new Stack<TreeNode<char>>();
    
        stack1.Push(treeNode);
        TreeNode<char> cur = treeNode;
    
        while (!(stack1.Count == 0))
        {
            cur = stack1.Pop();
            if (cur.LChild != null)
            {
                stack1.Push(cur.LChild);
            }
            if (cur.RChild != null)
            {
                stack1.Push(cur.RChild);
            }
            stack2.Push(cur);
        }
    
        while (!(stack2.Count == 0))
        {
            TreeNode<char> node = stack2.Pop();
            Console.WriteLine(node.Data); ;
        }
    }

    过程模拟:

    执行结果:mark

    非递归方式实现后序遍历二

    具体过程:

    使用一个栈实现

    1. 申请一个栈stack,将头节点压入stack,同时设置两个变量 h 和 c,在整个流程中,h代表最近一次弹出并打印的节点,c代表当前stack的栈顶节点,初始时令h为头节点,,c为null;

    2. 每次令c等于当前stack的栈顶节点,但是不从stack中弹出节点,此时分一下三种情况:

    (1)如果c的左孩子不为空,并且h不等于c的左孩子,也不等于c的右孩子,则吧c的左孩子压入stack中

    (2)如果情况1不成立,并且c的右孩子不为空,并且h不等于c的右孩子,则把c的右孩子压入stack中;

    (3)如果情况1和2不成立,则从stack中弹出c并打印,然后令h等于c;

    1. 一直重复步骤2,直到stack为空.

    代码实现:

    public static void PosOrderTwo(TreeNode<char> treeNode)
    {
        if (treeNode == null)
        {
            return;
        }
    
        Stack<TreeNode<char>> stack = new Stack<TreeNode<char>>();
        stack.Push(treeNode);
    
        TreeNode<char> h = treeNode;
        TreeNode<char> c = null;
        while (!(stack.Count == 0))
        {
            c = stack.Peek();
            //c结点有左孩子 并且 左孩子没被遍历(输出)过 并且 右孩子没被遍历过
            if (c.LChild != null && h != c.LChild && h != c.RChild)
                stack.Push(c.LChild);
            //c结点有右孩子 并且 右孩子没被遍历(输出)过
            else if (c.RChild != null && h != c.RChild)
                stack.Push(c.RChild);
            //c结点没有孩子结点 或者孩子结点已经被遍历(输出)过
            else
            {
                TreeNode<char> node = stack.Pop();
                Console.WriteLine(node.Data);
                h = c;
            }
        }
    }

    过程模拟:

    执行结果:mark

    层序遍历

    mark

    具体过程:

    1. 首先申请一个新的队列,记为queue;
    2. 将头结点head压入queue中;
    3. 每次从queue中出队,记为node,然后打印node值,如果node左孩子不为空,则将左孩子入队;如果node的右孩子不为空,则将右孩子入队;
    4. 重复步骤3,直到queue为空。

    代码实现:

    public static void LevelOrder(TreeNode<char> treeNode)
    {
        if(treeNode == null)
        {
             return;
        }
        Queue<TreeNode<char>> queue = new Queue<TreeNode<char>>();
        queue.Enqueue(treeNode);
    
        while (queue.Any())
        {
            TreeNode<char> node = queue.Dequeue();
            Console.Write(node.Data);
    
            if (node.Left != null)
            {
                queue.Enqueue(node.Left);
            }
    
            if (node.Right != null)
            {
                queue.Enqueue(node.Right);
            }
        }
    }

    执行结果:mark

     

    展开全文
  • 二叉树常见的遍历方法有: - 前序遍历(preorder):“根左右” - 中序遍历(inorder):“左根右” - 后序遍历(postorder):“左右根” - 层次遍历(level):逐层从左到右访问节点前三种遍历方法,属于树的...

    二叉树常见的遍历方法有:

    • 前序遍历(preorder):“根左右”
    • 中序遍历(inorder):“左根右”
    • 后序遍历(postorder):“左右根”
    • 层次遍历(level):逐层从左到右访问节点

    前三种遍历方法,属于树的深度优先搜索DFS。层次遍历方法则属于广度优先搜索BFS。

    前三种对应于数学上的前缀、中缀、后缀表达式(波兰/逆波兰表示),方便计算机来计算带括号区分运算优先级别的运算。

    借鉴leetcode中对于二叉树的定义,后面给出几种遍历方法的实现。完整的实现及测试代码见Github/Algorithm/Binary Tree

    # Definition for a binary tree node.
    class TreeNode(object):
        def __init__(self, x):
            self.val = x
            self.left = None
            self.right = None

    前序遍历

    递归实现,直接按照preorder的定义即可。

    def preorder_1(root):
        if root != None:
            print root.val
            preorder_1(root.left)
            preorder_1(root.right)    

    preorder的非递归实现,借助栈的数据结构实现,有两种实现方法:

    def preorder_2(root):
        stack = []
        stack.append(root)
        while stack:
            node = stack.pop()
            print node.val
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)    
    
    def preorder_3(root):
        stack = []
        while root or stack:
            if root:
                print root.val
                stack.append(root) # push root
                root = root.left # visit left
            else:
                root = stack.pop() # backtrack parent node
                root = root.right # visit right
    • 第一种方法主要是根节点出栈,访问根节点,然后压入右子节点左子节点(出栈顺序相反,才能实现访问先左后右),直到栈空。
    • 第二种方法也是基于栈,但用回溯策略,每次左子树遍历完之后才回溯,然后遍历右子树。

    中序遍历

    中序遍历的递归实现也是按定义直接来。非递归实现也是借助栈,采用和preorder第二种回溯相似的方法。对于BST,用中序遍历可以得到有序数列。

    def inorder_1(root):
        if root != None:
            inorder_1(root.left)
            print root.val
            inorder_1(root.right)
    
    def inorder_2(root):
        stack = []
        while root or stack:
            if root:
                stack.append(root)
                root = root.left
            else:
                root = stack.pop()
                print root.val
                root = root.right

    后序遍历

    后序遍历的非递归实现比较复杂,但可以借助两个栈实现。后序遍历的顺序是“左-右-根”,可以看作伪先序遍历“根-右-左”的逆过程,因此仿preorder的非递归实现,在出栈的同时压入另一个栈,可以实现反向输出“根-右-左”的顺序,即后序遍历。

    def postorder_1(root):
        if root != None:
            postorder_1(root.left)    
            postorder_1(root.right)
            print root.val
    
    def postorder_2(root):
        if root == None:
            return 
        stack = []
        output = []
        stack.append(root)
        while stack:
            node = stack.pop()
            output.append(node)
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
        while output:
            node = output.pop()
            print node.val

    借助辅助栈带来O(logn)的空间复杂度,能不能在O(1)的空间复杂度实现?

    Morris Traversal方法: Morris遍历方法用了线索二叉树,这个方法不需要为每个节点额外分配指针指向其前驱和后继结点,而是利用叶子节点中的右空指针指向中序遍历下的后继节点就可以了。这样就节省了需要用栈来记录前驱或者后继结点的额外空间, 所以可以达到O(1)的空间复杂度,但会暂时性修改树的结构。


    层次遍历

    层次遍历是广度优先的一种情形。BFS常常借助队列的数据结构来实现,因此层次遍历可以维护一个队列来实现。在访问当前节点时,也把它的左右子节点压入队列尾,访问完队列头(同一level)的节点后,再出队访问之前入队的下一level的一系列节点。

    def level_traversal(root):
        queue = []
        if root == None:
            return
        queue.append(root)
        while queue:
            node = queue.pop(0)
            print node.val
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

    相关题目:Binary Tree Level Order Traversal(I,II)和Binary Tree Zigzag Level Order Traversal。


    求二叉树深度(递归&非递归实现)

    Leetcode中Maximum Depth of Binary Tree定义二叉树的最大深度,是沿着从root到最远leaf的最长路径的节点数,大概就是层次遍历的最大层数吧?例如,只有一个节点,其深度为1;一个三层的二叉树深度为3。

    求二叉树的深度,是遍历二叉树的一个拓展应用。

    递归实现:很简单,分别求左右子树的深度,然后返回两者深度的最大值+1,即当前根子树的深度。时间复杂度O(n),空间复杂度取决于树的深度可能范围,介于O(logn)和O(n)之间。

    def maxDepth(self, root):
        if not root:
            return 0
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

    非递归实现:递归实现中先处理左子树、后处理右子树、再返回最大值,这一过程和后序遍历相同。因此可以参考后序遍历的借助栈的迭代实现。

    def maxDepth(self, root):
        if not root:
            return 0
        stack = []
        max_depth = 0
        stack.append(root)
        prev, cur = None, None
        while stack:
            cur = stack[-1]
            if not prev or (prev.left == cur) or (prev.right == cur):
                if cur.left:
                    stack.append(cur.left)
                elif cur.right:
                    stack.append(cur.right)
            elif cur.left == prev:
                if cur.right:
                    stack.append(cur.right)
            else:
                stack.pop()
    
            prev = cur
            if len(stack) > max_depth:
                max_depth = len(stack)
    
        return max_depth

    参考层次遍历:树的最大深度即层次遍历的层数,修改基于队列的层次遍历函数,同时记录层数,返回层数即可,效率更高。

    def maxDepth(root):
        if not root:
            return 0
        queue = []
        queue.append(root)
        max_depth = 0 # level = 0
        while queue:
            size = len(queue)
            for i in xrange(size):
                node = queue.pop(0)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            max_depth += 1 # level += 1
        return max_depth

    相关题目


    扩展阅读

    展开全文
  • 算法之二叉树各种遍历

    千次阅读 2016-04-15 10:23:33
    算法之二叉树各种遍历: http://blog.csdn.net/sjf0115/article/details/8645991
  • 与只能线性遍历的链表和数组不同,遍历二叉树有几种方法。树遍历算法主要分为深度优先和广度优先两部分。顾名思义,在深度优先的情况下,在访问下一个同级树之前,树向下(向深度)遍历二叉树的PreOrder,InOrder和...
  • 日期:2016-08-22本文总结一下二叉树的非递归遍历基本数据结构参考代码struct ValueType { int val; };struct Node { ValueType val; Node* leftChild; Node* rightChild; };一、前序遍历vector<ValueType> ...
  • 二叉树遍历 一共有4种遍历 先看图,对于这个图进行4种遍历的讲解     1、 先序遍历 定义:若二叉树为空,则空操作;否则 (1)访问根节点(2)先序遍历左子树(3)先序遍历右子树 根据...
  • 3)二叉树遍历:给出一棵二叉树,可以得到其三种遍历结果 遍历就是按某指定规则访问树中每个结点,且使得每个结点均被访问一次,而且仅被访问一次。遍历二叉树经常要遇到的一种操作。 前序遍历二叉树。前序遍历...
  • 在这篇文章中,我来介绍计算机理论中的最常见的数据结构之一:树。其实,树这种结构,并不只是存在于算法理论中,在计算机的其他领域也有着重要的作用。例如,我们所熟知的C,Java,C++等编程语言的编译器,都离不开...
  • 二叉树练习题及解析

    千次阅读 2020-06-14 14:06:51
    1、 某二叉树的前序序列和后序序列正好相反,则该二叉树一定是( )的二叉树。...当二叉树任一节点无左孩子时,L为空,前序遍历为M-R,后序遍历为R-M,结果正好相反,满足条件 当二叉树任一节点无右孩子时,R为空,前序遍
  • 计算机导论 测试题

    千次阅读 2019-03-17 17:36:30
    这套试题是用来测试计算机基础知识的 所以没有答案 不懂得可以直接百度 填空 计算机领域中采用________、________、________来表示数值。 冯·诺依曼型计算机的两大特征是“程序存储”和“________”。 美国标准...
  • 【目录】篇基本理论与知识章计算机概述1.1计算机模型1.1.1数据处理模型1.1.2图灵模型1.1.3冯·诺依曼模型1.2计算机的发展1.2.1机械计算机器(1930年以前)1.2.2电子计算机诞生(1930—1950年)1.2.3电子计算机的发展...
  • 一、填空题1. 以下程序的功能是实现带附加头结点的单链表数据结点逆序...【答案】【解析】每个非终端结点都是0表示该平衡二叉树没有高度落差。也就是说它是一棵满二叉 树。故结点个数为3. 从平均时间性能而言,_...
  • 队列和栈 【解析】广度优先遍历图使用队列这种数据结构,深度优先遍历图使用栈这种数据结构。 6. 设数组的基地址为2000,每个元素占2个存储单元,若以行序为主序顺序存储,则元素为_____。 【答案】9174;8788 ...
  • 判定一棵树是否为完全二叉树 判定两棵树是否相同 判定两棵树是否有相同结构和节点值的子树 找出树的最大深度 判定一棵树是否为高度平衡的二叉树(一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1) 判定...
  • 计算机导论

    2021-07-22 04:40:00
    篇基本理论与知识章计算机概述1.1计算机模型1.1.1数据处理模型1.1.2图灵模型1.1.3冯·诺依曼模型1.2计算机的发展1.2.1机械计算机器(1930年以前)1.2.2电子计算机诞生(1930—1950年)1.2.3电子计算机的发展(1950年至今)...
  • 计算机导论期末复习

    千次阅读 2020-12-22 18:32:12
    计算机导论期末复习 一、单选题 1.我国四大数据通信网是中国共用分组交换 数据网(ChinaPAC),中国公用数字数据网(ChinaDDN),中国共用计算机互联网(ChinaNet),中国公用帧中继网(ChinaFRN)。 2.我国Internet...
  • 堆(英语:heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质: 堆中某个节点的值总是不大于或不小于其父节点的值; 堆总是一棵完全二叉树。 将根节点...
  • /*(1) 建立一棵含有n个结点的二叉树,采用二叉链表存储建立结点的结构体类型...(2) 前序(或中序、后序)遍历二叉树*/#include<stdio.h>#include<malloc.h> // char DataType;typedef struct Node{ ...
  • 计算机导论-第四章-算法与数据结构期末测试习题与答案 一、选择题 1、算法的时间复杂度是指( )。 A.算法执行过程中所需要的基本运算次数 B.执行算法程序所需要的时间 C.算法程序的长度 D.算法程序中的指令条数 正确...
  • 按完全二叉树的层次关系给出二叉树遍历序列(#表示虚结点,数据结点为单一字符)。 输出: 二叉树的凹入表示  二叉树的先序序列、中序序列、后序序列  二叉树叶子结点个数  左、右子树相互交换后的二叉树的凹入...
  • 计算机导论》期末猜题

    千次阅读 2019-01-09 19:10:48
    1. 名词解释 计算机定义: 是一种能按照事先存储的程序,自动、高速地进行数值计算和...是用通信线路将分散在各地的具有独立自主的计算机系统相互联接,并按照网络协议进行数据通信和资源共享的计算机集合。 ...
  • 计算机科学导论》学习笔记

    千次阅读 多人点赞 2019-10-17 17:31:08
    计算机科学导论》 图灵模型 计算机是一个接收输入数据,处理数据并产生输出数据的黑盒 计算机是在存储器中储存数据 程序是用来告诉计算机对数据进行处理的指令集合。 输出数据是依赖两方面因素的结合作用:输入...
  • 在学习二叉搜索树之前,我准备先预习一下二叉树的概念和相关算法。 二叉树拥有结合有序数组和链表的优点,查找数据和在数组中查找一样快,插入删除数据则有和链表一样高效的性能,所以是面试中必问的知识点。 二叉树...
  • 树 比如下面这幅图,A节点是B节点的父节点,B节点是A节点的子节点。B、C、D这三个节点的父节点是同一个节点...二叉树,每个节点最多有两个“叉”,也就是两个子节点,分别是左子节点和右子节点。 其中,编号为2...
  • 计算机科学导论(读书笔记)

    千次阅读 2019-04-10 09:06:13
    冯诺依曼:提出程序也可以存储在计算机里(输入输出,控制单元,存储器,算术逻辑) 类:可以理解为自己创造指令,进行组合。 算法:解决问题的方法与步骤 软件工程:结构化程序的设计和编写(程序设计中遵循的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,695
精华内容 678
关键字:

计算机导论二叉树遍历