二叉树的前序、中序和后序线索化-创新互联
二叉树是一种非线性结构,遍历二叉树需要通过递归或者用栈辅助实现非递归的遍历。
创新互联公司坚持“要么做到,要么别承诺”的工作理念,服务领域包括:成都网站制作、网站设计、企业官网、英文网站、手机端网站、网站推广等服务,满足客户于互联网时代的盱眙网站设计、移动媒体设计的需求,帮助企业找到有效的互联网解决方案。努力成为您成熟可靠的网络建设合作伙伴!用二叉树作为压缩存储结构时,取到一个结点,只能获取节点的左孩子和右孩子,不能直接得到结点的任一遍历序列的前驱或者后继。为了实现这种遍历,偶们利用二叉树中指向左右子树的空指针来存放结点的前驱和后继。
线索化二叉树思路:
当某一结点的左结点或结右点存在NULL时,则该结点的为空的子结点需要线索化。
在进行线索化时,结点的前驱指向前一个访问过的结点,故定义一个指针prev来保存前一个结点;结点的后继偶们并不知道,则对于未来的事情并不知道,偶们可以在未来对该结点的后继进行线索化,使prev的后继指向cur。
前序遍历二叉树------根->左->右(1,2,3,4,5,6)
templatevoid BinaryTreeThd ::PrevOrderThreading()//前序线索化二叉树 { Node* prev = NULL; _PrevOrderThreading(_root, prev); } template void BinaryTreeThd ::_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; if (cur->_leftTag == LINK)//线索化左结点 { _PrevOrderThreading(cur->_left, prev); } if (cur->_rightTag == LINK)//线索化右结点 { _PrevOrderThreading(cur->_right, prev); } }
中序遍历二叉树------左->根->右(3,2,4,1,6,5)
递归实现:
templatevoid BinaryTreeThd ::InOrderThreading()//中序线索化二叉树 { //递归实现中序线索化 Node* prev = NULL;//线索化的前一个结点 _InOrederThreading(_root, prev); } template void BinaryTreeThd ::_InOrederThreading(Node* cur,Node*& prev)//中序线索化二叉树 { if (cur == NULL) { return; } _InOrederThreading(cur->_left, prev);//递归出cur->_left为空 if (cur->_left == NULL) { cur->_leftTag = THREAD; cur->_left = prev;//当前结点的前驱指向前一个结点 } //对先前的结点后继进行线索化,在cur指向下一个结点即后继时,将先前节点的后继指向cur //到未来的结点进行先前结点后继的线索化 if (prev && prev->_right == NULL) { cur->_rightTag = THREAD; prev->_right = cur; } prev = cur; _InOrederThreading(cur->_right, prev);//递归出cur->_right为空 }
非递归实现(利用栈):
templatevoid BinaryTreeThd ::InOrderThreading_NonR()//中序线索化二叉树--非递归 { //栈实现中序线索化 stack s; Node* prev = NULL; Node* cur = _root; if (cur == NULL) { return; } while (cur || !s.empty()) { while(cur)//找到最左结点,入栈 { s.push(cur); cur = cur->_left; }//cur不为空进栈,cur为空说明cur已经线索化了 cur = s.top();//循环进入使cur为栈顶元素并判断是否需要线索化 if (cur->_left == NULL) { cur->_leftTag = THREAD; cur->_left = prev; } s.pop();//弹出栈顶元素,使栈顶保存需要线索化的cur的后继 prev = cur; if (cur->_right == NULL && !s.empty()) { cur->_rightTag = THREAD; cur->_right = s.top(); cur = NULL;//设置cur为空,防止死循环(2) } else { cur = cur->_right;//线索化跳到右子树进行 } } }
后序遍历二叉树------左->右->根(3,4,2,6,5,1)
templatevoid BinaryTreeThd ::PastOrderThreading()//后序线索化二叉树 { Node* prev = NULL; _PastOrderThreading(_root, prev); } template void BinaryTreeThd ::_PastOrderThreading(Node* cur, Node*& prev)//后序线索化二叉树 { if (cur == NULL) { return; } _PastOrderThreading(cur->_left, prev);//最左结点 _PastOrderThreading(cur->_right, prev);//最右结点 if (cur->_left == NULL)//线索化前驱 { cur->_leftTag = THREAD; cur->_left = prev; } if (prev && prev->_right == NULL)//线索化后继 { prev->_rightTag = THREAD; prev->_right = cur; } prev = cur; }
创新互联www.cdcxhl.cn,专业提供香港、美国云服务器,动态BGP最优骨干路由自动选择,持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证, 机房独有T级流量清洗系统配攻击溯源,准确进行流量调度,确保服务器高可用性。佳节活动现已开启,新人活动云服务器买多久送多久。
网站标题:二叉树的前序、中序和后序线索化-创新互联
链接地址:http://pwwzsj.com/article/cspiee.html