---
# System prepended metadata

title: Binary Tree
tags: [Coding]

---

---
tags: Coding
---
# Binary Tree
## [二元數的找法(文章連結)](http://alrightchiu.github.io/SecondRound/binary-tree-traversalxun-fang.html#ex_code)
### **InorderSuccessor**
這是**InorderSuccessor**找到下一個節點並印出的方法，而**InorderPredecessor**是找到上一個，方法就是反過來。
![](https://github.com/alrightchiu/SecondRound/blob/master/content/Algorithms%20and%20Data%20Structures/Tree%20series/BinaryTree_fig/Traversal/f22.png?raw=true =400x)
#### 暴力建樹
```cpp=
int main(){

    ...
    // link parent pointer
    nodeB->parent = nodeA; nodeC->parent = nodeA;
    nodeD->parent = nodeB; nodeE->parent = nodeB;
    nodeG->parent = nodeE; nodeH->parent = nodeE;
    nodeF->parent = nodeC; 
    nodeI->parent = nodeF;
    ...

}

// inside definition of class BinaryTree
class BinaryTree{
public:
    TreeNode *root;         // 以root作為存取整棵樹的起點
    BinaryTree():root(0){};
    BinaryTree(TreeNode *node):root(node){};

    void Preorder(TreeNode *current);
    void Inorder(TreeNode *current);
    void Postorder(TreeNode *current);
    void Levelorder();

    TreeNode* leftmost(TreeNode *current);
    TreeNode* rightmost(TreeNode *current);

    TreeNode* InorderSuccessor(TreeNode *current);
    TreeNode* InorderPredecessor(TreeNode *current);

    void Inorder_by_parent(TreeNode *root);
    void Inorder_Reverse(TreeNode *root);
};
```
#### 找最左邊點 leftmost()
```cpp=
TreeNode* BinaryTree::leftmost(TreeNode *current){
    while (current->leftchild != NULL){
        current = current->leftchild;
    }
    return current;
}
```
#### 找下一個點 InorderSuccessor()
```cpp=
TreeNode* BinaryTree::InorderSuccessor(TreeNode *current){
    if (current->rightchild != NULL){
        return leftmost(current->rightchild);
    }

    // 利用兩個pointer: successor與current做traversal 

    TreeNode *successor = current->parent;   
    while (successor != NULL && current == successor->rightchild) {
        current = successor;
        successor = successor->parent;
    }
    return successor;
}
```
#### 合併印出 Inorder_by_parent()
```cpp=
void BinaryTree::Inorder_by_parent(TreeNode *root){
    TreeNode *current = new TreeNode;
    current = leftmost(root);

    while(current){
        std::cout << current->str << " ";
        current = InorderSuccessor(current);
    }
}
```
### queue實用在Level-Order Traversal
Level-Order Traversal就是依照字母順序由左而右、由上至下排列。運用queue先進先出的概念一層一層印完才往下一層。
![](https://github.com/alrightchiu/SecondRound/blob/master/content/Algorithms%20and%20Data%20Structures/Tree%20series/BinaryTree_fig/Traversal/f21.png?raw=true =400x)
```cpp=
void BinaryTree::Levelorder(){

    std::queue<TreeNode*> q;
    q.push(this->root);                     // 把root作為level-order traversal之起點
                                            // 推進queue中
    while (!q.empty()){                     // 若queue不是空的, 表示還有node沒有visiting

        TreeNode *current = q.front();      // 取出先進入queue的node
        q.pop();                          
        std::cout << current->str << " ";   // 進行visiting

        if (current->leftchild != NULL){    // 若leftchild有資料, 將其推進queue
            q.push(current->leftchild);
        }
        if (current->rightchild != NULL){   // 若rightchild有資料, 將其推進queue
            q.push(current->rightchild);
        }
    }
}
```
## [二元數的建立(文章連結)](http://alrightchiu.github.io/SecondRound/binary-tree-jian-li-yi-ke-binary-tree.html#description)
### 主程式包括建立與印出
x代表是空的
![](https://github.com/alrightchiu/SecondRound/blob/master/content/Algorithms%20and%20Data%20Structures/Tree%20series/BinaryTree_fig/Construct_from_char_array/f2.png?raw=true =400x)
```cpp=
#include <iostream>
#include <sstream>
#include <queue>

int main() {
    const char *a = "A B C D E F x x x G H x I";
    BinaryTree T(a);                // 以level-order規則建立Binary Tree
    T.Inorder_by_parent();      // 以inorder-traversal印出Binary Tree
    std::cout << std::endl;

    T.InsertLevelorder('K');
    T.InsertLevelorder('L');
    T.InsertLevelorder('M');
    T.InsertLevelorder('N');
    T.Inorder_by_parent();
    std::cout << std::endl;

    return 0;
}
```
### 建立一棵樹，但比上面的方法好
```cpp=
class BinaryTree;
class TreeNode{
private:
    TreeNode *leftchild;
    TreeNode *rightchild;
    TreeNode *parent;
    char data;
public:
    TreeNode():leftchild(0),rightchild(0),parent(0),data('x'){};
    TreeNode(char s):leftchild(0),rightchild(0),parent(0),data(s){};

    friend class BinaryTree;
};

class BinaryTree{
private:
    TreeNode *root;
public:
    BinaryTree():root(0){};
    BinaryTree(const char* str);

    void LevelorderConstruct(std::stringstream &ss);
    void InsertLevelorder(char data);

    TreeNode* leftmost(TreeNode *current);
    TreeNode* InorderSuccessor(TreeNode *current);
    void Inorder_by_parent();
};
```
#### BinaryTree()
```cpp=
BinaryTree::BinaryTree(const char* str){
    std::stringstream  ss;
    ss << str;                     // magic!

    root = new TreeNode;           // allocate memory for root
    ss >> root->data;              // assign character to root

    LevelorderConstruct(ss);
}
```
#### LevelorderConstruct()
```cpp=
void BinaryTree::LevelorderConstruct(std::stringstream &ss){

    std::queue<TreeNode*> q;         // create a queue to handle level-roder rule
    TreeNode *current = root;        // point *current to root
    char data = 'x';                 // initializa data as 'x'

    while (ss >> data) {
        if (data >= 65 && data <= 90){                // 處理current的leftchild
            TreeNode *new_node = new TreeNode(data);  // call constructor TreeNode(char s)
            new_node->parent = current;
            current->leftchild = new_node;
            q.push(new_node);
        }
        if (!(ss >> data)){                           // 有可能char array含有奇數筆資料
            break;                                    // 所以在這裡結束迴圈
        }
        if (data >= 65 && data <= 90){                // 處理current的rightchild
            TreeNode *new_node = new TreeNode;        // call constructor TreeNode()
            new_node->parent = current;
            current->rightchild = new_node;
            new_node->data = data;                    // assign data to new_node
            q.push(new_node);
        }
        current = q.front();                          // 從queue中更新current
        q.pop();                                      // 更新queue
    }
}
```
#### InsertLevelorder()
樹建立完後還想增加節點，為了節省樹的層數，把新字母插進空缺。像是塞入K。
![](https://github.com/alrightchiu/SecondRound/blob/master/content/Algorithms%20and%20Data%20Structures/Tree%20series/BinaryTree_fig/Construct_from_char_array/f16.png?raw=true =400x)
```cpp=
void BinaryTree::InsertLevelorder(char data){    

    std::queue<TreeNode*> q;
    TreeNode *current = root;

    while (current) {
        if (current->leftchild != NULL){               // current的leftchild沒有空位
            q.push(current->leftchild);                // 將其推進queue中
        }
        else{                                          // current的leftchild有空位
            TreeNode *new_node = new TreeNode(data);   // 建立新的node, 將字母放在這裡
            new_node->parent = current;
            current->leftchild = new_node;
            break;                         
        }
        if (current->rightchild != NULL) {             // current的rightchild沒有空位
            q.push(current->rightchild);               // 將其推進queue中
        }
        else{                                          // current的rightchild有空位
            TreeNode *new_node = new TreeNode(data);   // 建立新的node, 將字母放在這裡
            new_node->parent = current;                
            current->rightchild = new_node;
            break;
        }
        current = q.front();
        q.pop();
    }
}
```

