C++二叉树与线索二叉树

二叉树

1.学过数据结构的朋友应该都知道二叉树吧。

C++二叉树与线索二叉树C++二叉树与线索二叉树

这是一颗满二叉树，原理自己看书去，了解原理才能够更好的理解代码。我就不在这说原理了。

上代码。

构造一棵二叉树（左子树先构造）

1.这个是模板函数，模板函数的作用是你给定一个类型参数就行了，提高代码复用。就不用为了一个类型重载一个函数啦。

template<typename T>
void Tree<T>::CreateTree(TreeNode<T> *(&Node), list<T> &val)//利用list中栈的原理配置二叉树
{
	if (val.size())
	{
		auto beg = val.begin();
		T c = *beg;
		if (c == ' ')//表示该节点为空，他的父节点没有该叶子节点
		{
			val.pop_front();
			Node = NULL;
		}
		else
		{
			Node = new TreeNode<T>;
			Node->LChild = NULL;
			Node->RChild = NULL;
			Node->Ltag = LINK;//这个是线索树的标记
			Node->Rtag = LINK;//这个是线索树的标记
			Node->data = c;
			val.pop_front();//将顶层数据弹出

			CreateTree(Node->LChild, val);//构造Node的左子树
			CreateTree(Node->RChild, val);//同理构造右子树
		}
	}
}
/*
	list<T>：构造二叉树的原始数据；
	Node：一般是树的根Root;
	通过递归的方式先构造左子树再构造右子树。
*/

C++二叉树与线索二叉树C++二叉树与线索二叉树

注释：LC=要调用CreateTree(Node->LChild, val);

RC=CreateTree(Node->RChild, val);但凡节点的孩子为空都是用LC,和RC替换。

如果c==’ '，表示该节点为空。

二叉树的非递归遍历

由于递归遍历书上就有，所以不多做解释。

中序遍历的规则：先访问左节点，到根节点，再到右节点，

template<typename T>
void Tree<T>::StackInOrderPrint(TreeNode<T> *Node, stack<TreeNode<T>*> &val)//非递归中序遍历
{
	while (Node || val.size())//存在二叉树时进行遍历
	{
		//当节点存在先入栈，将其左节点地址赋值给Node，直至遍历至最左边的叶子节点
		while (Node)//1,2,3步
		{
			val.push(Node);
			Node = Node->LChild;
		}

		if (val.size())//4，5步
		{
			//当Node为空时，也就是栈顶元素节点的左子树为空时，弹出栈顶元素。
			//Node指向弹出的栈顶元素，打印出数据值，再对其右子树进行遍历。
			Node = val.top();//过去栈顶元素地址
			val.pop();//弹出栈顶元素
			cout << Node->data << " ";
			Node = Node->RChild;
		}
	}
}

/*
	利用压栈以及出栈的方式进行遍历
*/

C++二叉树与线索二叉树C++二叉树与线索二叉树

到此基本结束了，关闭时要记得delete内存,不要让内存泄露了。

线索二叉树

1.所谓线索二叉树就是提升查找节点前驱和后继的效率，牺牲一点内存，但是充分利用了空指针域。

enum { LINK, CLUES };//LINK表示链接的孩子节点，CLUES链接的是线索节点
template<typename T>
void Tree<T>::CreateCluesHeadNode()//创建一个标记节点，标记作用当前节点的前驱。
{
	if (HeadNode)
	{
		m_PreCluesNode = new TreeNode<T>;
		m_PreCluesNode->Ltag = LINK;//LINK是指向孩子节点
		m_PreCluesNode->Rtag = LINK;
		m_PreCluesNode->RChild = m_PreCluesNode;//指向自己是防止第一次构造线索树的时候出现乱指的问题
		m_PreCluesNode->LChild = HeadNode;
		m_TempCluesNode = m_PreCluesNode;//让中间节点指向线索头节点，在构造线索树中用中间节点，是防止m_PreCluesNode在线索化时地址被篡改，无法被正确析构。
	}
}
/*
	Build一个头指针m_PreCluesNode，使其左孩子指向树的根部。而右孩子指向自己。防止第					一次线索的时候会指向树的左子树的最左叶子节点。
*/

