二叉排序树 中序遍历 java基础复习——二叉树以及代码实现

说到二叉树，那都是很久以前学的了。。。 最近听到之前的一个同事说，有人说他基础很好，可以写出二叉树等数据结构的实现，这。二叉排序树 中序遍历。。虽然在很看来并没有什么，但是。。。二叉排序树 中序遍历我TM对二叉树完全没印象了，突然觉得自己好菜啊~~~

所以痛下决心，需要复习一下基础知识了~~~ 那么就先从这个二叉树开始吧。

所谓的二叉树，它是一种数据结构，同时具有数组和链表各自的特点：它可以像数组一样快速查找，也可以像链表一样快速添加。缺点就是：删除操作复杂。

二叉树：：每个结点最多有两个子树的有序树。在使用二叉树的时候，数据并不是随便插入到节点中的：“一个节点的左子节点的关键值必须小于此节点，右子节点的关键值必须大于或者是等于此节点”，所以又称二叉查找树、二叉排序树、二叉搜索树。

完全二叉树：若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。

满二叉树：除叶结点外的每一个结点都有左右子叶节点，且树的叶子结点都处在最底层。

特点：

1. 执行查找、删除、插入的时间复杂度都是O(logN)

2. 遍历二叉树的方法包括前序、中序、后序

3. 在非空二叉树中，第i层的结点总数不超过 , i>=1；

4. 深度为h的二叉树最多有个结点(h>=1)，最少有h个结点

5. 对于任意一棵二叉树，如果其叶结点数为，而度数为2的结点总数为，则.

二叉树的遍历

二叉树的遍历分为以下三种：

先序遍历：为先【遍历】根节点，再【遍历】左子树，最后【遍历】右子树——【根左右】

中序遍历：为先【遍历】左子树，再【遍历】根节点，最后【遍历】右子树——【左根右】

后序遍历：为先【遍历】左子树，再【遍历】右子树，最后【遍历】根节点——【左右根】

详细介绍一下遍历：

举例如下图：

先序遍历：ABEKLFCGMHDIJ

解：我们把遍历过程看作是一个递归过程，即每次取两层的树结构来执行遍历。那么按照这个图来执行这样的遍历顺序：首先遍历树ABC，先遍历根节点A，然后遍历树ABC的左子树B，此时B又可以看作是树BEF的根节点，那此时遍历的是树BEF的根节点B，接下来就需要遍历树BEF的左子树E，此时E又可以看作是树EKL的根节点，那此时遍历的是树EKL的根节点E，接下来就需要遍历树EKL的左子树K，此时K不再是任何树的根节点，说明树EKL的左子树遍历完成，再遍历树EKL的右子树L，此时树EKL的先序遍历完成；此时回退遍历树BEF的右子树F，此时树BEF先序遍历完成，再回退遍历树ABC的右子树C。到此该树的根节点->左子树遍历完成：

接下来的分析与上面相同，将该树的整个右子树看作是一个独立的树结构，使用上面的方法，先序遍历该独立树：

那么这个右半边树的先序遍历过程就是：根节点C->左子树G->右子树M->右子树H->右子树D->左子树I->右子树J；

结合上面的左半边子树的遍历过程，整个树的先序遍历过程就是上面的结论。

中序遍历：KELBFAGMCHIDJ

解：依然按照递归的思想执行遍历。首先中序遍历树ABC，在遍历左子树B时，由于B属于树BEF的根节点，按照递归思想，此时需要先遍历树BEF的左子树E，这时又发现左子树E属于树EKL的根节点，那此时就需要先遍历树EKL的左子树K，然后是树EKL的根节点E，再中序遍历树EKL的右子树L，此时树EKL中序遍历完成，回退中序遍历树BEF，此时树EKL整个相当于树BEF的左子树，即已经遍历完成树BEF的左子树，那么接下里遍历树BEF的根节点B，再遍历树BEF的右子树F。到此该树的左子树遍历完成：

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-63033-1.html