简述
任何一个节点都有两个强引用指向左右子节点，以及一个弱引用指向它的父节点。节点还包括一个
key成员保存数据内容。
实现
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 |
template<typename KType> struct BinaryTreeNode { public: typedef KType KeyType;//保存节点的数据类型 BinaryTreeNode():parent(std::weak_ptr<BinaryTreeNode>()), lchild(std::shared_ptr<BinaryTreeNode>()), rchild(std::shared_ptr<BinaryTreeNode>()), key(KeyType()) { } explicit BinaryTreeNode(const KeyType& keyvalue) :parent(std::weak_ptr<BinaryTreeNode>()), lchild(std::shared_ptr<BinaryTreeNode>()), rchild(std::shared_ptr<BinaryTreeNode>()), key(KeyType()) { } virtual std::string to_string() { std::ostringstream os; os << "node: "<<key; if (auto shared_p = parent.lock()) os<< "\n\t parent: "<<shared_p->key; else os<< "\n\t parent: "<<"nullptr"; os<< "\n\t left_child: "; if (lchild) os<< lchild->key; else os<< "nullptr"; os<< "\n\t right_child: "; if(rchild) os<< rchild->key; else os<< "nullptr"; return os.str(); } virtual std::string to_xml() { std::ostringstream os; os<< "\n<node>"<<key<<"\n"; if (auto shared_p = parent.lock()) os<<"\t <parent>"<<shared_p->key<<"</parent>"; else os<<"\t <parent>"<<"nullptr"<<"</parent>"; os<<"\n\t <left_child>"<<(lchild?lchild->to_xml():"nullptr")<<"</left_child>"\ <<"\n\t <right_child>"<<(rchild?rchild->to_xml():"nullptr")<<"</right_child>"\ <<"\n</node>"; return os.str(); } //判断本节点是否左节点 bool is_left_child() { if (auto shared_p = parent.lock()) { if (this == shared_p->lchild.get()) return true; } return false; } //判断本节点是否右节点 bool is_right_child() { if (auto shared_p == parent.lock()) { if (this == shared_p->rchild.get()) return true; } return false; } std::weak_ptr<BinaryTreeNode> parent;//父节点的弱引用 std::shared_ptr<BinaryTreeNode> lchild;//节点的左子节点的强引用 std::shared_ptr<BinaryTreeNode> rchild;//节点的右子节点的强引用 KeyType key; }; |
本文为原创文章，版权归Aet所有，欢迎分享本文，转载请保留出处！
你可能也喜欢
- ♥ 匹配_KMP模式匹配算法：二10/09
- ♥ 数据结构模板03/09
- ♥ 排序_桶排序05/09
- ♥ BFS和DFS06/29
- ♥ 查找_二分查找05/09
- ♥ 动态规划_最长公共子序列09/05