Question

1. 二叉树是树吗?它的定义为什么是递归的? 2. 三种根序遍历主要思路是什么? 3

Answer 1

1. 二叉树（Binary tree）是一种算法结构，是树形结构的一种。因为存储结构及其算法都较为简单，好理解，所以应用比较广泛。二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点。

2. 递归是算法的一种，它是指一种通过重复将问题分解为同类的子问题而解决问题的方法。而二叉树从算法定义上看，或者是实际编程，3种遍历方式，都符合递归算法的特征。

3. 二叉树递归遍历分为先序遍历、中序遍历和后序遍历。

   先序遍历为：根节点+左子树+右子树

   中序遍历为：左子树+根节点+右子树

   后序遍历为：左子树+右子树+根节点

   （你只要记住根节点在哪里就是什么遍历，且都是先左再右）

   举个例子，如二叉树：

   

   请点击输入图片描述

   这棵树的先序遍历为：1 2 3 4 5

   中序遍历为：2 1 4 3 5

   后序遍历为：2 4 5 4 1