資料結構與算法：初識樹

任務：使用C++編寫一個簡單的樹類型

頭檔案Tree.h如下：

#pragma once
#include <string.h>

//定義樹類型
template <class T>
class MyTree {
	T data;				// 資料
	MyTree* pParent;	// 父節點位址
	MyTree* pBrother;	// 兄弟節點位址
	MyTree* pChild;		// 子節點位址
public:
	MyTree();
	~MyTree();
	
	void InsertNode(T data, bool bIsChild = true); //插入節點函數
};


template<class T>
MyTree<T>::MyTree()
{
	data = 0;
	pParent = pBrother = pChild = NULL;
}


template<class T>
MyTree<T>::~MyTree()
{
	//這裡暫時先不寫節點的記憶體釋放
	pParent = pBrother = pChild = NULL;
}


/*
	插入節點函數
	規則:	1、如果bIsChild為真，新節點插入為最小孩子的孩子
			2、如果bIsChild為假，新節點插入為最小孩子的最小兄弟
*/
template<class T>
void MyTree<T>::InsertNode(T data, bool bIsChild)
{
	// 建立新節點
	MyTree* pNew = new MyTree;
	memset(pNew, 0, sizeof(MyTree));
	pNew->data = data;

	// 擷取目前樹的最小孩子
	MyTree* pTemp = this;
	while (pTemp->pChild)
	{
		pTemp = pTemp->pChild;
	}

	if (bIsChild) {
		//新節點設定為最小孩子的孩子
		pTemp->pChild = pNew;
		pNew->pParent = pTemp;
	}
	else
	{
		//新節點設定為最小孩子的最小兄弟的兄弟
		while (pTemp->pBrother)
		{
			pTemp = pTemp->pBrother;
		}
		pTemp->pBrother = pNew;
		pNew->pParent = pTemp->pParent;
	}
}
           

源檔案Tree.cpp如下：

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

int main()
{
	//初始化樹類型 Tree
	MyTree<int> Tree;

	//插入若幹元素
	Tree.InsertNode(1);
	Tree.InsertNode(2,false);
	Tree.InsertNode(3,false);
	Tree.InsertNode(11);
	Tree.InsertNode(12,false);
	Tree.InsertNode(111);
	Tree.InsertNode(112,false);
	Tree.InsertNode(113,false);

	printf("hello");
	while (1);
	return 0;
}
           

運作結果：

插入若幹元素後，進入斷點調試，監視Tree的記憶體情況如下圖所示，可看出已經具備基本的樹結構