Algorithm | 二分木（binary tree）をPython3で解説

## 二分木とは

二分木とは、2つに分かれていく木構造のこと。

例えば、次のような構造である。

![note_shogo(38).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/716184/c68649f9-105c-c5ef-3f9a-0c9ae7d27ef8.png)

`3`から`2`と`5`の`node`が出ている。

このように1つの`node`から2つ以上の枝が出ないような木構造のことを**二分木**という。

## `node`と枝の作成

`node`または、それをつなげる枝を作成するためには、`class Node:`というものを定義する必要がある。これがないと、`node`同士をつなぐことができない。

```python
class Node(object):
    def __init__(self, label):
        self.label = label
        self.left = None
        self.right = None
```

## 二分木の作成

二分木を作成するためには、**再帰**を用いて、次のようなコードで実装できる。

```python
def insert(node, label):
    if node == None:
        return Node(label)
    
    if label < node.label:
        node.left = insert(node.left, label)
    else:
        node.right = insert(node.right, label)
    return node
```

上図のような二分木にしたいときは、次のように書いてあげると良い。

```python
if __name__ == '__main__':
    root = None
    root = insert(root, 3)
    root = insert(root, 2)
    root = insert(root, 5)
    root = insert(root, 1)
    root = insert(root, 4)
    root = insert(root, 6)
    print(root.label)
    print(root.right.label)
    print(root.left.label)
    print(root.right.left.label)
    print(root.left.left.label)
```

```python
output
>> 3
>> 5
>> 2
>> 4
>> 1
```

それぞれの出力から、場所があっていることがわかる。

また、次のように書いても、同じような出力が得られる。

```python
if __name__ == '__main__':
    root = Node(3)
    root.left = Node(2)
    root.right = Node(5)
    root.left.left = Node(1)
    root.right.left = Node(4)
    root.right.right = Node(6)
    print(root.label)
    print(root.right.label)
    print(root.left.label)
    print(root.right.left.label)
    print(root.left.left.label)
```

```python
output
>> 3
>> 5
>> 2
>> 4
>> 1
```

## 木のなぞり

二分木のなぞりかたには、大きく分けて3種類ある。`inorder`と`preorder`と`postorder`である。

それぞれのコードは以下のように書ける。

### inorder

![note_shogo (20).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/716184/c2aa1302-13b0-c0d0-e053-49c30ae39e50.png)

```python
# inorder
def inorder(node):
    if node != None:
        inorder(node.left)
        print(node.label)
        inorder(node.right)

if __name__ == '__main__':
    root = None
    root = insert(root, 3)
    root = insert(root, 2)
    root = insert(root, 5)
    root = insert(root, 1)
    root = insert(root, 4)
    root = insert(root, 6)
    inorder(root)
```

```python
output
>> 1
>> 2
>> 3
>> 4
>> 5
>> 6
```

`inorder`は、`left`->`label`->`right`の順番になぞるものである。3種類のなかでは最もポピュラーで、よく使われている。

### preorder

![note_shogo (21).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/716184/3ff9adb5-7f21-d0bc-ed89-4b32148996c4.png)

```python
# preorder
def preorder(node):
    if node != None:
        print(node.label)
        preorder(node.left)
        preorder(node.right)

if __name__ == '__main__':
    root = None
    root = insert(root, 3)
    root = insert(root, 2)
    root = insert(root, 5)
    root = insert(root, 1)
    root = insert(root, 4)
    root = insert(root, 6)
    preorder(root)
```

```python
output
>> 3
>> 2
>> 1
>> 5
>> 4
>> 6
```

`preorder`は、`label`->`left`->`right`の順番になぞるものである。木の高層から左側から降りていくようなイメージである。

### postorder

![note_shogo (22).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/716184/5cb668b9-edd8-9022-5dae-ae4b1daa40b6.png)

```python
# postorder
def postorder(node):
    if node != None:
        postorder(node.left)
        postorder(node.right)
        print(node.label)

if __name__ == '__main__':
    root = None
    root = insert(root, 3)
    root = insert(root, 2)
    root = insert(root, 5)
    root = insert(root, 1)
    root = insert(root, 4)
    root = insert(root, 6)
    postorder(root)
```

```python
output
>> 1
>> 2
>> 4
>> 6
>> 5
>> 3
```

`postorder`は、`left`->`right`->`label`の順番になぞるものである。`preorder`に比べると、低層から高層にかけてなぞっていくものである。

#### `postorder`を用いた逆ポーランド記法

また、`postorder`は、工夫すると**逆ポーランド記法**を出力することができる。

![note_shogo (23).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/716184/232525ba-6210-6678-cd3c-bb6a15f48663.png)

```python
# rpn
def rpn(node):
    stack = []
    
    def _rpn(node):
        if node is not None:
            _rpn(node.left)
            _rpn(node.right)
            stack.append(node.label)

            return ' '.join(stack)
    
    return _rpn(node)

if __name__ == '__main__':
    root = Node('-')
    root.left = Node('+')
    root.right = Node('*')
    root.left.left = Node('1')
    root.left.right = Node('2')
    root.right.left = Node('3')
    root.right.right = Node('4')
    print(rpn(root))
```

```python
output
>> 1 2 + 3 4 * -
```