1.树的定义
一棵树（tree）是由n（n>0）个元素组成的[有限集合]，其中：
每个元素称为结点（node）；
有一个特定的结点，称为根结点或根（root）；
除根结点外，其余结点被分成m（m>=0）个互不相交的有限集合，而每个子集又都是一棵树（称为原树的子树）
2.二叉树的遍历
二叉树是父节点最多只有两个子节点的特殊树结构，为方便起见，分别为左节点和右节点。
树的数据结构具体如何不再赘述，因为已经烂大街了，随便搜都能搜的到。直接奔向主题：树的四种遍历方式。按照遍历顺序可以分为前序遍历、中序遍历和后序遍历。这前三种遍历均可以使用递归来快速编写还有一个是按照树的深度的层序遍历。由于二叉树只具有两个子节点，还有很多特征，选择二叉树来作为代码实现的对象。首先来看下数据定义：
class BSTNode(object):
"""python，二叉树节点，包含一个数据，两个分支"""
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
/**
* @author Sei
* @title: BST
* @projectName LinkedBST--java
* @description: TODO
* @date 2019/4/2218:58
*/
public class Node<T>{
private Node<T> childLeft = null;
private Node<T> childRight = null;
private T val;
public Node(T val){
this.val = val;
}
public Node<T> getChildLeft() {
return childLeft;
}
public Node<T> getChildRight() {
return childRight;
}
public T getVal() {
return val;
}
public void setChildLeft(Node<T> childLeft) {
this.childLeft = childLeft;
}
public void setChildRight(Node<T> childRight) {
this.childRight = childRight;
}
public void setVal(T val) {
this.val = val;
}
@Override
public String toString() {
return val.toString();
}
}
可以看到以上python和java实现的节点类均是由链接的形式构建，即不是内存的连续区域。接下来看一下树结构的构建，由于本文关注于遍历过程，所以不完全实现树结构，所以完全复制代码可能会导致不能运行的问题。
class LinkedBST(object):
def __init__(self, sourceCollection=None):
self._root = None
self.source = sourceCollection
def __str__(self):
def recurse(node, level):
s = ""
if node != None:
s += recurse(node.right, level + 1)
s += "| " * level
s += str(node.data) + "\n"
s += recurse(node.left, level + 1)
return s
return recurse(self._root, 0)
def isEmpty(self):
def getSize(node):
if node = None:
return 0
else:
return getSize(node.right)+getSize(node.left)+1
if getSize(self.root) == 0:
return True
else:
return False
class LinkedBST<T extends Number> implements BST {
private Node<T> root;
private int size;
public boolean isEmpty() {
if(size(root) == 0){
return true;
}
else return false;
}
public int getSize() {
return size;
}
public LinkedBST(){}
private int size(LinkedBST.Node root){
if(root == null){
return 0;
}
return size(root.getChildLeft())+size(root.getChildRight())+1;
}
2.1前序遍历
已经在前面说过了前序遍历的特点了，访问顺序是根节点-左子树-右子树。上代码：
def preorder(self):
"""前序遍历"""
lyst = list()
def recurse(node):
if node != None:
lyst.append(node.data)
recurse(node.left)
recurse(node.right)
recurse(self._root)
return iter(lyst)
private void recurse(Node<T> ndoe, Consumer fun){
if(this.root == null){
return;
}
else{
fun.accept(node.getVal());
recurse(node.getLeft());
recurse(node.getRight());
}
}
/**
* @description: 前序遍历
* @param ${tags}
* @return ${return_type}
* @throws
* @author Sei
* @date
*/
public void preOrderForeach(Consumer fun){
if(this.root == null){
return;
}
recurse(this.root, fun)
}
稍微做些讲解吧，python代码定义了前序遍历的方法，返回了树里数据的迭代器。java代码里给preOrderForeach的方法传入了一个Consumer的函数式接口，用来接收对遍历数据的操作，比如我可以传入System.out::println即可打印数据。
2.2-2.3中序遍历和后序遍历
换汤不换药，交换上面代码的
lyst.append(node.data)
recurse(node.left)
recurse(node.right)
和
fun.accept(node.getVal());
recurse(node.getLeft());
recurse(node.getRight());
代码的顺序即可实现。
- 中序遍历：左子树-根节点-右子树
- 后续遍历：左子树-右子树-根节点
2.4层序遍历
层序遍历是经常使用的遍历方式，因为树结构其实属于一种图结构，其实树的层序遍历就是图结构的BFS（广度优先遍历）。
上代码（python和java）：
def __iter__(self):
"""层序遍历"""
if not self.isEmpty():
stack = deque()
stack.append(self._root)
while len(stack) != 0:
node = stack.pop()
yield node.data
if node.right != None:
stack.append(node.right)
if node.left != None:
stack.append(node.left)
/**
* @description: 层序遍历
* @param ${tags}
* @return ${return_type}
* @throws
* @author Sei
* @date
*/
public void foreach(Consumer fun){
if(root == null){
return;
}
Queue<Node<T>> queue = new ArrayDeque<>();
queue.add(root);
while(queue.size()>0){
Node<T> node = queue.poll();
fun.accept(node);
if(node.getChildLeft() != null){
queue.add(node.childLeft);
}
if(node.getChildRight() != null){
queue.add(node.childRight);
}
}
}
代码都有一个共同点，就是使用了一个队列（先进先出）来存放父节点。当队列为空时遍历结束，在循环中不断地找父节点连接的子节点，如果不为空则添加到队列中去。就是这样的一个操作。
其实只要把队列换成栈（先进后出）的话就是DFS（深度优先遍历）的方式了，感兴趣的可以思考一下。
