【数据结构】二叉树的创建

---

二叉树的创建与遍历

以下图的二叉树为例：

Binary_Tree.h

#ifndef BINARY_TREE_H
#define BINARY_TREE_H

typedef char Element;
//二叉链式树节点
typedef struct BtNode
{
	Element data;				//数据域
	struct BtNode* leftchild;	//左孩子
	struct BtNode* rightchild;	//右孩子
}BtNode, *BinaryTree;


#endif

创建方式一

Bt.cpp

#include"Binary_Tree.h"
#include <iostream>

using namespace std;

//前序遍历二叉树
void PreOrder(BinaryTree root)
{
	if (root == NULL) return;
	cout << root->data << " ";
	PreOrder(root->leftchild);
	PreOrder(root->rightchild);
}

//中序遍历二叉树
void MidOrder(BinaryTree root)
{
	if (root == NULL) return;
	MidOrder(root->leftchild);
	cout << root->data << " ";
	MidOrder(root->rightchild);
}

//后序遍历二叉树
void LastOrder(BinaryTree root)
{
	if (root == NULL) return;
	LastOrder(root->leftchild);
	LastOrder(root->rightchild);
	cout << root->data << " ";
}

//申请节点
BtNode* BuyNode()
{
	BtNode* node = (BtNode*)malloc(sizeof(BtNode));
	if (NULL == node) return NULL;
	memset(node, 0, sizeof(BtNode));
	return node;
}
//创建二叉树方式一
//先序创建：先序序列：ABC##DE##F##G#H##
BtNode* Create_Bt()
{
	BtNode* s = NULL;
	Element elem;
	cin >> elem;
	if (elem != '#')
	{
		s = BuyNode();
		s->data = elem;
		s->leftchild = Create_Bt();
		s->rightchild = Create_Bt();
	}
	return s;
}


int main()
{
	BtNode* root = Create_Bt();
	PreOrder(root);
	cout << endl;
	MidOrder(root);
	cout << endl;
	LastOrder(root);
	cout << endl;
	return 0;
}

---

创建方式二：先序+中序

//创建方式二：
//先序序列：ABCDEFGH
//中序序列：CBEDFAGH
int FindRoot_from_Mid(const char* mid, int len,Element rootdata)
{
	int pos = -1;
	for (int i = 0; i < len; ++i)
	{
		if (mid[i] == rootdata)
		{
			pos = i;
			break;
		}
	}
	return pos;
}
BtNode* C_Bt_PM(const char* pre, const char* mid, int len)
{
	BtNode* s = NULL;
	if (len > 0)
	{
		s = BuyNode();
		if (NULL == s)
			exit(1);
		s->data = pre[0];	
		//中序中寻找相对根结点
		int pos = FindRoot_from_Mid(mid, len, pre[0]);
		//两序列不是同一个二叉树
		if (-1 == pos) exit(-1);

		s->leftchild = C_Bt_PM(pre + 1, mid, pos);
		s->rightchild = C_Bt_PM(pre + pos + 1, mid + pos + 1, len - pos - 1);
	}
	return s;
}
BtNode* Create_Bt_PM(const char* pre, const char* mid, int len)
{
	if (pre == NULL || mid == NULL || len <= 0) return NULL;
	else
	{
		return C_Bt_PM(pre, mid, len);
	}
}
int main()
{
	const char* pre = "ABCDEFGH";
	const char* mid = "CBEDFAGH";
	BtNode* root = Create_Bt_PM(pre, mid,strlen(pre));
	
	PreOrder(root);
	cout << endl;
	MidOrder(root);
	cout << endl;
	LastOrder(root);
	cout << endl;
	return 0;
}

---

创建方式三：中序+后序

//创建方式三：
//中序序列：CBEDFAGH
//后序序列：CEFDBHGA
int FindRoot_from_Mid(const char* mid, int len, Element rootdata)
{
	int pos = -1;
	for (int i = 0; i < len; ++i)
	{
		if (mid[i] == rootdata)
		{
			pos = i;
			break;
		}
	}
	return pos;
}
BtNode* C_Bt_ML(const char* mid, const char* last, int len)
{
	BtNode* s = NULL;
	if (len > 0)
	{
		s = BuyNode();
		if (NULL == s)
			exit(1);
		s->data = last[len - 1];
		//中序中寻找相对根结点
		int pos = FindRoot_from_Mid(mid, len, last[len - 1]);
		//两序列不是同一个二叉树
		if (-1 == pos) exit(-1);

		s->leftchild = C_Bt_ML(mid, last, pos);
		s->rightchild = C_Bt_ML(mid + pos + 1, last + pos, len - pos - 1);
	}
	return s;
}
BtNode* Create_Bt_ML(const char* mid, const char* last, int len)
{
	if (mid == NULL || last == NULL || len <= 0) return NULL;
	else
	{
		return C_Bt_ML(mid, last, len);
	}
}
int main()
{
	const char* mid = "CBEDFAGH";
	const char* last = "CEFDBHGA";
	BtNode* root = Create_Bt_ML(mid, last,strlen(mid));

	PreOrder(root);
	cout << endl;
	MidOrder(root);
	cout << endl;
	LastOrder(root);
	cout << endl;
	return 0;
}