二叉树的前序、中序、后序线索化及遍历-创新互联
前序线索化:
成都创新互联主要从事网页设计、PC网站建设(电脑版网站建设)、wap网站建设(手机版网站建设)、成都响应式网站建设公司、程序开发、网站优化、微网站、小程序开发等,凭借多年来在互联网的打拼,我们在互联网网站建设行业积累了丰富的网站建设、成都做网站、网站设计、网络营销经验,集策划、开发、设计、营销、管理等多方位专业化运作于一体。void _PrevOrderThreading(Node *cur, Node *& prev) { if(cur == NULL) { return; } if(cur->_left == NULL) { cur->_leftTag == THREAD; cur->_left = prev; } if(prev && prev->_right == NULL) { prev->_rightTag = THREAD; prev->_right = cur; } prev = cur; _PrevOrderThreading(cur->_left, prev); _PrevOrderThreading(cur->right, prev); }
前序遍历:
void PrevOrderThd() { Node *cur = _root; while(cur) { while(cur->_leftTag == LINK) { cout << cur->_data << " "; cur = cur->_left; } cout << cur->_data << " "; cur = cur->right; // // while(cur->_rightTag == THREAD) // { // cur = cur->_right; // cout << cur->_data << " "; // } // if(cur->_leftTag == LINK) // { // cur = cur->_left; // } // else // { // cur = cur->_right; // } } }
中序线索化:
void _InOrderThreading(Node *cur, Node *& prev) { if(cur == NULL) { return; } _InOrderThreading(cur->_left, prev); //线索化 if(cur->_left == NULL) { cur->_leftTag = THREAD; cur->_left = prev; } if(prev && prev->_right == NULL) { prev->_rightTag = THREAD; prev->_right = cur; } prev = cur; _InOrderThreading(cur->_right, prev); }
中序遍历:
void InOrderThd() { Node *cur = _root; while(cur) { //找最左节点 while(cur->_leftTag == LINK) { cur = cur->_left; } cout << cur->_data << " "; //访问连续后继 while(cur->_rightTag == THREAD) { cur = cur->_right; cout << cur->_data << " "; } cur = cur->_right; } }
后序线索化:
void _PostOrderThreading(Node *root, Node *&prev) { if (root == NULL) { return; } _PostOrderThreading(root->_LChild, prev); _PostOrderThreading(root->_RChild, prev); if (root->_LChild == NULL) { root->_LTag = THREAD; root->_LChild = prev; } if (prev->_RChild == NULL) { prev->_RTag = THREAD; prev->_RChild = root; } prev = root; }
后序遍历:
采用三叉链 或写一个查找根节点的方法
创新互联www.cdcxhl.cn,专业提供香港、美国云服务器,动态BGP最优骨干路由自动选择,持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证, 机房独有T级流量清洗系统配攻击溯源,准确进行流量调度,确保服务器高可用性。佳节活动现已开启,新人活动云服务器买多久送多久。
分享题目:二叉树的前序、中序、后序线索化及遍历-创新互联
标题网址:http://myzitong.com/article/djpiid.html