# 树

## 二叉树

所有非叶子结点至多拥有两个儿子（Left和Right）； 所有结点存储一个关键字 非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树

![Binary tree](https://2948810407-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LO_t_97Q_1lSd1D0sBF%2F-LO_thdMLDnF8PMuxKJq%2F-LO_tkC23gooCFA6ziGZ%2Funbalanced-b-tree.jpg?generation=1539307934967209\&alt=media)

先序：35 17 9 28 39 65

中序：9 17 28 35 39 65

后序：9 28 17 65 39 35

**三种遍历方法的考查顺序一致，得到的结果却不一样，原因在于：**

**先序：**&#x8003;察到一个节点后，即刻输出该节点的值，并继续遍历其左右子树。(根左右)

**中序：**&#x8003;察到一个节点后，将其暂存，遍历完左子树后，再输出该节点的值，然后遍历右子树。(左根右)

**后序：**&#x8003;察到一个节点后，将其暂存，遍历完左右子树后，再输出该节点的值。(左右根)
