您现在的位置:首页 > >

二叉树遍历

发布时间:

目录


一、三种遍历


二、遍历算法


1. 递归遍历


2. 循环遍历



一、三种遍历

二叉树遍历分为三种:前(先)序遍历、中序遍历、后序遍历


首先需要明确,二叉树以何种方式遍历,是以根节点在排序中的先后顺序来命名的,例如:



? ? 前序遍历:如果根节点先排序,则为前序遍历【ABC】


? ? 中序遍历:如果先排左节点,再排根节点,则为中序遍历【BAC】


? ? 后序遍历:如果根节点最后排序,则为前序遍历【BCA】


其中,树排序常用中序遍历以例讲解,有一种较快捷的排序方式如下:



二、遍历算法

以leetcode上的算法题为例,算法地址:https://leetcode.com/problems/binary-tree-inorder-traversal/


该算法可用两种方式实现:递归、循环


1. 递归遍历

(1)代码实现


a. 从父节点开始(起始节点为根节点),先遍历左子节点


b. 如果左子节点不为空,则将左子节点当成父节点继续遍历


c. 如果左子节点为空,则当前节点可放入结果集中


d. 接着再检查右子节点,如果右子节点不为空,则将右子节点当成父节点。


e. 依次重复上述该过程。


private static ArrayList inorderRecursive(TreeNode node, ArrayList intList) {
if (node == null) {
return intList;
}
if (node.left != null) {
inorderRecursive(node.left, intList);
}
intList.add(node.val); // 决定了该遍历是前、中、后序遍历的哪一种
if (node.right != null) {
inorderRecursive(node.right, intList);
}
return intList;
}

递归实现二叉树遍历


(2)空间复杂度:O(n),T(n) = 2 ? T ( n / 2 ) + 1


(3)时间复杂度:*均O(logn) , 最差O(n)


2. 循环遍历

(1)代码实现


a. 判断当前节点的左子节点是否为空,如果为空,则写入结果集


b. 如果不为空,则遍历该左子节点,找到其最末端的右子节点(没有右子节点时,可将当前节点当成右子节点),将当前节点当成最末端右子节点的右子节点。


该方法执行过程中,对树进行了调整,当遍历完成后,该二叉树所有节点的左子节点都为空


private static ArrayList inorderIterative(TreeNode root) {
ArrayList intList = new ArrayList<>();
TreeNode node = root;
while (node != null) {
if (node.left == null) {
intList.add(node.val);
node = node.right;
} else {
TreeNode rightNode = node.left;
while (rightNode.right != null) {
rightNode = rightNode.right;
}
TreeNode tempNode = node; // 对节点清理做准备
rightNode.right = node;
node = node.left;
tempNode.left = null;
}
}
return intList;
}

循环实现二叉树遍历


(2)空间复杂度:O(n)


(3)时间复杂度:O(n)



另外leetcode上还提供了一种利用栈自身数据结构的实现方式,可自行尝试


本文中展示的代码地址:BinaryTreeInorderTraversal


相关阅读:*衡二叉树


热文推荐
猜你喜欢
友情链接: 医学资料大全 农林牧渔 幼儿教育心得 小学教育 中学 高中 职业教育 成人教育 大学资料 求职职场 职场文档 总结汇报