树的孩子兄弟表示法.doc

#include#define MAX 30 /树节点的最大数using namespace std;templateclass nodepublic:node()child = nextsibling = NULL;T ele; /节点值node*child, *nextsibling;/左儿子右兄弟;templateclass Mytreepublic:Mytree()tree = NULL;Mytree()delete tree;void CreatTree(node*); /构造孩子兄弟表示法的树T GetParent(node*,T t); /返回树的父亲节点T GetLeftChild(node*,T); /返回树的最左儿子T GetRightsibling(node*,T); /返回树的最右兄弟T GetRoot(node*); /返回树的根节点node* RetPoint(T, node*); /返回值为t的节点的指针node* RetParentPoint(T, node*);/返回值为t的节点父亲指针void Display(node*); /树的左儿子右兄弟表示法的前序、中序、后序遍历private:void preTraverseTree(node*); /递归先序遍历void InTraverseTree(node*); /递归中序遍历void PostTraverseTree(node*); /递归后序遍历node *tree;templatevoid Mytree:CreatTree(node*tree) /构造左儿子右兄弟表示的树 /以tree为根节点构建if (*tree) != NULL)cout 输入节点 ele 的左儿子右兄弟(没有的话输入#)：;node*a = new node;node*b = new node;cin a-ele b-ele;if (a-ele != #) (*tree)-child = a; /有左儿子else (*tree)-child = NULL;if (b-ele != #) (*tree)-nextsibling = b; /有有兄弟else (*tree)-nextsibling = NULL;CreatTree(&(*tree)-child); /递归构造树CreatTree(&(*tree)-nextsibling);templateT Mytree:GetParent(node *tree,T t) /返回节点值为t的父亲node*p = RetParentPoint(t, tree);if (p)return p-ele;else return NULL;templateT Mytree:GetRoot(node*tree) /返回树的根节点值return tree-ele;templateT Mytree:GetLeftChild(node*tree,T t) /返回树的左儿子node*p=RetPoint(t, tree);if (p&p-child) return p-child-ele;else return NULL;templateT Mytree:GetRightsibling(node*tree,T t) /得到树tree的右兄弟node*p=RetPoint(t, tree);if (p&p-nextsibling) return p-nextsibling-ele;else return NULL;templatevoid Mytree:Display(node*tree) /三种递归遍历cout 先序递归遍历：;preTraverseTree(tree);cout endl;cout 中序递归遍历：;InTraverseTree(tree);cout endl;cout 后序递归遍历：;PostTraverseTree(tree);cout endl;templatevoid Mytree:preTraverseTree(node*tree) /先序递归遍历if (tree)cout ele child);preTraverseTree(tree-nextsibling);template void Mytree:InTraverseTree(node*tree) /中序递归遍历if (tree)InTraverseTree(tree-child);cout ele nextsibling);templatevoid Mytree:PostTraverseTree(node*tree) /后序递归遍历if(tree)PostTraverseTree(tree-nextsibling);PostTraverseTree(tree-child);cout ele ;templatenode* Mytree:RetPoint(T t, node* tree) /返回树节点值为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)return RetPoint(t, tree-nextsibling);else return NULL;else return NULL;templatenode* Mytree:RetParentPoint(T t, node*tree)if (tree&tree-child)if (tree-ele = t) return tree;else if (RetParentPoint(t, tree-child)return RetParentPoint(t, tree-child);else if (RetParentPoint(t, tree-nextsibling)return RetParentPoint(t, tree-nextsibling);else return NULL;int main()Mytree mytree;node *root = new node;cout root-ele;mytree.CreatTree(&root);cout树的根：mytree.GetRoot(root)endl;cout t;cout t的左儿子 mytree.GetLeftChild(root, t) endl;cout t的右兄弟 mytree.GetRightsibling(root, t) endl;cout t的父节点： mytree.GetParent(root,t) endl;cout 树的左儿子右兄弟表示法的三种遍历： endl;mytree.Display(root);return 0;/*输入根节点：a输入节点a的左儿子右兄弟(没有的话输入#)：b c输入节点b的左儿子右兄弟(没有的话输入#)：d e输入节点d的左儿子右兄弟(没有的话