在上一篇筆記有提到樹的觀念，現在這一篇筆記將會進行樹的實作
完成整棵樹的實作需要先進行節點的定義
這篇筆記以vector紀錄子節點，好處是方便編寫閱讀，還有便於新增子節點
要實作整棵樹之前需要先完成樹節點的定義
以下是節點的成員變數
DataType data;紀錄節點的資料
Node *parent; 紀錄節點的父節點
vector<Node *> childs; 紀錄節點的子節點
然後是新增子節點的成員函數，在節點的定義中就寫好新增子節點的函數有助於接下來在樹中新增子節點的函數編寫。
Node<DataType> *addChild(const DataType value)中以節點為回傳形式的理由會在之後提到
// 樹節點類定義 template <typename DataType> class Node { friend class Tree<DataType>; public: Node(DataType content) : data(content) {} // 以節點的類新增子節點的程式 Node<DataType> *addChild(const DataType value) { Node *newchild = new Node(value); newchild->parent = this; this->childs.push_back(newchild); return newchild; } DataType getdata() { return data; } private: DataType data; Node *parent; vector<Node *> childs; }; |
接下來是樹的類定義
如同註解寫到的成員變數只有Node<Type> *RootNode 就能記錄整棵樹了
一棵樹只需要紀錄根節點就能透過根節點的子節點紀錄整棵樹，原因是我們能透過RootNode的子節點vector<Node *> childs再去訪問這些子節點的vector<Node *> childs，以此達到訪問整棵樹的操作。
成員函式void addroot(Node<Type> *newroot)用於給這棵樹新增根節點，在主程式宣告一個節點之後就能用這個函式給一棵樹定義他的根節點。
然後是遍歷整棵樹的程式，遍歷方式Preorder traversal前序遍歷和Postorder Traversal後序遍歷的規則都在上一篇筆記資料結構筆記 樹(Tree)的觀念中有提到。
使用Preorder traversal前序遍歷的void PreorderPrint(Node<Type> *rootnode)將cout << current->data << " "; 這行印出資料的程式寫在For迴圈前的目的是要讓程式在進入遞迴前，先印出目前的節點的資料再去訪問子節點，如此就能完成先印出根節點、再印出第一個子節點、然後印出第一個子節點的子節點，第一個子節點組成的子樹都訪問完再去訪問第二個子節點，以此類推的操作。
使用vector紀錄子節點的優點也在這裡展現出來，透過迭代器與ｆｏｒ迴圈就能簡單的訪問完一個節點的所有子節點。
到了使用Postorder Traversal後序遍歷的void PostorderPrint(Node<Type> *rootnode)則是相反，先完成子節點的遞迴再印出節點的資料，以此完成後序遍歷的操作。
| // 以Preorder Traversal前序遍歷印出整棵樹 void PreorderPrint(Node<Type> *rootnode) const { Node<Type> *current = rootnode; cout << current->data << " "; // 先印出節點的資料再進入遞迴子節點的過程 for (typename vector<Node<Type> *>::const_iterator it = current->childs.begin(); it != current->childs.end(); it++) { PreorderPrint(*it); } } // 以Postorder Traversal 後序遍歷印出整棵樹 void PostorderPrint(Node<Type> *rootnode) const { Node<Type> *current = rootnode; // 先進行子節點的遞迴再印出節點的資料 for (typename vector<Node<Type> *>::const_iterator it = current->childs.begin(); it != current->childs.end(); it++) { PostorderPrint(*it); } cout << current->data << " "; } |
再來是刪除節點的函式void deleteNode(Node<Type> *rootnode, Type Dnode)與刪除子樹的函式void deleteSubtree(Node<Type> *rootnode)，特別的是需要刪除子樹的函式才能完成刪除節點的函式。
在void deleteSubtree(Node<Type> *rootnode)中利用遞迴完成刪除整顆子樹的操作，以此才能在void deleteNode(Node<Type> *rootnode, Type Dnode)中完成刪除整顆以該節點為根節點的子樹的操作。
接著是直接在樹中新增節點的
Node<Type> *addChildInTree(Node<Type> *rootnode, Type TargeNode, Type NodeData)
rootnode是這棵樹的根節點
TargeNode是要新增新的子節點的節點資料
NodeData則是要新增的節點資料
在節點的類定義中Node<DataType> *addChild(const DataType value)會回傳資料型態為Node＊的結果，而在樹中新增節點的操作就是利用這點。
在這段程式會檢測目前訪問的節點是否是要新增資料的目標節點，如果是，就會回傳rootnode->addChild(NodeData)的結果，這樣會完成在目標節點新增節點的操作，並回傳新增節點的指針。
而在這裡，如果遍歷完所有子節點都沒有找到目標的節點就會回傳nullptr，而在result未接受到回傳的新增節點的指針前都是空指針，程式就會持續尋找目標節點直到完成新增的動作。
| Node<Type> *addChildInTree(Node<Type> *rootnode, Type TargeNode, Type NodeData) { if (RootNode == nullptr) { cout << "Error: Tree is empty." << endl; return nullptr; } if (rootnode->data == TargeNode) { return rootnode->addChild(NodeData); } Node<Type> *current = rootnode; for (typename vector<Node<Type> *>::const_iterator it = current->childs.begin(); it != current->childs.end(); it++) { Node<Type> *result = addChildInTree((*it), TargeNode, NodeData); if (result != nullptr) { return result; // 找到目標節點，立即返回結果 } } return nullptr; // 如果在子節點中找不到目標節點，返回 nullptr } |
在這段程式會檢測目前訪問的節點是否是要新增資料的目標節點，如果是，就會回傳rootnode->addChild(NodeData)的結果，這樣會完成在目標節點新增節點的操作，並回傳新增節點的指針。
| if (rootnode->data == TargeNode) { return rootnode->addChild(NodeData); } |
而在這裡，如果遍歷完所有子節點都沒有找到目標的節點就會回傳nullptr，而在result未接受到回傳的新增節點的指針前都是空指針，程式就會持續尋找目標節點直到完成新增的動作。
| Node<Type> *current = rootnode; for (typename vector<Node<Type> *>::const_iterator it = current->childs.begin(); it != current->childs.end(); it++) { Node<Type> *result = addChildInTree((*it), TargeNode, NodeData); if (result != nullptr) { return result; // 找到目標節點，立即返回結果 } } return nullptr; // 如果在子節點中找不到目標節點，返回 nullptr |
下方的Node<Type> *FindNode(Node<Type> *rootnode, Type TargetNode)也是利用相同的原理，直到找到目標節點前都是回傳空指針，程式在找到目標節點前都會繼續執行。
整段樹的類定義的程式
// 樹的類定義 template <typename Type> class Tree { private: Node<Type> *RootNode; // 一棵樹只需要紀錄根節點就能透過根節點的子節點紀錄整棵樹 public: Tree() : RootNode(nullptr) {} // 新增根結點 void addroot(Node<Type> *newroot) { if (RootNode == nullptr) { RootNode = newroot; } else { cout << "Error: Only one root allowed." << endl; } } // 以Preorder Traversal前序遍歷印出整棵樹 void PreorderPrint(Node<Type> *rootnode) const { Node<Type> *current = rootnode; cout << current->data << " "; // 先印出節點的資料再進入遞迴子節點的過程 for (typename vector<Node<Type> *>::const_iterator it = current->childs.begin(); it != current->childs.end(); it++) { PreorderPrint(*it); } } // 以Postorder Traversal 後序遍歷印出整棵樹 void PostorderPrint(Node<Type> *rootnode) const { Node<Type> *current = rootnode; // 先進行子節點的遞迴再印出節點的資料 for (typename vector<Node<Type> *>::const_iterator it = current->childs.begin(); it != current->childs.end(); it++) { PostorderPrint(*it); } cout << current->data << " "; } void deleteNode(Node<Type> *rootnode, Type Dnode) { if (rootnode == nullptr) { cout << "Error: Tree is empty." << endl; return; } Node<Type> *current = rootnode; if (rootnode->data == Dnode) { // 如果目標節點是根節點，刪除整棵樹 deleteSubtree(rootnode); RootNode = nullptr; cout << "Tree deleted." << endl; return; } for (typename vector<Node<Type> *>::const_iterator it = current->childs.begin(); it != current->childs.end(); it++) { if ((*it)->data == Dnode) { deleteSubtree(*it); cout << "SubTree deleted." << endl; return; } deleteNode((*it), Dnode); } } void deleteSubtree(Node<Type> *rootnode) { // 遞迴刪除子樹 for (typename vector<Node<Type> *>::iterator it = rootnode->childs.begin(); it != rootnode->childs.end(); ++it) { deleteSubtree(*it); delete *it; } rootnode->childs.clear(); // 清空子節點向量 } // 查詢節點的子節點 void getChildren(Node<Type> *Tnode) const { for (typename vector<Node<Type> *>::const_iterator it = Tnode->childs.begin(); it != Tnode->childs.end(); it++) { cout << (*it)->data << " "; } return; } Node<Type> *addChildInTree(Node<Type> *rootnode, Type TargeNode, Type NodeData) { if (RootNode == nullptr) { cout << "Error: Tree is empty." << endl; return nullptr; } if (rootnode->data == TargeNode) { return rootnode->addChild(NodeData); } Node<Type> *current = rootnode; for (typename vector<Node<Type> *>::const_iterator it = current->childs.begin(); it != current->childs.end(); it++) { Node<Type> *result = addChildInTree((*it), TargeNode, NodeData); if (result != nullptr) { return result; // 找到目標節點，立即返回結果 } } return nullptr; // 如果在子節點中找不到目標節點，返回 nullptr } Node<Type> *FindNode(Node<Type> *rootnode, Type TargetNode) { if (RootNode == nullptr) { cout << "Error: Tree is empty." << endl; return nullptr; } if (rootnode->data == TargetNode) { return rootnode; } Node<Type> *current = rootnode; for (typename vector<Node<Type> *>::const_iterator it = current->childs.begin(); it != current->childs.end(); it++) { Node<Type> *result = FindNode(*it, TargetNode); if (result != nullptr) { return result; // 找到目標節點，立即返回結果 } } return nullptr; // 如果在子節點中找不到目標節點，返回 nullptr } // 查詢節點的父節點 Node<Type> *getParent(Node<Type> *Tnode) const { return Tnode->parent; } Node<Type> *getRoot() const { return RootNode; } }; |
完整程式與測試用的主程式：
| #include <iostream> #include <vector> using namespace std; template <typename DataType> class Tree; // 樹節點類定義 template <typename DataType> class Node { friend class Tree<DataType>; public: Node(DataType content) : data(content) {} // 以節點的類新增子節點的程式 Node<DataType> *addChild(const DataType value) { Node *newchild = new Node(value); newchild->parent = this; this->childs.push_back(newchild); return newchild; } DataType getdata() { return data; } private: DataType data; Node *parent; vector<Node *> childs; }; // 樹的類定義 template <typename Type> class Tree { private: Node<Type> *RootNode; // 一棵樹只需要紀錄根節點就能透過根節點的子節點紀錄整棵樹 public: Tree() : RootNode(nullptr) {} // 新增根結點 void addroot(Node<Type> *newroot) { if (RootNode == nullptr) { RootNode = newroot; } else { cout << "Error: Only one root allowed." << endl; } } // 以Preorder Traversal前序遍歷印出整棵樹 void PreorderPrint(Node<Type> *rootnode) const { Node<Type> *current = rootnode; cout << current->data << " "; // 先印出節點的資料再進入遞迴子節點的過程 for (typename vector<Node<Type> *>::const_iterator it = current->childs.begin(); it != current->childs.end(); it++) { PreorderPrint(*it); } } // 以Postorder Traversal 後序遍歷印出整棵樹 void PostorderPrint(Node<Type> *rootnode) const { Node<Type> *current = rootnode; // 先進行子節點的遞迴再印出節點的資料 for (typename vector<Node<Type> *>::const_iterator it = current->childs.begin(); it != current->childs.end(); it++) { PostorderPrint(*it); } cout << current->data << " "; } void deleteNode(Node<Type> *rootnode, Type Dnode) { if (rootnode == nullptr) { cout << "Error: Tree is empty." << endl; return; } Node<Type> *current = rootnode; if (rootnode->data == Dnode) { // 如果目標節點是根節點，刪除整棵樹 deleteSubtree(rootnode); RootNode = nullptr; cout << "Tree deleted." << endl; return; } for (typename vector<Node<Type> *>::const_iterator it = current->childs.begin(); it != current->childs.end(); it++) { if ((*it)->data == Dnode) { deleteSubtree(*it); cout << "SubTree deleted." << endl; return; } deleteNode((*it), Dnode); } } void deleteSubtree(Node<Type> *rootnode) { // 遞迴刪除子樹 for (typename vector<Node<Type> *>::iterator it = rootnode->childs.begin(); it != rootnode->childs.end(); ++it) { deleteSubtree(*it); delete *it; } rootnode->childs.clear(); // 清空子節點向量 } // 查詢節點的子節點 void getChildren(Node<Type> *Tnode) const { for (typename vector<Node<Type> *>::const_iterator it = Tnode->childs.begin(); it != Tnode->childs.end(); it++) { cout << (*it)->data << " "; } return; } Node<Type> *addChildInTree(Node<Type> *rootnode, Type TargeNode, Type NodeData) { if (RootNode == nullptr) { cout << "Error: Tree is empty." << endl; return nullptr; } if (rootnode->data == TargeNode) { return rootnode->addChild(NodeData); } Node<Type> *current = rootnode; for (typename vector<Node<Type> *>::const_iterator it = current->childs.begin(); it != current->childs.end(); it++) { Node<Type> *result = addChildInTree((*it), TargeNode, NodeData); if (result != nullptr) { return result; // 找到目標節點，立即返回結果 } } return nullptr; // 如果在子節點中找不到目標節點，返回 nullptr } Node<Type> *FindNode(Node<Type> *rootnode, Type TargetNode) { if (RootNode == nullptr) { cout << "Error: Tree is empty." << endl; return nullptr; } if (rootnode->data == TargetNode) { return rootnode; } Node<Type> *current = rootnode; for (typename vector<Node<Type> *>::const_iterator it = current->childs.begin(); it != current->childs.end(); it++) { Node<Type> *result = FindNode(*it, TargetNode); if (result != nullptr) { return result; // 找到目標節點，立即返回結果 } } return nullptr; // 如果在子節點中找不到目標節點，返回 nullptr } // 查詢節點的父節點 Node<Type> *getParent(Node<Type> *Tnode) const { return Tnode->parent; } Node<Type> *getRoot() const { return RootNode; } }; int main() { // 創建樹 Tree<int> TestTree; // 創建樹節點 Node<int> *root = new Node<int>(1); TestTree.addroot(root); // 新增子節點 root->addChild(2); root->addChild(3); root->addChild(4); TestTree.addChildInTree(TestTree.getRoot(), 2, 5); TestTree.addChildInTree(TestTree.getRoot(), 2, 6); TestTree.addChildInTree(TestTree.getRoot(), 2, 7); TestTree.addChildInTree(TestTree.getRoot(), 3, 8); TestTree.addChildInTree(TestTree.getRoot(), 3, 9); TestTree.addChildInTree(TestTree.getRoot(), 4, 10); // 先序遍歷印出樹 cout << "Preorder Traversal: "; TestTree.PreorderPrint(root); cout << endl; // 後序遍歷印出樹 cout << "Postorder Traversal: "; TestTree.PostorderPrint(root); cout << endl; // 查詢節點的子節點 cout << "Children of Root: "; TestTree.getChildren(root); cout << endl; // 查詢節點的父節點 cout << "Parent of Child1: "; Node<int> *parent = TestTree.getParent(TestTree.FindNode(TestTree.getRoot(), 2)); if (parent) { cout << parent->getdata(); } else { cout << "No parent (root node)."; } cout << endl; // 刪除整棵樹 TestTree.deleteSubtree(TestTree.getRoot()); return 0; } |
