【数据结构】智能指针管理二叉树

---

二叉树结构

#ifndef BINARY_TREE_H
#define BINARY_TREE_H
#include <iostream>
#include<memory>
using namespace std;
typedef char Element;
//二叉链式树节点
typedef struct BtNode
{
	Element data;				//数据域
	struct BtNode* leftchild;	//左孩子
	struct BtNode* rightchild;	//右孩子
}BtNode, *BinaryTree;

//二叉链式shared_ptr树节点
#if 1
typedef struct SBT_Node
{
	Element data;				//数据域
	std::shared_ptr<SBT_Node> leftchild;	//左孩子
	std::shared_ptr<SBT_Node> rightchild;	//右孩子

	SBT_Node() { cout << "SBT_Node() "<< endl; }
	~SBT_Node() { cout << "~SBT_Node() "<< this->data<< endl; }
}SBT_Node;

#endif
#endif

---

完整代码

//改造二叉树使用智能指针进行管理
#if 0 
//申请节点
SBT_Node* BuyNode()
{
	SBT_Node* node = (SBT_Node*)malloc(sizeof(SBT_Node));
	if (NULL == node) return NULL;
	memset(node, 0, sizeof(SBT_Node));
	return node;
}

//创建方式三：
//中序序列：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;
}
shared_ptr<SBT_Node> C_Bt_ML_Shared(const char* mid, const char* last, int len)
{
	shared_ptr<SBT_Node> s(NULL);
	if (len > 0)
	{
		s = make_shared<SBT_Node>();
		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_Shared(mid, last, pos);
		s->rightchild = C_Bt_ML_Shared(mid + pos + 1, last + pos, len - pos - 1);
	}
	return s;
}
shared_ptr<SBT_Node> Create_Bt_ML_Shared(const char* mid, const char* last, int len)
{
	if (mid == NULL || last == NULL || len <= 0) return NULL;
	else
	{
		return C_Bt_ML_Shared(mid, last, len);
	}
}
int main()
{
	const char* mid = "CBEDFAGH";
	const char* last = "CEFDBHGA";
	shared_ptr<SBT_Node> root = Create_Bt_ML_Shared(mid, last,strlen(mid));

	return 0;
}
#endif