1.樹的定義

一棵樹（tree）是由n（n>0）個元素組成的[有限集合]，其中：

• 每個元素稱為結(jié)點（node）；

• 有一個特定的結(jié)點，稱為根結(jié)點或根（root）；

• 除根結(jié)點外，其余結(jié)點被分成m（m>=0）個互不相交的有限集合，而每個子集又都是一棵樹（稱為原樹的子樹）

2.二叉樹的遍歷

二叉樹是父節(jié)點最多只有兩個子節(jié)點的特殊樹結(jié)構(gòu)，為方便起見，分別為左節(jié)點和右節(jié)點。
樹的數(shù)據(jù)結(jié)構(gòu)具體如何不再贅述，因為已經(jīng)爛大街了，隨便搜都能搜的到。直接奔向主題：樹的四種遍歷方式。按照遍歷順序可以分為前序遍歷、中序遍歷和后序遍歷。這前三種遍歷均可以使用遞歸來快速編寫還有一個是按照樹的深度的層序遍歷。由于二叉樹只具有兩個子節(jié)點，還有很多特征，選擇二叉樹來作為代碼實現(xiàn)的對象。首先來看下數(shù)據(jù)定義：

class BSTNode(object):
    """python，二叉樹節(jié)點，包含一個數(shù)據(jù)，兩個分支"""
    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實現(xiàn)的節(jié)點類均是由鏈接的形式構(gòu)建，即不是內(nèi)存的連續(xù)區(qū)域。接下來看一下樹結(jié)構(gòu)的構(gòu)建，由于本文關(guān)注于遍歷過程，所以不完全實現(xiàn)樹結(jié)構(gòu)，所以完全復(fù)制代碼可能會導(dǎo)致不能運行的問題。

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前序遍歷

已經(jīng)在前面說過了前序遍歷的特點了，訪問順序是根節(jié)點-左子樹-右子樹。上代碼：

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代碼定義了前序遍歷的方法，返回了樹里數(shù)據(jù)的迭代器。java代碼里給preOrderForeach的方法傳入了一個Consumer的函數(shù)式接口，用來接收對遍歷數(shù)據(jù)的操作，比如我可以傳入System.out::println即可打印數(shù)據(jù)。

2.2-2.3中序遍歷和后序遍歷

換湯不換藥，交換上面代碼的

lyst.append(node.data)
recurse(node.left)
recurse(node.right)

和

fun.accept(node.getVal());
recurse(node.getLeft());
recurse(node.getRight());

代碼的順序即可實現(xiàn)。

• 中序遍歷：左子樹-根節(jié)點-右子樹
• 后續(xù)遍歷：左子樹-右子樹-根節(jié)點

2.4層序遍歷

層序遍歷是經(jīng)常使用的遍歷方式，因為樹結(jié)構(gòu)其實屬于一種圖結(jié)構(gòu)，其實樹的層序遍歷就是圖結(jié)構(gòu)的BFS（廣度優(yōu)先遍歷）。
上代碼（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);
            }
        }
    }

代碼都有一個共同點，就是使用了一個隊列（先進先出）來存放父節(jié)點。當(dāng)隊列為空時遍歷結(jié)束，在循環(huán)中不斷地找父節(jié)點連接的子節(jié)點，如果不為空則添加到隊列中去。就是這樣的一個操作。
其實只要把隊列換成棧（先進后出）的話就是DFS（深度優(yōu)先遍歷）的方式了，感興趣的可以思考一下。