树的二三事(一)

一、树的结构

首先树是建立于物理结构上的逻辑结构，这意味着它是底层实现是允许用List或者Vector来完成。树最重要可以分为三部分:

• 根
• 父节点
• 子节点

而树从每个节点的最大分支数N可以分为N叉树，最常用的是二叉树，即每个节点至多有两个分支。

这里给出一个二叉树节点的定义更方便了解其中关系

class TreeNode{
    int val;
    TreeNode leftChild;
    TreeNode rightChild;
}

这是最普通的树节点定义方法。在树的表示法中，有

• 双亲表示法
• 孩子表示法
• 孩子兄弟表示法

是分别为不同底层物理结构以及应用场景所设计的。

1、双亲表示法

双亲表示法如下

class TreeNode{
    int val;
    int parentPos;
}

之所以定位父节点只用了一个秩Rank去表示，用往往这类树的底层结构是分布紧密的Vector数组结构，是寻秩访问的。

遍历该类树时能够很简单的从某一结点开始循着父节点往上直至根节点。

2、孩子表示法

因为这类表示法是适用于多叉树的，这意味着孩子节点的个数往往是不可知的，因此采用孩子罗列的方式就不合理的，因此可以采用

class TreeNode{
    int val;
    List<TreeNode> child;
}

使用一个可变长度的链表存储孩子，遍历该链表即可访问所有孩子节点。

3、孩子兄弟表示法

这类方法可以将多叉树隐式地转成二叉树的结构，定义如下

class TreeNode{
    int val;
    TreeNode firstchild,nextsibling;
}

其定义了某个节点的首个孩子节点以及当前节点的下一兄弟节点，虽然从节点的关系上两个方向并不平级，但由于是两个出口，因此也可以认为是二叉树的两个子节点。

二、树的遍历方法

多叉树的遍历方式:
1. 前序遍历 VC
2. 后序遍历 CV

二叉树的遍历方式:
1. 前序遍历 VLR
2. 中序遍历 LVR
3. 后序遍历 LRV

V：根节点 C：子节点 L：左孩子 R：右孩子

首先树的遍历用递归是非常简单的，如先序遍历N叉树

List<Integer> result = new ArrayList<>();
class TreeNode{
    int val;
    List<TreeNode> child;
}
public void preorder(TreeNode n){
    if(n==null){
        return;
    }
    result.add(n.val);
    for(TreeNode c:n.child){
        preorder(c);
    }
}
public void postorder(TreeNode n){
    if(n==null){
        return;
    }
    for(TreeNode c:n.child){
        preorder(c);
    }
    result.add(n.val);
}

其区别仅仅只是读取其数据域的那一步的位置（二叉树同理）。
其重点在于如何采用迭代实现，由于其遍历顺序可能会与读取顺序不同，即FILOM，因此便要引入一个能达到这种效果，也就是栈。
这里可以参考我前面一篇文章 N叉树的前后序迭代遍历

关于树的遍历方式还有一种是层次遍历，即遍历是由每个层次由左到右的，这里写出递归及迭代的两个代码

List<ArrayList<Integer>> result = new ArrayList<>();
class TreeNode{
    int val;
    List<TreeNode> child;
}
//思路依然是DFS，遍历过程携带一个当前层级属性
//采用一个二维结构存遍历的数据
//遍历完成只要再遍历这个二维结构就完成了
public void levelTraversalRecursion(TreeNode n,int level){
    List<Integer> curLevel = null;
    if(level>result.size()){
        curLevel = result.add(new ArrayList<Integer>());
    }else{
        curLevel = result.get(level-1);
    }
    curLevel.add(n.val);
    for(TreeNode c:n.child){
        levelTraversalRecursion(c,level+1);
    }
}
//因为遵守了FIFO，迭代反而更适合层次遍历
//引入一个队列即可完美地实现层次遍历
List<Integer> result = new ArrayList<>();
Queue<TreeNode> store = new Queue<>();
public void levelTraversal(TreeNode root){
    store.add(root)
    while(!store.isEmpty())
    {
        TreeNode temp = store.poll();
        result.add(temp.val);
        for(TreeNode c:temp.cild){
            store.add(c);
        }
    }
}