当前位置:首页 > 公司荣誉 >

数据结构:中序线索二叉树

编辑:北京盛典时光文化传媒有限公司时间:2017-09-10 09:59:56阅读次数:2
数据结构:中序线索二叉树 //所谓线索二叉树无非是为了让原本指向NULL的节点指向一个具体的 //已经存在的节点,逻辑上实现指针的无空指向的实现,下面是我中 //序线索二叉树的实现。还是把先序线索二叉树与后序线索分开来写吧。 #include using namespace std; template struct Node { Type data; bool rflags;//false为线。 bool lflags; Node *right; Node *left; Node(Type d = Type()) :data(d), right(NULL), left(NULL), lflags(false),rflags(false){} }; template class MyTree { public: MyTree() :root(NULL){} void Create_lvr_lrv(Type *LVR,Type *LRV) { int n = strlen(LRV); Create_lvr_lrv(root,LVR,LRV,n); } void Create_Thread_V()//中序构造线索二叉树。 { Node *pr = NULL; Create_Thread_V(root, pr); Node *p = root; while (p->right != NULL) { p = p->right; } p->right = NULL; p->rflags = true; } void Printf_V() { Node *p = root; while (p->left != NULL) { p = p->left; } Printf_V(p); } private: void Printf_V(Node *t)//中序线索二叉树的打印。 { Node *p = t; while (p != NULL) { cout << p->data << ; Node*m = p->right; if (p->rflags != true) { while (m != NULL && m->lflags != true) { m = m->left; } } p=m; } } void Create_Thread_V(Node *t, Node *&pr) { if (t == NULL) { return; } Create_Thread_V(t->left, pr); if (t->left== NULL) { t->left = pr; t->lflags = true; } if (pr!=NULL && pr->right ==NULL) { pr->right = t; pr->rflags = true; } pr = t; Create_Thread_V(t->right,pr); } void Create_lvr_lrv(Node *&t, Type *LVR, Type *LRV, int n) { if (n == 0)return; int i = 0; while (LRV[n - 1] != LVR[i])i++; t = new Node(LRV[n - 1]); Create_lvr_lrv(t->right,LVR+i+1,LRV+i,n-i-1); //根据中序及后序构造二叉树,此处我选择先构造右子树,然后才构造左子树。 Create_lvr_lrv(t->left,LVR,LRV,i); } private: Node *root; }; int main() { char LVR[] = CBDAFEG; char LRV[] = CDBFGEA; MyTree mt; mt.Create_lvr_lrv(LVR,LRV); mt.Create_Thread_V(); mt.Printf_V(); return 0; }

这里写图片描述

企业建站2800元起,携手武汉肥猫科技,做一个有见地的颜值派!更多优惠请戳:武汉SEO http://wuhan.4567w.com

上一篇:更新 drupal6的 imagecache presets 到 Drupal7 的ima 下一篇:最后一页

相关阅读