美文网首页前端编程
二叉树的遍历

二叉树的遍历

作者: vinson_sheep | 来源:发表于2017-04-03 21:03 被阅读0次

文章来源https://segmentfault.com/a/1190000000740261

基本性质

  1. 每个节点有三个指针,分别指向父母、左孩子、右孩子、
  2. 第i层至多有2i-1个结点
  3. 深度为k的二叉树最多有2i-1个结点

顺序/链式

顺序存储,是用一维数组存储二叉树中的各个结点,而且结点的存储位置能体现结点之间的逻辑关系。
国际标准都使用链式结构

二叉树的遍历

  1. 前序遍历(DLR),首先访问根结点,然后遍历左子树,最后遍历右子树。简记根-左-右。、
  2. 中序遍历(LDR),首先遍历左子树,然后访问根结点,最后遍历右子树。简记左-根-右。
  3. 后序遍历(LRD),首先遍历左子树,然后遍历右子树,最后访问根结点。简记左-右-根。
1/3 前序遍历
遍历的顺序为:A B D H I E J C F K G
//先序遍历 function preOrder(node){ if(!node == null){ putstr(node.show()+ " "); preOrder(node.left); preOrder(node.right); } }
2/3 中序遍历
遍历的顺序为:H D I B E J A F K C G
//使用递归方式实现中序遍历 function inOrder(node){ if(!(node == null)){ inOrder(node.left);//先访问左子树 putstr(node.show()+ " ");//再访问根节点 inOrder(node.right);//最后访问右子树 } }
3/3 后序遍历
遍历的顺序为:H I D J E B K F G C A
//后序遍历 function postOrder(node){ if(!node == null){ postOrder(node.left); postOrder(node.right); putStr(node.show()+ " "); } }

相关文章

  • 二叉树 基础操作

    二叉树的使用 二叉树结构 先序创建二叉树 DFS 先序遍历二叉树 中序遍历二叉树 后序遍历二叉树 BFS 层次遍历...

  • 二叉树遍历

    二叉树 二叉树的存储结构 前序遍历 中序遍历 后序遍历 遍历代码 反转二叉树 深入学习二叉树 二叉树-你必须要懂!...

  • 二叉树操作

    树节点 逐行顺序解析二叉树 前序遍历二叉树 中序遍历二叉树 后序遍历二叉树 删除指定数值的节点 前序遍历顺序存储的...

  • 关于二叉树的算法题

    前序遍历中序遍历后序遍历判断是否是平衡二叉树判断是否是对称二叉树判断二叉树高度按照层遍历二叉树判断二叉树宽度

  • 二叉树三种遍历Swift代码实现

    二叉树的三种遍历 二叉树 前序遍历 中序遍历 后序遍历 另外 不得不说,得到二叉树的前序遍历和中序遍历的结果或者后...

  • 数据结构与算法之二叉树遍历(七)

    目录 前序遍历中序遍历后序遍历层序遍历遍历方式的选择条件根据遍历结果重构二叉树翻转二叉树计算二叉树的高度判断一棵树...

  • 二叉树的遍历

    二叉树的遍历 二叉树遍历 分为前序遍历、中序遍历和后序遍历。 前序遍历 (DLR) 先访问根节点,然后前序遍历左子...

  • 数据结构:树的实现和遍历(c++)

    (一)二叉树的遍历——递归实现 二叉树常见的遍历方式分为前序遍历、中序遍历和后序遍历。 1 前序遍历 前序遍历也叫...

  • 二叉树的蛇形层次遍历(LeetCode.103)

    题目 解析 首先参考二叉树的层次遍历层次遍历二叉树(LeetCode--102二叉树的层次遍历)[https://...

  • 算法精选题总结之二叉树类

    1.二叉树的中序遍历中序遍历的迭代方法中序遍历的递归方法2.二叉树前序遍历3.二叉树后续遍历4.二叉树的最近公共祖...

网友评论

    本文标题:二叉树的遍历

    本文链接:https://www.haomeiwen.com/subject/btqnottx.html