已知二叉树先序遍历中序遍历求其后序遍历、重建二叉树

水深无声 2022-08-09 01:53 194阅读 0赞

已知二叉树先序遍历中序遍历求其后序遍历

(注：已知中序遍历序列和剩下两种遍历序列中的一种都可以确定二叉树，即可得到另一种遍历序列，      但是已知前序遍历和后序遍历序列并不能唯一确定二叉树，例如：preorder：AB postorder：BA，我们不能确定B是A的左子还是右子。）

二叉树的先序遍历的第一个元素总是树的根结点，而在中序遍历中，根结点在序列的中间，其左右两边分别是根结点的左右子树。

因此我们可以根据先序遍历确定根结点，然后在中序遍历中扫描根结点，同时可得到左右子树的中序遍历和先序遍历，递归此过程，即可获得二叉树的所有结点。

而后序遍历即为根结点左子树的后序遍历+右子树的后序遍历+根结点。

递归实现思路非常简单，C++代码：

string getpostorder(char* preorder, char* inorder, int length){
    	string str = "";
    	char* rootInorder;        //根结点在中序遍历中的位置
    	int leftlength;           //左子树长度
    	if (length <= 0||preorder==NULL||inorder==NULL)//递归边界条件
    		return "";
    	else{
    		leftlength = 0;
    		rootInorder = inorder;
                    //扫描根结点
                    while (leftlength < length&& *rootInorder != preorder[0]){
    			leftlength++;
    			rootInorder++;
    		}
    		if (rootInorder == inorder+length-1 && *rootInorder != preorder[0])
    			throw exception("Invalid input.");
                    //递归
                    str = getpostorder(preorder + 1,inorder,leftlength)+getpostorder(preorder+leftlength+1,inorder+leftlength+1,length-leftlength-1);
    		str.push_back(preorder[0]);
    		return str;
    	}
    }

已知二叉树先序遍历中序遍历重建二叉树

二叉树的重建，也是运用递归方法思想，首先建立根结点，然后递归构建出其左右子树，递归边界条件为先序遍历和中序遍历只有一个元素的时候。

二叉树结点一般结构为：

typedef struct BinaryTreeNode{
        char data;
        struct BinaryTreeNode *left;
        struct BinaryTreeNode *right;
    }BiTreeNode;

重建代码：

BinaryTreeNode *Construct(char* preorder,char* inorder, int length){
    	if (preorder == NULL || inorder == NULL || length <= 0)
    		return NULL;
    	return ConstructCore(preorder, preorder + length - 1, inorder, inorder + length - 1);
    }
    
    //递归函数 前两个参数和后两个参数分别确定了某子树先序遍历和中序遍历序列
    //参数为指针，操作方便
    BinaryTreeNode *ConstructCore(char* startPreorder, char* endPreorder, char* startInorder, char* endInorder){
            //构建根节点
            char rootValue = startPreorder[0];
    	BinaryTreeNode* root = new BinaryTreeNode();
    	root->left = root->right = NULL;
    	root->data = rootValue;
    	if (startPreorder == endPreorder){
    		if (startInorder == endInorder && *startPreorder == *startInorder){
    			return root;
    		}
    		else
    			throw exception("Invalid input.");
    	}
    	
    	char* rootInorder = startInorder;
            //扫描中序遍历寻找根结点
    	while (rootInorder <= endInorder && *rootInorder != *startPreorder)
    		++rootInorder;
    	if (rootInorder==endInorder && *rootInorder!=rootValue)
    		throw exception("Invalid input.");
    
            //这两个变量用于确定左右子树
    	int leftLength = rootInorder - startInorder;
    	char* leftPreorderEnd = startPreorder + leftLength;
    
    	if (leftLength > 0){
                    //构建左子树
    		root->left = ConstructCore(startPreorder+1,leftPreorderEnd,startInorder,rootInorder-1);
    	}
    	if (leftLength < endPreorder - startPreorder){//右子树
    		root->right = ConstructCore(leftPreorderEnd+1,endPreorder,rootInorder+1,endInorder);
    	}
    	return root;
    }

加上main（）函数之后的完整代码:

#include<iostream>
    #include<string>
    #include<cstring>
    #include<stack>
    using namespace std;
    
    typedef struct BinaryTreeNode{
    	char data;
    	struct BinaryTreeNode *left;
    	struct BinaryTreeNode *right;
    }BiTreeNode;
    
    BinaryTreeNode *ConstructCore(char* startPreorder, char* endPreorder, char* startInorder, char* endInorder){
    	char rootValue = startPreorder[0];
    	BinaryTreeNode* root = new BinaryTreeNode();
    	root->left = root->right = NULL;
    	root->data = rootValue;
    	if (startPreorder == endPreorder){
    		if (startInorder == endInorder && *startPreorder == *startInorder){
    			return root;
    		}
    		else
    			throw exception("Invalid input.");
    	}
    	
    	char* rootInorder = startInorder;
    	while (rootInorder <= endInorder && *rootInorder != *startPreorder)
    		++rootInorder;
    	if (rootInorder==endInorder && *rootInorder!=rootValue)
    		throw exception("Invalid input.");
    
    	int leftLength = rootInorder - startInorder;
    	char* leftPreorderEnd = startPreorder + leftLength;
    
    	if (leftLength > 0){
    		root->left = ConstructCore(startPreorder+1,leftPreorderEnd,startInorder,rootInorder-1);
    	}
    	if (leftLength < endPreorder - startPreorder){
    		root->right = ConstructCore(leftPreorderEnd+1,endPreorder,rootInorder+1,endInorder);
    	}
    	return root;
    }
    
    BinaryTreeNode *Construct(char* preorder,char* inorder, int length){
    	if (preorder == NULL || inorder == NULL || length <= 0)
    		return NULL;
    	return ConstructCore(preorder, preorder + length - 1, inorder, inorder + length - 1);
    }
    
    //递归遍历重建的二叉树
    string posttravel(BinaryTreeNode* root){
    	string str="";
    	if (root != NULL){
    		str = posttravel(root->left) + posttravel(root->right);
    		str.push_back(root->data);
    		return str;
    	}
    	else
    		return "";
    }
    
    string getpostorder(char* preorder, char* inorder, int length){
    	string str = "";
    	char* rootInorder;
    	int leftlength;
    	if (length <= 0||preorder==NULL||inorder==NULL)
    		return "";
    	else{
    		leftlength = 0;
    		rootInorder = inorder;
    		while (leftlength < length&& *rootInorder != preorder[0]){
    			leftlength++;
    			rootInorder++;
    		}
    		if (rootInorder == inorder+length-1 && *rootInorder != preorder[0])
    			throw exception("Invalid input.");
    		str = getpostorder(preorder + 1,inorder,leftlength)+getpostorder(preorder+leftlength+1,inorder+leftlength+1,length-leftlength-1);
    		str.push_back(preorder[0]);
    		return str;
    	}
    }
    
    int main(){
    	string postorder;
    	char preorder[100], inorder[100];
    	cout << "Input preoder & inorder of the binary tree:";
    	cin >> preorder >> inorder;
    	BinaryTreeNode* root=Construct(preorder,inorder,strlen(preorder));
    	//postorder = posttravel(root);//此函数为递归后序遍历重建的二叉树
    	postorder = getpostorder(preorder, inorder, strlen(preorder));
    	cout << postorder << endl;
    	system("pause");
    	return 0;
    }