首页 / 算法 / 已知中序后序创建二叉树

已知中序后序创建二叉树

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了已知中序后序创建二叉树，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1591字，纯文字阅读大概需要3分钟。

内容图文

    
#include<iostream.h>
#include<string.h>
#include<stdlib.h>
#include<assert.h>

template<class Type>
class BinaryTree
{
public:
	struct TreeNode
	{
		Type data;
		TreeNode *leftchild, *rightchild;
	};
	BinaryTree() {}
	~BinaryTree(){}
private:
	TreeNode *root;

	static TreeNode *_BuyNode()
	{
		TreeNode *p = (TreeNode *)malloc(sizeof(TreeNode));
		assert(p != NULL);
		return p;
	}

	static int find(Type *is, const Type &x, int n)
	{
		for(int i = 0; i < n; ++i)
		{
			if(is[i] == x)
				return i;
		}
		return -1;
	}

	static TreeNode *CreatInPost(Type *post, Type *is, int n)
	{
		if(post == NULL || is == NULL || n ==0)
			return NULL;
		else
		{
			TreeNode *s = _BuyNode();
			s->data = post[n-1];

			int num = find(is, post[n-1], n);
			if(num == -1)
				exit(1);
			s->leftchild = CreatInPost(post, is,num);//此处放进去的是线序遍历的前num个
			s->rightchild = CreatInPost(post+num, is+num +1, n-num-1);//此处减1是因为这是从后序遍历中找的每次最后一个数就被使用了，每次到这里就要将它除掉
			return s;
		}
		
	}

	static void PreOrder(TreeNode *root)
	{
		if(root != NULL)
		{
			cout << root->data << " ";
			PreOrder(root->leftchild);
			PreOrder(root->rightchild);
		}
	}
public:
	void Creat(Type *post, Type *is, int n)
	{
		if(post != NULL && is != NULL)
		root = CreatInPost(post, is, n);
	}
	void PreOrder()
	{
		PreOrder(root);
		cout << endl;
	}
};

int main(void)
{
	BinaryTree<int> tree;
	int post[] = {34,56,67,45,23,89,78,12};
	int is[] = {34,23,56,45,67,12,78,89};
	int n = sizeof(post) / sizeof(post[0]);
	
	tree.Creat(post, is, n);
	tree.PreOrder();

	return 0;
}


原文：http://blog.csdn.net/xiaomoniao/article/details/21553647

内容总结

以上是互联网集市为您收集整理的已知中序后序创建二叉树全部内容，希望文章能够帮你解决已知中序后序创建二叉树所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1069826.html

来源：【匿名】