由二叉樹的前序和中序如何得到二叉樹的后序呢？

由二叉樹的前序和中序如何得到二叉樹的后序呢？

在山城等地區(qū)，都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局，加強(qiáng)發(fā)展的系統(tǒng)性、市場(chǎng)前瞻性、產(chǎn)品創(chuàng)新能力，以專注、極致的服務(wù)理念，為客戶提供做網(wǎng)站、成都網(wǎng)站建設(shè) 網(wǎng)站設(shè)計(jì)制作定制開發(fā),公司網(wǎng)站建設(shè),企業(yè)網(wǎng)站建設(shè),高端網(wǎng)站設(shè)計(jì),營(yíng)銷型網(wǎng)站建設(shè),成都外貿(mào)網(wǎng)站建設(shè)公司,山城網(wǎng)站建設(shè)費(fèi)用合理。

首先得明白什么是前序、中序、后序。

二叉樹前序：遍歷順序?yàn)?，根?jié)點(diǎn)、左子樹、右子樹；中序：遍歷順序?yàn)?，左子樹、根?jié)點(diǎn)、右子樹；后序：遍歷順序?yàn)?，左子樹、右子樹、根?jié)點(diǎn)

可以發(fā)現(xiàn)，二叉樹前序中的第一個(gè)節(jié)點(diǎn)為樹的根節(jié)點(diǎn)root，然后找出root在中序里面的位置，就可以把前序和中序分別劃分為左、右子樹兩個(gè)部分，然后遞歸調(diào)用即可。

#include<iostream>
using namespace std;
template<class T>
struct BinaryTreeNode
{
	T _data;
	BinaryTreeNode* _left;
	BinaryTreeNode* _right;
	BinaryTreeNode(const T& x)
		:_data(x)
		, _left(NULL)
		, _right(NULL)
	{}
};
template<class T>
class BinaryTree
{
protected:
	BinaryTreeNode<T>* _root;
protected:
	void _PreOrder(BinaryTreeNode<T>* root)
	{
		if (root != NULL)
		{
			cout << root->_data << " ";
			_PreOrder(root->_left);
			_PreOrder(root->_right);
		}
		return;
	}
	BinaryTreeNode<T>* _CreateBinary(char* preOrder, char* inOrder, int length)
	{
		BinaryTreeNode<T>* root = NULL;
		if (length == 0)
			return NULL;
		int tmp = *preOrder;
		int index = 0;
		while (index < length&&inOrder[index] != tmp)
			index++;
		if (index < length)
		{
			root = new BinaryTreeNode<T>(tmp-'0');
			root->_left = _CreateBinary(preOrder + 1, inOrder,index);
			root->_right = _CreateBinary(preOrder + index + 1, inOrder + index + 1, length - index - 1);
		}
		return root;
	}
	void _Clear(BinaryTreeNode<T>* root)
	{
		if (root)
		{
			_Clear(root->_left);
			_Clear(root->_right);
			delete root;
		}
	}
public:
	BinaryTree()
		:_root(NULL)
	{}
	~BinaryTree()
	{
		_Clear(_root);
		_root = NULL;
	}
	void  PreOrder()
	{
		_PreOrder(_root);
		cout << endl;
	}
	void CreateBinaryTree(char* preOrder, char* inOrder)
	{
		int length = strlen(preOrder);
		_root = _CreateBinary(preOrder, inOrder,length);
	}
};
void Test1()
{
	char* preOrder = "12473568";
	char* inOrder = "47215386";
	BinaryTree<int> bt;
	bt.CreateBinaryTree(preOrder, inOrder);
	bt.PreOrder();
}

網(wǎng)頁(yè)標(biāo)題：由二叉樹的前序和中序如何得到二叉樹的后序呢？
文章路徑：http://bm7419.com/article22/jcshjc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供定制開發(fā)、App開發(fā)、移動(dòng)網(wǎng)站建設(shè)、網(wǎng)站設(shè)計(jì)、面包屑導(dǎo)航、做網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)