滴水-day37-二叉树

在内存图中会有两个地址来存储左右子树，而这两个地址，相对小的那个地址通常存储的是左子树，而大地址存储的是右子树。

普通二叉树

#pragma once

#include <iostream>
#include <windows.h>
#include <cstring>
#include <string>

using  namespace std;

// 怪物类
class Monster
{
public:
	int ID;
	int Level;
	//std::string Name;
	char Name[20];
public:
	Monster() {}
	Monster(int ID, int Level, const char* Name)
	{
		this->ID = ID;
		this->Level = Level;
		//this->Name = Name;
		memcpy(&this->Name, Name, strlen(Name) + 1);
	}
};

template<class T>
class TreeNode {
public:
	T element;							//当前节点存储的数据	
	TreeNode<T>* pLeft;					//指向左子节点的指针	
	TreeNode<T>* pRight;				//指向右子节点的指针	

	TreeNode(T& ele) {
		//初始化Node节点					
		memset(&element, 0, sizeof(TreeNode));
		//为元素赋值					
		memcpy(&element, &ele, sizeof(T));
		pLeft = pRight = NULL;
	}
};

template<class T>
class BSortTree {
public:
	BSortTree();					//构造函数	
	~BSortTree();					//析构函数	
public:
	void InOrderTraverse(TreeNode<T>* pNode);					//中序遍历	
	void PreOrderTraverse(TreeNode<T>* pNode);					//前序遍历	
	void PostOrderTraverse(TreeNode<T>* pNode);					//后序遍历	
	TreeNode<T>* GetRoot();					//返回根节点	
	int GetDepth(TreeNode<T>* pNode);		//返回某个节点的高度/深度	
private:
	void Init();
	void Clear(TreeNode<T>* pNode);
private:
	TreeNode<T>* m_pRoot;					//根结点指针	
	int size;								//树中元素总个数	
};

template<class T>
BSortTree<T>::BSortTree()
{
	Init();
}
template<class T>
BSortTree<T>::~BSortTree() {

	//释放所以节点空间	
	Clear(m_pRoot);
}

// 初始化函数
template<class T>
void BSortTree<T>::Init()
{

	Monster m1(1, 1, "刺猬");
	Monster m2(2, 2, "野狼");
	Monster m3(3, 3, "野猪");
	Monster m4(4, 4, "士兵");
	Monster m5(5, 5, "火龙");
	Monster m6(6, 6, "独角兽");
	Monster m7(7, 7, "江湖大盗");

	TreeNode<Monster>* n1 = new TreeNode<Monster>(m1);
	TreeNode<Monster>* n2 = new TreeNode<Monster>(m2);
	TreeNode<Monster>* n3 = new TreeNode<Monster>(m3);
	TreeNode<Monster>* n4 = new TreeNode<Monster>(m4);
	TreeNode<Monster>* n5 = new TreeNode<Monster>(m5);
	TreeNode<Monster>* n6 = new TreeNode<Monster>(m6);
	TreeNode<Monster>* n7 = new TreeNode<Monster>(m7);

	m_pRoot = n5;
	n5->pLeft = n4;
	n5->pRight = n6;
	n4->pLeft = n1;
	n1->pRight = n2;
	n6->pLeft = n3;
	n3->pRight = n7;
	size = 7;

	/*
					5

				4		6

			1		    3

				 2		        7

	*/
}
template<class T>
TreeNode<T>* BSortTree<T>::GetRoot()
{
	return m_pRoot;
}

template<class T>
int BSortTree<T>::GetDepth(TreeNode<T>* pNode)
{
	if (pNode == NULL)
	{
		return 0;
	}
	else
	{
		int m = GetDepth(pNode->pLeft);
		int n = GetDepth(pNode->pRight);
		return (m > n) ? (m + 1) : (n + 1);
	}
}

template<class T>
void BSortTree<T>::InOrderTraverse(TreeNode<T>* pNode)
{

	// 中序遍历所有怪物,列出怪的名字						
	// 左 根 右
	char* pName = nullptr;
	if (pNode != NULL)
	{
		InOrderTraverse(pNode->pLeft);
		pName = (char*)&pNode->element;
		pName += 0x8;
		cout << pNode->element.Name << endl;
		InOrderTraverse(pNode->pRight);
	}
}

template<class T>
void BSortTree<T>::PreOrderTraverse(TreeNode<T>* pNode)
{

	// 前序遍历所有怪物,列出怪的名字	
	// 根 左 右
	char* pName = nullptr;
	if (pNode != NULL)
	{
		pName = (char*)(&pNode->element);
		pName += 0x8;
		cout << pName << endl;
		PreOrderTraverse(pNode->pLeft);
		PreOrderTraverse(pNode->pRight);
	}
}

template<class T>
void BSortTree<T>::PostOrderTraverse(TreeNode<T>* pNode)
{

	//后序遍历所有怪物,列出怪的名字
	// 左 右 根
	char* pName = nullptr;
	if (pNode != NULL)
	{
		PostOrderTraverse(pNode->pLeft);
		PostOrderTraverse(pNode->pRight);
		pName = (char*)(&pNode->element);
		pName += 0x8;
		cout << pName << endl;
	}
}

template<class T>
void BSortTree<T>::Clear(TreeNode<T>* pNode)
{
	if (pNode != NULL)
	{
		Clear(pNode->pLeft);
		Clear(pNode->pRight);
		delete pNode;
	}
}

搜索二叉树

平衡二叉树

遍历方式

这三种遍历方式都是以根为准，前就表示根在第一位，中就在第二位，后就在最后。

遍历中可以理解为右永远在左的后边，和平常做运动一样，都是以左为开始。

前序遍历

根，左，右

template<class T>
void BSortTree<T>::PreOrderTraverse(TreeNode<T>* pNode)
{

	// 前序遍历所有怪物,列出怪的名字	
	// 根 左 右
	char* pName = nullptr;
	if (pNode != NULL)
	{
		pName = (char*)(&pNode->element);
		pName += 0x8;
		cout << pName << endl;
		PreOrderTraverse(pNode->pLeft);
		PreOrderTraverse(pNode->pRight);
	}
}

中序遍历

左，根，右

template<class T>
void BSortTree<T>::InOrderTraverse(TreeNode<T>* pNode)
{

	// 中序遍历所有怪物,列出怪的名字						
	// 左 根 右
	char* pName = nullptr;
	if (pNode != NULL)
	{
		InOrderTraverse(pNode->pLeft);
		pName = (char*)&pNode->element;
		pName += 0x8;
		cout << pNode->element.Name << endl;
		InOrderTraverse(pNode->pRight);
	}
}

后续遍历

左，右，根

template<class T>
void BSortTree<T>::PostOrderTraverse(TreeNode<T>* pNode)
{

	//后序遍历所有怪物,列出怪的名字
	// 左 右 根
	char* pName = nullptr;
	if (pNode != NULL)
	{
		PostOrderTraverse(pNode->pLeft);
		PostOrderTraverse(pNode->pRight);
		pName = (char*)(&pNode->element);
		pName += 0x8;
		cout << pName << endl;
	}
}

二叉树反汇编分析