#include "stdafx.h"#include#include #include #include #include using namespace std;enum TYPE{ TYPE_LINK = 0, TYPE_CLUES,};typedef struct _Node{ int data; struct _Node *left; struct _Node *right; bool isVisit; //用于后序非递归遍历，表示节点是否可以访问 TYPE lType; //标示左子树为指向左子树还是前驱 TYPE rType; //标示右子树为指向右子树还是后驱 _Node() { data = 0; left = NULL; right = NULL; isVisit = false; lType = TYPE_LINK; rType = TYPE_LINK; }}Node, *_PNode;//假定二叉树如下图所示，利用前序和中序、后序与中序可以唯一确定一棵二叉树的原理// 1// / \// 2 3// / \ / \// 4 5 6 7 // / \ /// 8 9 10const int MAX_NUM = 10; //二叉树的节点数int pre[MAX_NUM] = { 1, 2, 4, 8, 9, 5, 10, 3, 6, 7}; //前序遍历的数组int mid[MAX_NUM] = { 8, 4, 9, 2, 10, 5, 1, 6, 3, 7}; //中序遍历的数组int post[MAX_NUM] = { 8, 9, 4, 10, 5, 2, 6, 7,3, 1}; //后序遍历的数组//获取前序数组的data在中序数组的索引int GetPositionInMid(int data){ for (int i = 0; i < MAX_NUM; i++) { if (mid[i] == data) { return i; } }}//利用前序和中序可以唯一确定一棵二叉树//参数说明// pRoot —— 需要建造节点的指针引用// iPre —— 表示pRoot节点的左子树（右子树）在前序数组的第一个索引// iMid —— 表示pRoot节点的左子树（右子树）在中序数组的第一个索引// length —— 表示pRoot节点的左子树（右子树）的长度void PreAndMidRecurCreate(_PNode &pRoot, int iPre, int iMid, int length){ if (length <= 0) { return; } pRoot = new Node; pRoot->data = pre[iPre]; int pos = GetPositionInMid(pre[iPre]); PreAndMidRecurCreate(pRoot->left, iPre + 1, iMid, pos - iMid); PreAndMidRecurCreate(pRoot->right, iPre + (pos - iMid) + 1, pos + 1, length - (pos - iMid) - 1);}//利用后序和中序可以唯一确定一棵二叉树//参数说明// pRoot —— 需要建造节点的指针引用// iPost —— 表示pRoot节点的左子树（右子树）在后序数组的第一个索引// iMid —— 表示pRoot节点的左子树（右子树）在中序数组的第一个索引// length —— 表示pRoot节点的左子树（右子树）的长度void PostAndMidRecurCreate(_PNode &pRoot, int iPost, int iMid, int length){ if (length <= 0) { return; } pRoot = new Node; pRoot->data = post[iPost]; int pos = GetPositionInMid(post[iPost]); PostAndMidRecurCreate(pRoot->left, iPost - 1 - (length - (pos - iMid) - 1), iMid, pos - iMid); PostAndMidRecurCreate(pRoot->right, iPost - 1, pos + 1, length - (pos - iMid) - 1);}//****************************************二叉树的线索*******************************************begin_PNode prePreNode; //前序线索二叉树指向的节点前驱_PNode preMidNode; //中序线索二叉树指向的节点前驱_PNode prePostNode; //后序线索二叉树指向的节点前驱//前序线索二叉树的递归函数void PreInClues(_PNode &pRoot){ if (NULL != pRoot) { if (NULL == pRoot->left) //1、如果当前节点左子树为空，则线索 { pRoot->left = prePreNode; pRoot->lType = TYPE_CLUES; } if (NULL == prePreNode->right)//2、如果前驱节点右子树为空，则线索 { prePreNode->right = pRoot; prePreNode->rType = TYPE_CLUES; } prePreNode = pRoot; if (pRoot->lType == TYPE_LINK) { PreInClues(pRoot->left); } if (pRoot->rType == TYPE_LINK) { PreInClues(pRoot->right); } }}//前序线索二叉树//参数说明 pPreRoot —— 指向根节点的指针// pRoot —— 根节点的指针void PreTraversalInClues(_PNode &pPreRoot, _PNode &pRoot){ pPreRoot = new Node; pPreRoot->right = pPreRoot; pPreRoot->rType = TYPE_CLUES; pPreRoot->lType = TYPE_LINK; if (NULL == pRoot) { pPreRoot->left = pPreRoot; } else { pPreRoot->left = pRoot; prePreNode = pPreRoot; PreInClues(pRoot); prePreNode->right = pPreRoot; prePreNode->rType = TYPE_CLUES; pPreRoot->right = prePreNode; }}//中序线索化的输出void PreCluesOutput(_PNode pPreRoot){ _PNode pNode = pPreRoot->left; while (pNode != pPreRoot) { cout< data<<'\t'; if (pNode->lType == TYPE_LINK) { pNode = pNode->left; } else { pNode = pNode->right; } }}//中序线索二叉树的递归函数void MidInClues(_PNode &pRoot){ if (NULL != pRoot) { MidInClues(pRoot->left); if (NULL == pRoot->left) //1、如果当前节点左子树为空，则线索 { pRoot->left = preMidNode; pRoot->lType = TYPE_CLUES; } if (NULL == preMidNode->right) //2、如果前驱节点右子树为空，则线索 { preMidNode->right = pRoot; preMidNode->rType = TYPE_CLUES; } preMidNode = pRoot; MidInClues(pRoot->right); }}//中序线索二叉树void MidTraversalInClues(_PNode &pPreRoot, _PNode &pRoot){ pPreRoot = new Node; pPreRoot->right = pPreRoot; pPreRoot->rType = TYPE_CLUES; pPreRoot->lType = TYPE_LINK; if (NULL == pRoot) { pPreRoot->left = pPreRoot; } else { pPreRoot->left = pRoot; preMidNode = pPreRoot; MidInClues(pRoot); preMidNode->right = pPreRoot; preMidNode->rType = TYPE_CLUES; pPreRoot->right = preMidNode; }}//中序线索化的输出void MidCluesOutput(_PNode pPreRoot){ _PNode pNode = pPreRoot->left; while (pNode != pPreRoot) { while (pNode->lType == TYPE_LINK) { pNode = pNode->left; } cout< data<<'\t'; while (pNode->rType == TYPE_CLUES && pNode->right != pPreRoot) { pNode = pNode->right; cout< data<<'\t'; } pNode = pNode->right; }}//****************************************二叉树的线索*******************************************end int _tmain(int argc, _TCHAR* argv[]){ _PNode pRoot1 = NULL; _PNode pRoot2 = NULL; _PNode pPreRoot = NULL; _PNode pMidRoot = NULL; //cout< <<"******************根据前序和中序建造二叉树********************"< <
运行界面如下：