template<typename T>
TreeNode<T>* Tree<T>::BuildCluesTree(TreeNode<T> *Node)
{
	if(Node)
	{
		BuildCluesTree(Node->LChild);//一直递归到左子树的叶子节点
		
		if (!Node->LChild)//如果Node节点没有左孩子
		{
			Node->Ltag = CLUES;//将标记设置为线索
			Node->LChild = m_TempCluesNode;//左孩子节点指向前一个节点。
		}

		if (!m_TempCluesNode->RChild)//前一个节点的右孩子为空时指向Node节点
		{
			m_TempCluesNode->Rtag = CLUES;
			m_TempCluesNode->RChild = Node;
		}

		m_TempCluesNode = Node;
		BuildCluesTree(Node->RChild);//以右孩子节点作为根节点递归
	}
	return Node;
}

源码：

编译环境：VS2017

//Tree.h
#pragma once
#include<list>
#include<stack>
using namespace std;
enum { LINK, CLUES };//LINK表示链接的孩子节点，CLUES链接的是线索节点

template<typename T>
struct TreeNode
{
	TreeNode<T> *LChild;
	TreeNode<T> *RChild;
	int Ltag;
	int Rtag;
	T data;
};

template<typename T>
class Tree
{
public:
	Tree();
	Tree(list<T> &val);
	~Tree();
	void CreateTree(TreeNode<T> *(&Node), list<T> &val);//创建一个二叉树
	void CreateCluesHeadNode();//创建标记节点记录当前节点的前驱。
	TreeNode<T>* BuildCluesTree(TreeNode<T> *Node);//创建线索树，要先创建标记节点，
	void AddLNode(Tree<T> *Node, T c);//扩充左孩子
	void AddRNode(Tree<T> *Node, T c);//扩充右孩子
	void StackInOrderPrint(TreeNode<T> *, stack<TreeNode<T>*> &val);//非递归中序遍历
	void InOrderPrint(TreeNode<T> *(&));//递归中序遍历
	void Release(TreeNode<T> *(&Node));//释放资源
public:
	TreeNode<T> *HeadNode;//头节点
	TreeNode<T> *m_PreCluesNode;//前驱节点
	TreeNode<T> *m_TempCluesNode;//中间节点，无需析构。
};

template<typename T>
Tree<T>::Tree()
{
}

template<typename T>
Tree<T>::Tree(list<T> &val)
{
	CreateTree(HeadNode, val);
}

template<typename T>
Tree<T>::~Tree()
{
	if (HeadNode)
	{
		Release(HeadNode);
	}

	if (m_PreCluesNode)
	{
		delete m_PreCluesNode;
		m_PreCluesNode = NULL;
	}
}

template<typename T>
void Tree<T>::Release(TreeNode<T> *(&Node))
{
	if (!Node) return;
	TreeNode<T> *LChild=NULL;
	TreeNode<T> *RChild=NULL;
	if (Node->Ltag == LINK)
	{
		LChild = Node->LChild;
	}

	if (Node->Rtag == LINK)
	{
		RChild = Node->RChild;
	}

	if (Node)
	{
		cout << "删除了:" << Node->data << endl;
		delete Node;
		Node = NULL;
	}

	if (LChild)
	{
		Release(LChild);
	}

	if (RChild)
	{
		Release(RChild);
	}
}

template<typename T>
void Tree<T>::CreateTree(TreeNode<T> *(&Node), list<T> &val)//利用list中栈的原理配置二叉树
{
	if (val.size())
	{
		auto beg = val.begin();
		T c = *beg;
		if (c == ' ')
		{
			val.pop_front();
			Node = NULL;
		}
		else
		{
			Node = new TreeNode<T>;
			Node->LChild = NULL;
			Node->RChild = NULL;
			Node->Ltag = LINK;
			Node->Rtag = LINK;
			Node->data = c;
			val.pop_front();

			CreateTree(Node->LChild, val);
			CreateTree(Node->RChild, val);
		}
	}
}
template<typename T>
void Tree<T>::StackInOrderPrint(TreeNode<T> *Node, stack<TreeNode<T>*> &val)//非递归中序遍历
{
	while (Node || val.size())
	{
		while (Node)
		{
			val.push(Node);
			Node = Node->LChild;
		}

		if (val.size())
		{
			Node = val.top();
			val.pop();
			cout << Node->data << " ";
			Node = Node->RChild;
		}
	}
}

