---
tags: Coding
---
# Binary Tree
## [二元數的找法(文章連結)](http://alrightchiu.github.io/SecondRound/binary-tree-traversalxun-fang.html#ex_code)
### **InorderSuccessor**
這是**InorderSuccessor**找到下一個節點並印出的方法，而**InorderPredecessor**是找到上一個，方法就是反過來。
#### 暴力建樹
```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先進先出的概念一層一層印完才往下一層。
```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代表是空的
```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。
```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();
}
}
```
Sign in with Wallet
Connect another wallet