数据结构（三）树

一种便于查找访问的数据结构。

表示

一种表示法是

struct TreeNode{
    object obj;
    TreeNode *firstChild;
    TreeNode *nextSibling;
}

其中有两个指针，第一个指向它的第一个子节点，第二个指向自己的同级节点。

原因主要是子节点数量不确定，这样表示可以节省空间，并且有不错的灵活性。

遍历

前序遍历

就是类似于tree展示的文件目录树。节点在子节点前被处理。

后序遍历

先处理子节点，再处理当前节点。例如目录体积的计算。

应用

表达式树

这是一个二叉树，树叶是操作数，节点是运算符。

二叉树具有固定的子节点数量，所以除了前/后序遍历，还引入了中序遍历。先处理左边的子节点，再处理自身，最后处理右边的子节点。