template<typename T>
void Tree<T>::AddLNode(Tree<T> *Node, T c)
{

}

template<typename T>
void Tree<T>::AddRNode(Tree<T> *Node, T c)
{

}

template<typename T>
void Tree<T>::InOrderPrint(TreeNode<T> *(&tree))//递归调用
{
	if (tree)
	{
		InOrderPrint(tree->LChild);
		cout << tree->data << " ";
		InOrderPrint(tree->RChild);
	}
}

template<typename T>
TreeNode<T>* Tree<T>::BuildCluesTree(TreeNode<T> *Node)
{
	if(Node)
	{
		BuildCluesTree(Node->LChild);//一直递归到左子树的叶子节点
		
		if (!Node->LChild)//如果Node节点没有左孩子
		{
			Node->Ltag = CLUES;//将标记设置为线索
			Node->LChild = m_TempCluesNode;//左孩子节点指向前一个节点。
		}

		if (!m_TempCluesNode->RChild)//前一个节点的右孩子为空时指向Node节点
		{
			m_TempCluesNode->Rtag = CLUES;
			m_TempCluesNode->RChild = Node;
		}

		m_TempCluesNode = Node;
		BuildCluesTree(Node->RChild);//以右孩子节点作为根节点递归
	}
	return Node;
}

template<typename T>
void Tree<T>::CreateCluesHeadNode()//创建一个标记节点，标记作用当前节点的前驱。
{
	if (HeadNode)
	{
		m_PreCluesNode = new TreeNode<T>;
		m_PreCluesNode->Ltag = LINK;
		m_PreCluesNode->Rtag = LINK;
		m_PreCluesNode->RChild = m_PreCluesNode;//指向自己是防止第一次构造线索树的时候出现乱指的问题
		m_PreCluesNode->LChild = HeadNode;
		m_TempCluesNode = m_PreCluesNode;//让中间节点指向前驱节点，在构造线索树中用中间节点，是防止析构的时候m_PreCluesNode内存改变而无法析构
	}
}

//.cpp
/*
	1.如果你要在函数体中new一个对象的话记得要传引用指针（*(&)或者返回一个指针，
	不然你new的内存就会找不到了，会导致内存泄露。
*/

#include<iostream>
#include"Tree.h"
using namespace std;

int main()
{
	list<char> val{'A','B','D',' ',' ','E',' ',' ','C','F',' ',' ','G',' ',' '};
	Tree<char> *tree;
	stack<TreeNode<char>*> NodeArray;
	tree = new Tree<char>;
	tree->CreateTree(tree->HeadNode,val);
	tree->InOrderPrint(tree->HeadNode);
	cout << endl;
	tree->StackInOrderPrint(tree->HeadNode, NodeArray);
	cout << endl;
	tree->CreateCluesHeadNode();
	tree->BuildCluesTree(tree->HeadNode);
	delete tree;
	system("pause");
	return 0;
}

C++二叉树与线索二叉树C++二叉树与线索二叉树

C++二叉树与线索二叉树

二叉树

构造一棵二叉树（左子树先构造）

二叉树的非递归遍历

线索二叉树

继续阅读

树的基本概念(定义、基本术语、性质)

GSL--GNU Scientific Library

D5|哈希表，善用数据结构

如何成为一名.net 工程师?

BMP文件结构及图像每行字节计算方法

D. Ehab the Xorcist(构造+思维)

查找算法之二分查找查找算法之二分查找

JAVA高效编程指南

CQ V1.0分词bates(基于双数组tire树)—应该是目前最快的中文分词算法

【数据结构】医院选址

[转]ISUP信令的IAM消息详细内容

笔试面试题目：滑动窗口(二)

交通/城市相关的公开的数据集上学时整理的Xie et al., 2020收集的

数据结构与算法（27）——排序（二）

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

Linux设备模型（中）之上层容器