樹的孩子兄弟表示法

1、.#include<iostream>#define MAX 30/ 樹節(jié)點的最大數(shù)using namespace std;template<class T>class nodepublic:node()child = nextsibling = NULL;T ele; / 節(jié)點值node*child, *nextsibling;/左兒子右兄弟;template<class T>class Mytreepublic:Mytree()tree = NULL;Mytree()delete tree;void CreatTree(node<T>*);/

2、 構(gòu)造孩子兄弟表示法的樹T GetParent(node<T>*,T t);/返回樹的父親節(jié)點T GetLeftChild(node<T>*,T);/ 返回樹的最左兒子T GetRightsibling(node<T>*,T);/返回樹的最右兄弟T GetRoot(node<T>*);/返回樹的根節(jié)點node<T>* RetPoint(T, node<T>*);/ 返回值為t 的節(jié)點的指針node<T>* RetParentPoint(T, node<T>*);/返回值為t 的節(jié)點父親指針void

3、Display(node<T>*);/ 樹的左兒子右兄弟表示法的前序、中序、后序遍歷private:void preTraverseTree(node<T>*);/ 遞歸先序遍歷void InTraverseTree(node<T>*);/ 遞歸中序遍歷void PostTraverseTree(node<T>*);/ 遞歸后序遍歷node<T> *tree;.template<class T>void Mytree<T>:CreatTree(node<T>*tree)/ 構(gòu)造左兒子右兄弟表示的樹/

4、 以tree為根節(jié)點構(gòu)建if (*tree) != NULL)cout << " 輸入節(jié)點 " << (*tree)->ele << " 的左兒子右兄弟(沒有的話輸入#)： "node<T>*a = new node<T>node<T>*b = new node<T>cin >> a->ele >> b->ele;if (a->ele != '#') (*tree)->child = a; /有左兒子e

5、lse (*tree)->child = NULL;if (b->ele != '#') (*tree)->nextsibling = b; /有有兄弟else (*tree)->nextsibling = NULL;CreatTree(&(*tree)->child);/ 遞歸構(gòu)造樹CreatTree(&(*tree)->nextsibling);template<class T>T Mytree<T>:GetParent(node<T>*tree,T t)/返回節(jié)點值為 t 的父親nod

6、e<T>*p = RetParentPoint(t, tree);if (p)return p->ele;else return NULL;template<class T>T Mytree<T>:GetRoot(node<T>*tree)/返回樹的根節(jié)點值return tree->ele;template<class T>T Mytree<T>:GetLeftChild(node<T>*tree,T t)/返回樹的左兒子node<T>*p=RetPoint(t, tree);if (p

7、&&p->child) return p->child->ele;else return NULL;.template<class T>T Mytree<T>:GetRightsibling(node<T>*tree,T t)/得到樹 tree 的右兄弟node<T>*p=RetPoint(t, tree);if (p&&p->nextsibling) return p->nextsibling->ele;else return NULL;template<class T&

8、gt;void Mytree<T>:Display(node<T>*tree)/ 三種遞歸遍歷cout << " 先序遞歸遍歷："preTraverseTree(tree);cout << endl;cout << " 中序遞歸遍歷："InTraverseTree(tree);cout <<endl;cout << " 后序遞歸遍歷："PostTraverseTree(tree);cout << endl;template<class

9、 T>void Mytree<T>:preTraverseTree(node<T>*tree)/ 先序遞歸遍歷if (tree)cout << tree->ele << " "preTraverseTree(tree->child);preTraverseTree(tree->nextsibling);template <class T>void Mytree<T>:InTraverseTree(node<T>*tree)/中序遞歸遍歷if (tree)InTrave

10、rseTree(tree->child);cout << tree->ele << ""InTraverseTree(tree->nextsibling);.template<class T>void Mytree<T>:PostTraverseTree(node<T>*tree)/ 后序遞歸遍歷if(tree)PostTraverseTree(tree->nextsibling);PostTraverseTree(tree->child);cout << tree->

11、;ele << " "template<class T>node<T>* Mytree<T>:RetPoint(T t, node<T>* tree)/返回樹節(jié)點值為t 的指針if (tree)if (tree->ele = t) return tree;else if (RetPoint(t, tree->child)!=NULL)return RetPoint(t, tree->child);else if (RetPoint(t, tree->nextsibling) != NULL)

12、return RetPoint(t, tree->nextsibling);elsereturn NULL;else return NULL;template<class T>node<T>* Mytree<T>:RetParentPoint(T t, node<T>*tree)if (tree&&tree->child)if (tree->ele = t)return tree;else if (RetParentPoint(t, tree->child)return RetParentPoint(t,

13、tree->child);else if (RetParentPoint(t, tree->nextsibling)return RetParentPoint(t, tree->nextsibling);else return NULL;.int main()Mytree<char> mytree;node<char> *root = new node<char>cout << " 輸入根節(jié)點："cin >> root->ele;mytree.CreatTree(&root);cou

14、t<<" 樹的根： "<<mytree.GetRoot(root)<<endl;cout << " 輸入 t： "char t;cin >> t;cout << "t 的左兒子 " << mytree.GetLeftChild(root, t) << endl; cout << "t 的右兄弟 " << mytree.GetRightsibling(root, t) << endl; cout << "t 的父節(jié)點： " << mytree.GetParent(root,t) << endl;cout << " 樹的左兒子右兄弟表示法的三種遍歷： " << endl; mytree.Display(root);return 0;/*輸入根節(jié)點： a輸入節(jié)點a 的左兒子右兄弟(沒有的話輸