BST,bst

二元樹

Posted by Jason Wong on March 16, 2019

民國108年3月16日

說明:文章關於二元樹的算法根據 “Data Structures and Algorithms:Annotated Reference with Examples” 這本書的僞代碼通過C++實現而得，此外本文用於說明的插圖也出自此書。 1.二元樹的結構 (1).data, 左子樹，右子樹

typedef struct bTree {
    int data;
    bTree *left;
    bTree *right;
} node;

parent->left->data < parent->data;
parent->right->data > parent->data;

二元樹的特點：左子樹的值小於父節點的值，右子樹的值大於父節點的值，最終，二元樹左側的數據小於右測的數據。

2.創建新節點：createNewNode

node *createNewNode(int value) {
    node *newNode = new(node);
    newNode->data = value;
    newNode->left = nullptr;
    newNode->right = nullptr;
    return newNode;
}

3.添加新值.insertNode(node *current, node *newNode

void insertNode(node *current, node *newNode) {
    if (newNode->data < current->data) {
        if (current->left == nullptr) {   //若無左子樹
            current->left = newNode;    //添加新節點，操作完成。
        } else {    //否則current->left作爲新的查找節點，繼續遞歸查找，直到current->left == nullptr || current->right == nullptr
            insertNode(current->left, newNode);
        }
    } else {
        if (current->right == nullptr) {
            current->right = newNode;
        } else {
            insertNode(current->right, newNode);
        }
    }
}
此函式的作用是添加新節點到二元樹裏。首先比較要插入節點的元素值和當前插入點的元素值之大小，若小於當前元素之值，則插入當前元素之左側;若當前節點無左子樹，則直接添加作爲當前節點的左子樹;否則再遞歸進入current->left繼續判斷，直到找出此二元樹的葉子節點，再添加。

void insert(node **root, int value) {
    node *temp = createNewNode(value);  //創建存儲新值的節點
    if (*root == nullptr) {   //若樹爲空，直接添加作爲根節點
        *root = temp;
    } else {   //否則執行insertNode函式查找葉子節點插入
        insertNode(*root, temp);
    }
}

4.二元樹的四種遍歷方式 4.1前序遍歷

void printPreOrder(node *root) {
    if (root == nullptr) {
        return;
    }
    std::cout << root->data << "    ";
    printPreOrder(root->left);
    printPreOrder(root->right);
}

先序遍歷順序：根節點–>左子樹–>右子樹。遍歷過程如下圖所示,圖出自”Data Structures and Algorithms: Annotated Reference with Examples”，第27頁:

4.2中序遍歷

void printInOrder(node *root) {
    if (root == nullptr) {
        return;
    } else {
        printInOrder(root->left);
        std::cout << root->data << "    ";
        printInOrder(root->right);
    }
}

中序遍歷順序:左子樹–>根節點–>右子樹，如下圖所示,圖出自”Data Structures and Algorithms: Annotated Reference with Examples”，第29頁:

4.3後序遍歷

void printPostOrder(node *root) {
    if (root == nullptr) {
        return;
    }
    printPostOrder(root->left);
    printPostOrder(root->right);
    std::cout << root->data << "    ";
}

後序遍歷，順序：左子樹–>右子樹–>根節點，如下圖所示,圖出自”Data Structures and Algorithms: Annotated Reference with Examples”，第28頁:

4.4按樹的深度遍歷 即每次遍歷完成一層的深度後再往下遍歷之。需要std::queue輔助保存當前遍歷節點之位置;std::vector保存所遍歷的每一個節點的值，這樣vector裏的數據就會按由小到大的順序排列。

void breadthFirst(node *root) {
    std::queue<node *> queue;
    std::vector<int> vector;

    while (root != nullptr) {
        vector.emplace_back(root->data);
        if (root->left != nullptr) {
            queue.push(root->left);
        }
        if (root->right != nullptr) {
            queue.push(root->right);
        }
        if (!queue.empty()) {
            root = queue.front();
            queue.pop();
        } else {
            root = nullptr;
        }
    }
    auto it = vector.begin();
    std::cout << "Breadth first.........." << std::endl;
    for (; it != vector.end(); ++it) {
        std::cout << *it << "   ";
    }
    std::cout << "\n";
}

5.一些輔助函式 5.1contains(node *root, int value) 作用是驗證給定的value是否在二元樹root中

bool contains(node *root, int value) {
    if (root == nullptr) {
        std::cout << "The value: " << value << " not contained in the node!" << std::endl;
        return false;
    }
    if (root->data == value) {
        std::cout << "The value: " << value << "  contains in the node!" << std::endl;
        return true;
    } else if (value < root->data) {
        std::cout << "Left node..." << std::endl;
        return contains(root->left, value);
    } else if (value > root->data) {
        std::cout << "Right node..." << std::endl;
        return contains(root->right, value);
    }
}

5.2.findParent(node *root, int value) 作用：通過給定value查找此value的parent節點;成功：返回此value的parent節點，失敗：返回nullptr

node *findParent(node *root, int value) {
    if (value == root->data) {
        std::cout << "The hight of node is 1" << std::endl;
        return root;
    }
    if (value < root->data) {
        if (root->left == nullptr) {
            return nullptr;
        } else if (value == root->left->data) {
            std::cout << "Left node..." << std::endl;
            return root;
        } else {
            return findParent(root->left, value);
        }
    } else {
        if (root->right == nullptr) {
            return nullptr;
        } else if (value == root->right->data) {
            std::cout << "Right node..." << std::endl;
            return root;
        } else {
            return findParent(root->right, value);
        }
    }
}

5.3.findNode(node *root, int value) 作用：通過給定value查找此value的節點;成功：返回此value的節點，失敗：返回nullptr

node *findNode(node *root, int value) {
    if (root == nullptr) {
        std::cout << "Empty node" << std::endl;
        return nullptr;
    }
    if (value == root->data) {
        return root;
    } else if (value < root->data) {
        std::cout << "Left node..." << std::endl;
        return findNode(root->left, value);
    } else if (value > root->data) {
        std::cout << "Right node..." << std::endl;
        return findNode(root->right, value);
    }
}

5.4.countAllNode(node *root) 作用：計算二元樹的節點數, 成功：返回二元樹的節點數.

int countAllNode(node *root) {
    if (root == nullptr) {
        return 0;
    }
    return countAllNode(root->left) + countAllNode(root->right) + 1;
}

5.5.findSmallest(node *parent) 作用：查找二元樹中最小值的節點,成功：返回包含最小值的節點。

node *findSmallest(node *parent) {
    if (parent->left == nullptr) {
        return parent;
    }
    return findSmallest(parent->left);
}

5.6.findLargest(node *parent) 作用：查找二元樹最大值的節點，成功：返回包含最大值的節點。

node *findLargest(node *parent) {
    if (parent->right == nullptr) {
        return parent;
    }
    return findLargest(parent->right);
}

6.remove(node **root, int value) 作用：刪除二元樹中包含value值的節點，此函式是本文章中最複雜的。刪除節點時有五種情況需要考慮: (1).二元樹只有一個節點 (2).要刪除的節點是葉子節點，即其下面無左子樹與右子樹 (3).要刪除的節點有左子樹，無右子樹 (4).要刪除的節點有右子樹，無左子樹 (5).要刪除的節點有左子樹和右子樹

bool remove(node **root, int value) {
    node *nodeToRemove = findNode(*root, value);
    if (nodeToRemove == nullptr) {
        std::cout << "Value not in BST" << std::endl;
        return false;
    }
    node *parent = findParent(*root, value);
    int count = countAllNode(*root);
    if (count == 1) {
        std::cout << "We are removing the only node in the BST" << std::endl;
        delete *root;
        *root = nullptr;
    } else if (nodeToRemove->left == nullptr && nodeToRemove->right == nullptr) {
        std::cout << "Node to remove is a leaves node" << std::endl;
        if (nodeToRemove->data < parent->data) {
            parent->left = nullptr;
            delete parent->left;
        } else {
            parent->right = nullptr;
            delete parent->right;
        }
    } else if (nodeToRemove->left == nullptr && nodeToRemove->right != nullptr) {
        std::cout << "The node to remove has right node" << std::endl;
        if (nodeToRemove->data < parent->data) {
            parent->left = nodeToRemove->right;
            delete nodeToRemove;
        } else {
            parent->right = nodeToRemove->right;
            delete nodeToRemove;
        }
    } else if (nodeToRemove->left != nullptr && nodeToRemove->right == nullptr) {
        std::cout << "The node to remove has left node" << std::endl;
        if (nodeToRemove->data < parent->data) {
            parent->left = nodeToRemove->left;
            delete nodeToRemove;
        } else {
            parent->right = nodeToRemove->left;
            delete nodeToRemove;
        }
    } else {
        std::cout << "The node to remove has both left node and right node" << std::endl;
        //find the largest value in the left node OR find the smallest value in the right node.
            //查找nodeToRemove的右節點的最小值
 //        node *smallest = findSmallest(nodeToRemove->right);  
 	   //找到此最小值的父節點
//         node *smallesetParent = findParent(smallest, smallest->data); 
             //把最小值節點的右節點賦值給smallest父節點的左子樹
 //        smallesetParent->left = smallest->right; 
            //使用最小值smallest->data替換nodeToRemove->data
//         nodeToRemove->data = smallest->data;    
             //刪除之
 //        delete smallest; 
	
	//查找nodeToRemove的左節點的最大值
        node *largest = findLargest(nodeToRemove->left);   
        //找largest的父節點
        node *largestParent = findParent(largest, largest->data);   
        //largest只有左節點，否則它就不是最大值。把largest的左節點和largestParent的右節點連接
        largestParent->right = largest->left;  
        nodeToRemove->data = largest->data;    
        //使用最大值largest->data替換nodeToRemove的值
        delete largest;   //delete largest
    }
    return true;
}

圖解如下:

a),b)說明刪除的節點只有一個子樹的情況，a)要刪除z,即值爲16的節點，首先找到其子樹,b)把z的子樹和z的父節點連接，最後刪除z. c)說明z，即值爲5的節點是要刪除的節點： (1)首先查找z的右子樹最小值或z的左子樹的最大值。圖片是查找z的右子樹最小值，注意查找到的最大/最小值的節點只有一個子節點。比如這裏，找到的z的右子樹y的最小值是6,此節點只會有一個右子樹，值爲7;若y還有一個左子樹，那麼y就不會是包含最小值的節點;同理，找左子樹的最大值也是這個道理。 (2)接下來把值爲7的節點和y的父節點連接; (3)把找到的右子樹的最小值和要刪除節點的值交換，這裏是把y的值和z的值交換，此時z=6,再刪除y節點。