# tree一般樹 *

[toc]

## 為什麼二元樹效率大於一般樹
分支度是以整棵樹中，最大的分支度來算，所以可能有個節點他的分支度為1000 但是其他的為2 ，這棵樹的分支度一樣叫做1000 ，這時就會有link 浪費了，所以binary tree 會比一班tree節省空間， 因為我們一開始在開儲存空間的時候就要依照分支度去開，例如有N個節點就要開１０００ｎ個link 但是實際上有用到的link 只有n-1

樹的定義
----

樹(Tree)屬於一種`非線性結構`，是一種上下階層關係，舉例: 組織架構圖、家族譜、賽程表等，類似一棵倒過來的樹，從`一個樹根(root)開始向下發展許多節點(node)`。

## 樹結構名稱


1. `Node(節點)：`每個Tree所連接到的點，都可被稱作這棵樹的Node(節點)。
2. `Root(根節點或樹根)：`每個Tree最初(或最頂層)的節點，每個Tree都只有一個Root，如: A節點。
3. `Parent(父節點)：`若該節點有下一層連結節點，則該節點為它的父節點，如: B是E的父節點。
4. `Children (子節點)：`若該節點有上一層連結節點，則該節點為它的子節點，如: D、E是B的子節點。
5. `Siblings (兄弟節點):`有共同的父節點之節點，它們稱為兄弟節點，如: F、G為兄弟節點。
6. `Leaf(葉節點)/ Terminal(終端節點)：`沒有子節點的節點，如: H、I、E、F、G都是葉節點/終端節點。
7. `Level(階層)：`該節點所在的水平層級，如: B的階層為2。
8. `Degree (分支度):`該節點的子節點總數，如: B的分支度為2。
9. `Depth(深度)/ Height(高度)：`這棵Tree的總共階層，上圖Tree的深度/高度為4。

>degree 為2 的tree 為binary tree

## 一般樹implemnet

#   Created by Elshad Karimov on 05/06/2020.
#   Copyright © 2020 AppMillers. All rights reserved.

class TreeNode:
    def __init__(self, data, children = []):
        self.data = data
        self.children = children # 子樹的list 
   
    def __str__(self, level=0):
        ret = "  " * level + str(self.data)  + "\n"
        for child in self.children:
            ret += child.__str__(level + 1)
        return ret
    
    def addChild(self, TreeNode):
        self.children.append(TreeNode)  # 把節點放到子樹list 

tree = TreeNode('Drinks', []) # 建立有子樹的Treenode  
cold = TreeNode('Cold', [])
hot = TreeNode('Hot', [])

tree.addChild(cold) 
tree.addChild(hot)
tea = TreeNode('Tea', [])
coffee = TreeNode('Coffee', [])
cola = TreeNode('Cola', [])
fanta = TreeNode('Fanta', [])
cold.addChild(cola)
cold.addChild(fanta)
hot.addChild(tea)
hot.addChild(coffee)
print(tree)