樹(shù)
樹(shù)用遞歸體現(xiàn)：
樹(shù)由 n 個(gè)節(jié)點(diǎn)組成有限合集。
當(dāng) n = 0 的時(shí)候是空樹(shù)
當(dāng) n > 0 的時(shí)候除根節(jié)點(diǎn)其他的節(jié)點(diǎn)可以劃分為 m 個(gè)互不相交的有限集合，每個(gè)集合稱為子樹(shù)
度：一個(gè)節(jié)點(diǎn)擁有子樹(shù)的數(shù)目稱為節(jié)點(diǎn)的度，度為零的節(jié)點(diǎn)叫葉節(jié)點(diǎn)，度不為零叫分支節(jié)點(diǎn)。樹(shù)的度為所有度節(jié)點(diǎn)中度的最大值。
樹(shù)的前驅(qū)和后繼：節(jié)點(diǎn)的后繼叫孩子，具有相同父親的節(jié)點(diǎn)叫兄弟，節(jié)點(diǎn)的前驅(qū)叫父親。
樹(shù)的高度：是樹(shù)中節(jié)點(diǎn)最大層次
有序樹(shù)：樹(shù)中節(jié)點(diǎn)從左到右是有序的，且子樹(shù)不能互換位置
深林：由n棵互不相交的樹(shù)組成的集合
節(jié)點(diǎn): 樹(shù)中的節(jié)點(diǎn)包含了一個(gè)數(shù)據(jù)和指向其他節(jié)點(diǎn)的指針
線性非線性:從根節(jié)點(diǎn)到葉節(jié)點(diǎn)是非線性的,從葉節(jié)點(diǎn)到根節(jié)點(diǎn)是線性的(等同鏈表)
樹(shù)的表示方法:
雙親孩子表示法:
a. 每個(gè)節(jié)點(diǎn)都有指向父親的指針
b. 每個(gè)節(jié)點(diǎn)都有指向若干個(gè)孩子的指針
#ifndef GTREENODE_H #define GTREENODE_H #include"Tree.h" #include"LinkList.h" namespace DSL { template <typename T> class GTreeNode : public TreeNode<T> { public: LinkList<GTreeNode<T>*> m_GTreeNode; static GTreeNode<T>* NewNode() // 工廠模式 { GTreeNode<T>* ret = new GTreeNode<T>(); if(ret != NULL) { ret->m_flag = ture; // 標(biāo)識(shí)堆空間申請(qǐng)的對(duì)象 } } }; } #endif
#ifndef GTREE_H #define GTREE_H #include"Tree.h" #include"GTreeNode.h" #include"Exception.h" #include"LinkListQueue.h" namespace DSL { template <typename T> class GTree : public Tree<T> { LinkListQueue<GTreeNode<T>*> m_queue; // 實(shí)現(xiàn)節(jié)點(diǎn)順序存儲(chǔ) protected: GTreeNode<T>* find(GTreeNode<T>* root, const T& value) const { GTreeNode<T>* ret = NULL; if(root != NULL) { if(value == root->value) { return root; } else { for(root->m_GTreeNode.move(0); !root->m_GTreeNode.end() && (ret == NULL); root->m_GTreeNode.next()) { find(root->m_GTreeNode.current(),value); } } } return ret; } GTreeNode<T>* find(GTreeNode<T>* root, GTreeNode<T>* node) const { GTreeNode<T>* ret = NULL; if(root == node) { return root; } else { if(root != NULL) { for(root->m_GTreeNode.move(0); !root->m_GTreeNode.end() && (ret == NULL); root->m_GTreeNode.next()) { find(root->m_GTreeNode.current(), node); } } } return ret; } void free(GTreeNode<T>* root) { if(root == NULL) { return; } else { for(root->m_GTreeNode.move(0); !root->m_GTreeNode.end(); root->m_GTreeNode.next()) { free(root->m_GTreeNode.current()); } if(root->flag()) { delete root; } } } int count(GTreeNode<T>* node) const { int ret = 0; if(node == NULL) { return ret; } else { ret = 1; // 加上根節(jié)點(diǎn)的 for(node->m_GTreeNode.move(0); !node->m_GTreeNode.end(); node->m_GTreeNode.next()) { ret = ret + count(node->m_GTreeNode.current()); // return count(node->m_GTreeNode.current()) + 1; // 1 當(dāng)前根節(jié)點(diǎn) // ret = 1 + count(node->m_GTreeNode.current()); } } return ret; } int height(GTreeNode<T>* node) const { int ret = 0; if(node == NULL) { return ret; } else { for(node->m_GTreeNode.move(0); !node->m_GTreeNode.end(); node->m_GTreeNode.next()) { int h = height(node->m_GTreeNode.current()); if(h < ret) { h = ret; } } ret = ret + 1; // 子樹(shù)全部遍歷一次，則已知高度加1 } } int degree(GTreeNode<T>* node) const { int ret = 0; if(node == NULL) { return ret; } else { ret = node->m_GTreeNode.length(); for(node->m_GTreeNode.move(0); !node->m_GTreeNode.end(); node->m_GTreeNode.next()) { int temp = degree(node->m_GTreeNode.current()); if(temp > ret) { ret = temp; } } } return ret; } public: GTree() {} bool insert(TreeNode<T>* node) { bool ret = ture; if(node != NULL) { if(this->m_root == NULL) { node->parent = NULL; this->m_root = node; } else { GTreeNode<T>* parent_node = find(node->parent); if(parent_node != NULL) { // parent_node->m_GTreeNode.insert() 下面可避免重復(fù)插入樹(shù)中有的節(jié)點(diǎn) GTreeNode<T>* temp_node = dynamic_cast<GTreeNode<T>*>(node); if(parent_node->m_GTreeNode.find(temp_node) < 0) { parent_node->m_GTreeNode.insert(temp_node); } } else { ret = false; } } } else { THROW_EXCEPTION(InvalidParameterException, "insert node is NULL!"); } return ret; } bool insert(const T& value, TreeNode<T>* parent) { bool ret = ture; GTreeNode<T>* temp_node = GTreeNode<T>::NewNode(); if(temp_node != NULL) { temp_node->value = value; temp_node->parent = parent; insert(temp_node); } else { THROW_EXCEPTION(InvalidOperationException, "no enough memory to create a node!"); } return ret; } SharedPointer<Tree<T>> remove(TreeNode<T>* node) { GTree<T>* del_tree; if(del_tree == NULL) { THROW_EXCEPTION(NotEnoughMemoryException, "no enough memory to create new tree!"); } else { GTreeNode<T>* del_node = dynamic_cast<GTreeNode<T>*>(find(node)); if(del_node != NULL) { if(root() == del_node) { this->m_root = NULL; } else { LinkList<GTreeNode<T>*>& par_node_list = dynamic_cast<GTreeNode<T>*>(del_node->parent)->m_GTreeNode; par_node_list.remove(par_node_list.find(del_node)); del_node->parent = NULL; m_queue.clear(); } } else { THROW_EXCEPTION(InvalidParameterException, "can not find a node by value!"); } del_tree->m_root = del_node; return del_tree; } } SharedPointer<Tree<T>> remove(const T& value) { GTree<T>* del_tree; if(del_tree == NULL) { THROW_EXCEPTION(NotEnoughMemoryException, "no enough memory to create new tree!"); } else { GTreeNode<T>* del_node = find(value); if(del_node != NULL) { if(root() == del_node) { this->m_root = NULL; } else { LinkList<GTreeNode<T>*>& par_node_list = dynamic_cast<GTreeNode<T>*>(del_node->parent)->m_GTreeNode; par_node_list.remove(par_node_list.find(del_node)); del_node->parent = NULL; m_queue.clear(); } } else { THROW_EXCEPTION(InvalidParameterException, "can not find a node by value!"); } del_tree->m_root = del_node; return del_tree; } } GTreeNode<T>* find(TreeNode<T>* node) const { return find(root(), dynamic_cast<GTreeNode<T>*>(node)); } GTreeNode<T>* find(const T& value) const { return find(root(), value); } GTreeNode<T>* root() const { return dynamic_cast<GTreeNode<T>*>(this->m_root); } int degree() const { return degree(root()); } int count() const { return count(root()); } int height() const { return height(root()); } /* * 實(shí)現(xiàn)樹(shù)按照橫向?qū)哟蝸?lái)遍歷：通過(guò)隊(duì)列頭返回一個(gè)節(jié)點(diǎn)時(shí)，將其子節(jié)點(diǎn)全部插入隊(duì)列尾部實(shí)現(xiàn)樹(shù)的順序存儲(chǔ)和讀取。 * begin() * next() * current() * end() */ bool begin() // 根節(jié)點(diǎn)壓入隊(duì)列 { if(root() == NULL) { return false; } else { m_queue.clear(); m_queue.add(root()); return ture; } } bool next() // 彈出隊(duì)頭元素，將隊(duì)頭節(jié)點(diǎn)孩子壓入隊(duì)列 { if(m_queue.length() <= 0) { return false; } else { GTreeNode<T>* node = m_queue.front(); m_queue.remove(); for(node->m_GTreeNode.move(0); !node->m_GTreeNode.end(); node->m_GTreeNode.next()) { m_queue.add(node->m_GTreeNode.current()); } return ture; } } T current() // 訪問(wèn)隊(duì)頭元素指向節(jié)點(diǎn)的數(shù)據(jù) { if(!end()) { return m_queue.front()->value; } else { THROW_EXCEPTION(InvalidOperationException, "index out of bound!"); } } bool end() { return (m_queue.length() != 0); } void clear() { free(root()); this->m_root = NULL; m_queue.clear(); } ~GTree() { clear(); } }; } #endif
孩子兄弟表示法:
a. 每個(gè)節(jié)點(diǎn)都有指向第一個(gè)孩子的指針
b. 每個(gè)節(jié)點(diǎn)都有指向第一個(gè)右兄弟的指針
優(yōu)點(diǎn):每個(gè)節(jié)點(diǎn)只有兩個(gè)指針和一個(gè)數(shù)據(jù),節(jié)點(diǎn)總類只有五種,但是可以描述任意類型的樹(shù)形結(jié)構(gòu),形象稱為二叉樹(shù)
二叉樹(shù):由一個(gè)根節(jié)點(diǎn)和兩棵樹(shù)組成,稱為左子樹(shù)和右子樹(shù).
滿二叉樹(shù): 二叉樹(shù)中所有分支節(jié)點(diǎn)度數(shù)都為2,且葉子節(jié)點(diǎn)都在同一層次上.
完全二叉樹(shù):一個(gè)二叉樹(shù)的已有的節(jié)點(diǎn)在位置上和高度相同的滿二叉樹(shù)在位置編號(hào)(層次遍歷編號(hào))上一一對(duì)應(yīng).(一顆具有n個(gè)節(jié)點(diǎn)高度為k的二叉樹(shù),每一個(gè)節(jié)點(diǎn)和高度為k的滿二叉樹(shù)中的編號(hào)為1 -- n節(jié)點(diǎn)一一對(duì)應(yīng))
特點(diǎn): 同樣節(jié)點(diǎn)數(shù)的二叉樹(shù)中完全二叉樹(shù)高度最小.完全二叉樹(shù)葉節(jié)點(diǎn)只出現(xiàn)在最下面兩層. 最底層葉節(jié)點(diǎn)一定在左邊.倒數(shù)第二層葉節(jié)點(diǎn)一定在右邊.完全二叉樹(shù)度為一的節(jié)點(diǎn)只有左孩子
二叉樹(shù)特點(diǎn):
1. 在二叉樹(shù)的第 i 層最多有 2^(i-1) 個(gè)節(jié)點(diǎn)
2. 高度為k的二叉樹(shù)一共最多有2^k - 1個(gè)節(jié)點(diǎn)
3. 任意一顆二叉樹(shù),葉節(jié)點(diǎn)有n0個(gè),度為2的非葉節(jié)點(diǎn)有n2個(gè), n0 = n2 + 1
4. 具有n個(gè)節(jié)點(diǎn)的完全二叉樹(shù)的高度為[log2n]+1. ([X]表示不大于X的最大整數(shù))
5. 一棵n個(gè)節(jié)點(diǎn)的完全二叉樹(shù),按照層次編號(hào)(先從上到下再?gòu)淖蟮接?,對(duì)于任意節(jié)點(diǎn)i有以下父子關(guān)系:
a. i = 0, 節(jié)點(diǎn)i表示二叉樹(shù)的根. i > 1, 雙親節(jié)點(diǎn)為[i/2]
b. 2i < n,節(jié)點(diǎn)i的左孩子為2i. 2i > n 節(jié)點(diǎn)i無(wú)左孩子
c. 2i + 1 <= n 節(jié)點(diǎn)i的右孩子為2i + 1. 2i + 1 > n節(jié)點(diǎn)i無(wú)右孩子
遍歷:
層次遍歷:從上到下從左到右
先序遍歷:根節(jié)點(diǎn)在開(kāi)始位置被訪問(wèn)
中序遍歷:根節(jié)點(diǎn)在中間位置被訪問(wèn)
后序遍歷:根節(jié)點(diǎn)在最后位置被訪問(wèn)
#ifndef BTREENODE_H #define BTREENODE_H #include"TreeNode.h" namespace DSL { template <typename T> class BTreeNode : public TreeNode<T> { public: BTreeNode<T>* left_child; BTreeNode<T>* right_child; BTreeNode() { left_child = NULL; right_child = NULL; } static BTreeNode<T>* NewNode() { BTreeNode<T>* ret = new BTreeNode<T>(); if(ret != NULL) { ret->m_flag = ture; } } }; enum ChildDirect { ANY_DIR, LEFT_DIR, RIGHT_DIR }; } #endif
#ifndef BTREE_H #define BTREE_H #include"Tree.h" #include"BTreeNode.h" #include"Exception.h" #include"LinkListQueue.h" #include"SharedPointer.h" #include"DynamicArray.h" namespace DSL { enum TraversalType { PREORDER, INORDER, POSORDER, LEVELORDER }; template <typename T> class BTree : public Tree<T> { protected: LinkListQueue<BTreeNode<T>*> m_queue; virtual BTreeNode<T>* find(BTreeNode<T>* root, const T& value) const { BTreeNode<T>* ret = NULL; if(root != NULL) { if(root->value == value) { ret = root; } else { if(ret == NULL) { find(root->left_child, value); } if(ret == NULL) { find(root->right_child, value); } } } return ret; } virtual BTreeNode<T>* find(BTreeNode<T>* root, BTreeNode<T>* node) const { BTreeNode<T>* ret = NULL; if(root == node) { ret = node; } else { if(root != NULL) { if(ret == NULL) { find(root->left_child, node); } if(ret == NULL) { find(root->right_child, node); } } } return ret; } virtual bool insert(BTreeNode<T>* node_parent, BTreeNode<T>* node, ChildDirect direct) { bool ret = ture; if(direct == ANY_DIR) { if(node_parent->left_child == NULL) { node_parent->left_child = node; } else if(node_parent->right_child == NULL) { node_parent->right_child = node; } else { ret = false; } } else if(direct == LEFT_DIR) { if(node_parent->left_child == NULL) { node_parent->left_child = node; } else { ret = false; } } else if(direct == RIGHT_DIR) { if(node_parent->right_child == NULL) { node_parent->right_child = node; } else { ret = false; } } else { ret = false; } return ret; } virtual void remove(BTreeNode<T>* node, BTree<T>*& ret) { ret = new BTree<T>(); if(ret == NULL) { THROW_EXCEPTION(NotEnoughMemoryException, "no enough memory to allocate a tree!"); } else { BTreeNode<T>* node_parent = dynamic_cast<BTreeNode<T>*>(node->parent); if(node_parent->left_child == node) { node_parent->left_child = NULL; } else if(node_parent->right_child == node) { node_parent->right_child = NULL; } node->parent = NULL; } ret->m_root = node; } virtual void free(BTreeNode<T>* del_node) { if(del_node ==NULL) { return; } else { free(del_node->left_child); free(del_node->right_child); if(del_node->flag()) { delete del_node; } } } int count(BTreeNode<T>* root) const { int ret = 0; if(root == NULL) { return ret; } else { return (count(root->left_child) + count(root->right_child) + 1); // 1為當(dāng)前根節(jié)點(diǎn) } // return ((root != NULL) ? (count(root->left_child) + count(root->right_child) + 1) : 0); } int height(BTreeNode<T>* root) const { int ret = 0; if(root == NULL) { return ret; } else { int left_height = count(root->left_child); int right_height = count(root->right_child); if(left_height > right_height) { ret = left_height + 1; // 1為當(dāng)前根節(jié)點(diǎn)個(gè)數(shù) } return ret; // return (((left_height > right_height) ? left_height : right_height) + 1); } } int degree(BTreeNode<T>* root) const { int ret = 0; if(root == NULL) { return ret; } else { int degree_root = (!!root->left_child) + (!!root->right_child); if(ret < 2) { int degree_left = degree(root->left_child); if(degree_left > degree_root) ret = degree_left; } if(ret < 2) { int degree_right = degree(root->right_child); if(degree_right > degree_root) ret = degree_right; } return ret; } /* int ret = 0; if(root == NULL) { return ret; } else { int degree_left = degree(root->left_child); int degree_right = degree(root->right_child); int degree_root = (!!root->left_child) + (!!root->right_child); if(degree_left > degree_root) { ret = degree_left; } if(degree_right > degree_root) { ret = degree_right; } if(degree_left > degree_right) { ret = degree_left; } return ret; } */ } // 先序遍歷:根節(jié)點(diǎn)在開(kāi)始位置被訪問(wèn) void PreOrderTraversal(BTreeNode<T>* root, LinkListQueue<BTreeNode<T>*>& queue) { if(root == NULL) { return; } else { queue.add(root); PreOrderTraversal(root->left_child, queue); PreOrderTraversal(root->right_child, queue); } } //中序遍歷:根節(jié)點(diǎn)在中間位置被訪問(wèn) void InOrderTraversal(BTreeNode<T>* root, LinkListQueue<BTreeNode<T>*>& queue) { if(root == NULL) { return; } else { InOrderTraversal(root->left_child, queue); queue.add(root); InOrderTraversal(root->right_child, queue); } } //后序遍歷:根節(jié)點(diǎn)在最后位置被訪問(wèn) void PostOrderTraversal(BTreeNode<T>* root, LinkListQueue<BTreeNode<T>*>& queue) { if(root == NULL) { return; } else { PostOrderTraversal(root->left_child, queue); PostOrderTraversal(root->right_child, queue); queue.add(root); } } //層次遍歷：從上到下從左到右。第一個(gè)隊(duì)列完成層次次序的訪問(wèn)，第二個(gè)隊(duì)列保存訪問(wèn)次序 void LevelOrderTraversal(BTreeNode<T>* root, LinkListQueue<BTreeNode<T>*>& ret_queue) { if(root == NULL) { THROW_EXCEPTION(InvalidParameterException, "can not convert a empty tree!"); } else { LinkListQueue<BTreeNode<T>*> temp_queue; BTreeNode<T>* temp_node; temp_queue.add(root); while(temp_queue.length() > 0) { temp_node = temp_queue.front(); if(temp_node->left_child) { temp_queue.add(temp_node->left_child); } if(temp_node->right_child) { temp_queue.add(temp_node->right_child); } temp_queue.remove(); ret_queue.add(temp_node); } } } BTreeNode<T>* clone(const BTreeNode<T>* node) const { BTreeNode<T>* temp_node = NULL; if(node == NULL) { return NULL; } else { if(temp_node == NULL) { THROW_EXCEPTION(NotEnoughMemoryException, "can not create new node!"); } else { temp_node->value = node->value; temp_node->left_child = clone(node->left_child); temp_node->right_child = clone(node->right_child); // 初始化每個(gè)節(jié)點(diǎn)parent指針 if(temp_node->left_child) { temp_node->left_child->parent = temp_node; } if(temp_node->right_child) { temp_node->right_child->parent = temp_node; } } } } bool equal(BTreeNode<T>* left_tree, BTreeNode<T>* right_tree) const { if(left_tree == right_tree) { return ture; } else if((left_tree != NULL) && (right_tree != NULL)) { return ((left_tree->value == right_tree->value) && (equal(left_tree->left_child, right_tree->left_child)) && (equal(left_tree->right_child, right_tree->right_child))); } else // 一棵二叉樹(shù)為空，一顆二叉樹(shù)不為空 { return false; } } BTreeNode<T>* add(BTreeNode<T>* tree1_root, BTreeNode<T>* tree2_ndoe) const { BTreeNode<T>* temp_node = NULL; if((tree1_root == NULL) && (tree2_ndoe != NULL)) { return clone(tree2_ndoe); } else if((tree1_root != NULL) && (tree2_ndoe == NULL)) { return clone(tree1_root); } else if((tree1_root != NULL) && (tree2_ndoe != NULL)) { temp_node = BTreeNode<T>::NewNode(); if(temp_node == NULL) { THROW_EXCEPTION(NotEnoughMemoryException, "no enought memory to create new node!"); } else { temp_node->value = tree1_root->value + tree2_ndoe->value; temp_node->left_child = add(tree1_root->left_child,tree2_ndoe->left_child); temp_node->right_child = add(tree1_root->right_child, tree2_ndoe->right_child); // 初始化每個(gè)節(jié)點(diǎn)parent指針 if(temp_node->left_child) { temp_node->left_child->parent = temp_node; } if(temp_node->right_child) { temp_node->right_child->parent = temp_node; } } } else // 兩棵樹(shù)都為空 { return NULL; } } // 線索化STEP1：將輸入的樹(shù)root轉(zhuǎn)化根據(jù)遍歷類型type遍歷并將其按照遍歷順序存放在ret_queue隊(duì)列中 void traversal(BTreeNode<T>* root, LinkListQueue<BTreeNode<T>*>& ret_queue, TraversalType type) { switch (type) { case PREORDER: PreOrderTraversal(root, ret_queue); break; case INORDER: InOrderTraversal(root, ret_queue); break; case POSORDER: PostOrderTraversal(root, ret_queue); break; case LEVELORDER: LevelOrderTraversal(root, ret_queue); break; default: THROW_EXCEPTION(InvalidParameterException, "unknown traversal type!"); break; } } //線索化STEP2：將輸入節(jié)點(diǎn)為樹(shù)節(jié)點(diǎn)的queue轉(zhuǎn)化為雙向鏈表，并返回雙向鏈表頭節(jié)點(diǎn) // 連接隊(duì)列中的節(jié)點(diǎn)(right指向后繼，left指向前驅(qū))形成雙向鏈表 BTreeNode<T>* connect(LinkListQueue<BTreeNode<T>*>& queue) { BTreeNode<T>* list_head = NULL, slider = NULL; if(queue == NULL && queue.length() > 0) { return NULL; } else { list_head = queue.front(); slider = queue.front(); queue.remove(); slider->left_child = NULL; while(queue.length() > 0) { slider->right_child = queue.front(); queue.front()->right_child = slider; slider = queue.front(); queue.remove(); } slider->right_child = NULL; } return list_head; } public: bool insert(TreeNode<T>* node) { return insert(node, ANY_DIR); } bool insert(TreeNode<T>* node, ChildDirect direct) { bool ret = ture; if(node != NULL) { if(this->m_root == NULL) { node->parent = NULL; this->m_root = node; } else { BTreeNode<T>* node_parent = find(node->parent); if(node_parent != NULL) { if(!insert(dynamic_cast<BTreeNode<T>*>(node), node_parent, direct)) { ret = false; } } else { ret = false; } } } else { THROW_EXCEPTION(InvalidParameterException, "insert node is NULL!"); } return ret; } bool insert(const T& value, TreeNode<T>* parent) { return insert(value, parent, ANY_DIR); } bool insert(const T& value, TreeNode<T>* parent, ChildDirect direct) { bool ret = ture; BTreeNode<T>* temp_node = BTreeNode<T>::NewNode(); if(temp_node != NULL) { temp_node->value = value; temp_node->parent = parent; if(!insert(temp_node, direct)) { delete temp_node; ret = false; } } else { THROW_EXCEPTION(InvalidParameterException, "can not allcote new node!"); } return ret; } SharedPointer<Tree<T>> remove(TreeNode<T>* node) { BTree<T>* ret_tree = NULL; node = find(node); if(node == NULL) { THROW_EXCEPTION(InvalidParameterException, "remove node is not in tree!"); } else { remove(dynamic_cast<BTreeNode<T>*>(node), ret_tree); m_queue.clear(); //清空隊(duì)列； } return ret_tree; } SharedPointer<Tree<T>> remove(const T& value) { BTree<T>* ret_tree = NULL; BTreeNode<T>* node = find(value); if(node == NULL) { THROW_EXCEPTION(InvalidParameterException, "remove node is not in tree!"); } else { remove(node, ret_tree); m_queue.clear(); //清空隊(duì)列； } return ret_tree; } BTreeNode<T>* find(TreeNode<T>* node) const { return find(root(), dynamic_cast<BTreeNode<T>*>(node)); } BTreeNode<T>* find(const T& value) const { return find(root(), value); } BTreeNode<T>* root() const { return dynamic_cast<BTreeNode<T>*>(this->m_root); } int degree() const { return degree(root()); } int count() const { return count(root()); } int height() const { return height(root()); } // 二叉樹(shù)的層次遍歷 bool begin() { if(root() == NULL) { return false; } else { m_queue.clear(); m_queue.add(root()); return ture; } } bool next() { if(m_queue.length() <= 0) { return false; } else { BTreeNode<T>* head_node = m_queue.front(); m_queue.remove(); if(head_node->left_child) { m_queue.add(head_node->left_child); } if(head_node->right_child) { m_queue.add(head_node->right_child); } return ture; } } bool end() { return (m_queue.length() == 0); } T current() { if(end()) { THROW_EXCEPTION(InvalidOperationException, "index out of bound!"); } else { return m_queue.front()->value; } } // 二叉樹(shù)的先序，中序，后續(xù)遍歷 SharedPointer<DynamicArray<T>> traversal(BTreeNode<T>* root, TraversalType type) { LinkListQueue<BTreeNode<T>*> queue; DynamicArray<T>* array = NULL; if(root() == NULL) { THROW_EXCEPTION(InvalidOperationException, "empty tree can not be traversaled!"); } else { traversal(root, queue, type); array = new DynamicArray<T>(queue.length()); if(array == NULL) { THROW_EXCEPTION(NotEnoughMemoryException, "no enough to create a new array!"); } else { for(int i = 0; i < array.length(); i++, queue.remove()) { array.set(i, queue.front()->value); } } } } //拷貝根節(jié)點(diǎn)為tree_root的二叉樹(shù) SharedPointer<Tree<T>>* clone(BTreeNode<T>* tree_root) const { BTree<T>* temp_tree = new BTree<T>(); if(temp_tree == NULL) { THROW_EXCEPTION(NotEnoughMemoryException, "no enough memory to create tree!"); } else { temp_tree->m_root = clone(tree_root); } return temp_tree; } //對(duì)二叉樹(shù)每個(gè)元素進(jìn)行比較 bool operator == (const BTree<T>* tree) const { return equal(root(), tree.root()); } bool operator != (const BTree<T>* tree) const { return !(*this == tree); } //二叉樹(shù)相加操作，將當(dāng)前二叉樹(shù)與參數(shù)樹(shù)在對(duì)應(yīng)節(jié)點(diǎn)的數(shù)值相加 //返回值是堆空間申請(qǐng)的新二叉樹(shù) SharedPointer<BTree<T>> add(const BTree<T>& btree) const { BTree<T>* temp_tree = new BTree<T>(); if(temp_tree == NULL) { THROW_EXCEPTION(NotEnoughMemoryException, "no enough memory to create a new tree!"); } else { temp_tree->m_root = add(root(), btree.root()); } return temp_tree; } // 線索化二叉樹(shù)：將二叉樹(shù)轉(zhuǎn)化成雙向鏈表。 BTreeNode<T>* threaded(BTree<T>* tree, TraversalType type) { if(root == NULL) { return NULL; } else { BTreeNode<T>* list_head = NULL; LinkListQueue<BTreeNode<T>*> queue = NULL; traversal(tree.root(), queue, LEVELORDER); list_head = connect(queue); tree.m_root = NULL; tree.clear(); return list_head; } } // 刪除樹(shù)根節(jié)點(diǎn)為root中的單度節(jié)點(diǎn) BTreeNode<T>* delete_single_drgree_node(BTreeNode<T>* root) { BTreeNode<T>* head = NULL; if(root == NULL) { return NULL; } else { if(((root->left_child == NULL) && (root->right_child != NULL)) || ((root->left_child != NULL) && (root->right_child ==NULL)))// 單度情況 { BTreeNode<T>* parent = dynamic_cast<BTreeNode<T>*>(root->parent); BTreeNode<T>* child = ((root->left_child != NULL) ? root->left_child : root->right_child); if(parent != NULL) { ((parent->left_child != NULL) ? parent->left_child : parent->right_child) = child; // C++三目運(yùn)算表達(dá)式返回變量本身 child->parent = parent; } if(parent == NULL) // 處理根節(jié)點(diǎn)就是單度節(jié)點(diǎn)的情況 { child->parent = NULL; } if(root->flag()) { delete root; } head = delete_single_drgree_node(child); } else // 考慮度為0或2的情況 { delete_single_drgree_node(root->left_child); delete_single_drgree_node(root->right_child); head = root; } } return head; } // 刪除樹(shù)根節(jié)點(diǎn)為root中的單度節(jié)點(diǎn)，返回根節(jié)點(diǎn)為root的樹(shù)， 沒(méi)有父節(jié)點(diǎn) void delete_single_drgree_node(BTreeNode<T>*& root) { if(root == NULL) { THROW_EXCEPTION(InvalidParameterException, "can not do delete single degree node for empty tree!"); } else { if(((root->left_child != NULL) && (root->right_child ==NULL)) || ((root->left_child == NULL) && (root->right_child != NULL))) { BTreeNode<T>* child = ((root->left_child != NULL) ? root->left_child : root->right_child); if(root->flag()) delete root; root = child; delete_single_drgree_node(root); } else { delete_single_drgree_node(root->left_child); delete_single_drgree_node(root->right_child); } } } // 中序遍歷并直接線索化 // pre指針指向中序訪問(wèn)時(shí)前驅(qū)結(jié)點(diǎn)，root指向中序訪問(wèn)節(jié)點(diǎn) void inorderthreaded(BTreeNode<T>* root_node, BTreeNode<T>*& pre_node) { if(root_node ==NULL) { return ; } else { inorderthreaded(root_node->left_child, pre_node); // 這里返回后代表左子樹(shù)線索化完畢，pre_node指向鏈表的最后一個(gè)節(jié)點(diǎn) root_node->left_child = pre_node; if(pre_node != NULL) { pre_node->right_child = root_node; } pre_node = root_node; inorderthreaded(root_node->right_child, pre_node); return ; } } // 中序遍歷線并直接索化 // 中序遍歷節(jié)點(diǎn)的次序是節(jié)點(diǎn)的水平次序 head_node轉(zhuǎn)換完成后的頭節(jié)點(diǎn)，tail_node指向尾節(jié)點(diǎn) void inorderthreaded(BTreeNode<T>* root_node, BTreeNode<T>*& head_node, BTreeNode<T>*& tail_node) { if(root_node == NULL) { return; } else { BTreeNode<T>* head = NULL; BTreeNode<T>* tail = NULL; inorderthreaded(root_node->left_child, head, tail); root_node->left_child = tail; if(tail != NULL) tail->right_child = root_node; head_node = ((head != NULL) ? head : root_node); head = NULL; tail = NULL; inorderthreaded(root_node->right_child ,head, tail); root_node->right_child = head; if(head != NULL) head->left_child = root_node; tail_node = ((tail != NULL) ? tail : root_node); } } void clear() { free(root()); m_queue.clear(); //清空隊(duì)列； this->m_root = NULL; } ~BTree() { clear(); } }; } #endif
浙公網(wǎng)安備 33010602011771號(hào)