文档章节

c++学习之前序递归遍历二叉树和中序循环遍历二叉树

指尖残雪
 指尖残雪
发布于 2016/05/22 23:56
字数 736
阅读 3
收藏 0

例子简单,不多说。近来手痒写了一下。代码如下:

简单入门哦!!!

#include<iostream.h>
#include<memory.h>

template <class Type>
class CBinaryTree
{
private:
	int m_nNodeCount;
	Type* m_pRootNode;//根节点
public:
	CBinaryTree()
	{
		m_pRootNode = new Type();
		m_nNodeCount = 1;
		InitBinaryTree();
	}

	Type* GetRootNode() const
	{
		return m_pRootNode;
	}
	//初始化
	void InitBinaryTree()
	{
		Type* pTmpNode = m_pRootNode;
		for(int i=1;i<11;i++)
		{
			Type* pNode = new Type;
			pNode->m_nData = i;
label:		bool bRet = AddNode(pTmpNode,pNode,0);
			if(!bRet)//左节点添加失败则添加右节点
			{
				bRet = AddNode(pTmpNode,pNode,1);
			}
			if(!bRet)
			{
				pTmpNode = pTmpNode->m_pLeftNode;
				goto label;
			}
		}
	}
	//递归遍历二叉树
	void IterateBinaryTree(Type *pNode)
	{
		if(pNode!=NULL)
		{
			cout<<"节点数据:"<<pNode->m_nData<<endl;
		}
		if(pNode->m_pLeftNode!=NULL)
		{
			IterateBinaryTree(pNode->m_pLeftNode);
		}
		if(pNode->m_pRightNode!=NULL)
		{
			IterateBinaryTree(pNode->m_pRightNode);
		}
	}
	//添加节点
	bool AddNode(Type *pDestation,Type *pNode,int nFlag = 0)
	{
		if(pDestation!=NULL&&pNode!=NULL)
		{
			if(nFlag)
			{
				if(!pDestation->m_pRightNode)
				{
					pDestation->m_pRightNode = pNode;
				}
				else
				{
					return false;
				}
			}
			else
			{
				if(!pDestation->m_pLeftNode)
				{
					pDestation->m_pLeftNode = pNode;
				}
				else
				{
					return false;
				}
			}
			m_nNodeCount++;
			return true;
		}
		return false;
	}
	//销毁节点
	void DestroyBinaryTree(Type *pNode)
	{
		Type *pLeftNode,*pRightNode;
		if(pNode!=NULL)
		{
			pLeftNode = pNode->m_pLeftNode;
			pRightNode = pNode->m_pRightNode;
			delete pNode;
			pNode =NULL;
		}
		if(pLeftNode!=NULL)
		{
			DestroyBinaryTree(pLeftNode);
		}
		if(pRightNode!=NULL)
		{
			DestroyBinaryTree(pRightNode);
		}
	}
	//析构函数
	virtual ~CBinaryTree()
	{
		DestroyBinaryTree(m_pRootNode);
	}
};

class CNode
{
private:
	CNode *m_pLeftNode;
	CNode *m_pRightNode;
	int m_nData;
public:
	CNode()
	{
		m_pLeftNode = NULL;
		m_pRightNode = NULL;
		m_nData = 0;
	}

	friend class CBinaryTree<CNode>;

	virtual ~CNode()
	{
		m_pLeftNode = NULL;
		m_pRightNode = NULL;
		m_nData = 0;
	}
};

int main(int argc,char* argv[])
{
	CBinaryTree<CNode> BinaryTree;
	BinaryTree.IterateBinaryTree(BinaryTree.GetRootNode());
	return 0;
}

中序 :使用循环遍历二叉树,使用数据结构的栈来存入读出

#include<iostream.h>
#include<memory.h>

template<class Type>
class CStact
{
private:
	Type *m_pBottom;
	Type *m_pTop;
	int m_nStackSize;//栈大小
public:
	CStact()
	{
		m_pBottom = NULL;
		m_pTop = NULL;
		m_nStackSize = 30;
	}
	~CStact()
	{
		if(m_pBottom!=NULL)
		{
			m_pBottom++;
			delete [] m_pBottom;
		}
	}
	bool InitStack(int nStackSize)
	{
		m_nStackSize = nStackSize;
		try
		{
			m_pBottom = new Type[m_nStackSize];
			m_pBottom--;//落入栈底
			m_pTop = m_pBottom;//空栈
		}
		catch(...)
		{
			return false;
		}
		return true;
	}

	bool Push(Type *pNode)//入栈
	{
		if(m_pTop-m_pBottom>=m_nStackSize||pNode==NULL)
		{
			return false;
		}
		m_pTop++;//移动栈顶指针
		memcpy(m_pTop,pNode,sizeof(Type));
		return true;
	}

	bool Pop(Type *pNode)//出栈
	{
		if(m_pTop == m_pBottom)//空栈
		{
			return false;
		}
		memcpy(pNode,m_pTop,sizeof(Type));
		m_pTop--;
		return true;
	}

	bool GetTop(Type *pNode)
	{
		if(m_pTop == m_pBottom)//空栈
		{
			return false;
		}
		memcpy(pNode,m_pTop,sizeof(Type));
		return true;
	}

	bool IsEmpty()
	{
		return (m_pTop == m_pBottom);
	}
};


template <class Type>
class CBinaryTree
{
private:
	int m_nNodeCount;
	Type* m_pRootNode;//根节点
public:
	CBinaryTree()
	{
		m_pRootNode = new Type();
		m_nNodeCount = 1;
		InitBinaryTree();
	}

	Type* GetRootNode() const
	{
		return m_pRootNode;
	}
	//初始化
	void InitBinaryTree()
	{
		Type* pTmpNode = m_pRootNode;
		for(int i=1;i<11;i++)
		{
			Type* pNode = new Type;
			pNode->m_nData = i;
label:		bool bRet = AddNode(pTmpNode,pNode,0);
			if(!bRet)//左节点添加失败则添加右节点
			{
				bRet = AddNode(pTmpNode,pNode,1);
			}
			if(!bRet)
			{
				pTmpNode = pTmpNode->m_pLeftNode;
				goto label;
			}
		}
	}
	
	void LoopBinaryTree()
	{
		CStact<CNode> Stack;
		Stack.InitStack(m_nNodeCount);
		Stack.Push(m_pRootNode);
		Type *pNode = m_pRootNode;
		while(!Stack.IsEmpty())
		{
			if(pNode)
			{
				while(pNode)//遍历左子节点,直到尽头
				{
					Stack.Push(pNode->m_pLeftNode);//入栈
					pNode = pNode->m_pLeftNode;
				}
			}
			else
			{
				Type Node;
				bool bRet = Stack.Pop(&Node);//回退指针
				if(bRet)
				{
					cout<<"节点数据 : "<<Node.m_nData<<endl;
				}
				bRet = Stack.Pop(&Node);
				if(bRet)
				{
					cout<<"节点数据 : "<<Node.m_nData<<endl;
				}
				if(bRet&&Node.m_pRightNode!=NULL)
				{
					Stack.Push(Node.m_pRightNode);
					pNode = Node.m_pRightNode;
				}
			}
		}
	}

	//添加节点
	bool AddNode(Type *pDestation,Type *pNode,int nFlag = 0)
	{
		if(pDestation!=NULL&&pNode!=NULL)
		{
			if(nFlag)
			{
				if(!pDestation->m_pRightNode)
				{
					pDestation->m_pRightNode = pNode;
				}
				else
				{
					return false;
				}
			}
			else
			{
				if(!pDestation->m_pLeftNode)
				{
					pDestation->m_pLeftNode = pNode;
				}
				else
				{
					return false;
				}
			}
			m_nNodeCount++;
			return true;
		}
		return false;
	}

	//销毁节点
	void DestroyBinaryTree(Type *pNode)
	{
		Type *pLeftNode,*pRightNode;
		if(pNode!=NULL)
		{
			pLeftNode = pNode->m_pLeftNode;
			pRightNode = pNode->m_pRightNode;
			delete pNode;
			pNode = NULL;
		}
		if(pLeftNode!=NULL)
		{
			DestroyBinaryTree(pLeftNode);
		}
		if(pRightNode!=NULL)
		{
			DestroyBinaryTree(pRightNode);
		}
	}
	//析构函数
	virtual ~CBinaryTree()
	{
		DestroyBinaryTree(m_pRootNode);
	}

};

class CNode
{
private:
	CNode *m_pLeftNode;
	CNode *m_pRightNode;
	int m_nData;
public:
	CNode()
	{
		m_pLeftNode = NULL;
		m_pRightNode = NULL;
		m_nData = 0;
	}

	friend class CBinaryTree<CNode>;

	virtual ~CNode()
	{
		m_pLeftNode = NULL;
		m_pRightNode = NULL;
		m_nData = 0;
	}
};

int main(int argc,char* argv[])
{
	CBinaryTree<CNode> BinaryTree;
	BinaryTree.LoopBinaryTree();
	return 0;
}



本文转载自:http://blog.csdn.net/bq1073100909/article/details/41282245

共有 人打赏支持
指尖残雪
粉丝 7
博文 73
码字总数 0
作品 0
上海
后端工程师
LeetCode算法练习——深度优先搜索 DFS

更多干货就在我的个人博客 BlackBlog.tech 欢迎关注! 也可以关注我的csdn博客:黑哥的博客 谢谢大家! 网上大部分LeetCode的代码都没有给出注释和解释,对于新手学习很不方便。笔者在这里尽...

BlackBlog__
07/30
0
0
C语言/C++编程新手入门基础知识整理学习

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界
04/01
0
0
Java学习资料-Java常用算法-二叉树算法

二叉树算法的数据结构: 二叉树结点Node实现与c中的区别是,c中采用的是结构体,而java中是用类来实现,而在c++的教材中,类是一种自定义数据结构。 二叉树的leftchild和rightchild在c中是利...

晓阳
2015/01/28
0
0
面试常考的常用数据结构与算法【简】

数据结构与算法,这个部分的内容其实是十分的庞大,要想都覆盖到不太容易。在校学习阶段我们可能需要对每种结构,每种算法都学习,但是找工作笔试或者面试的时候,要在很短的时间内考察一个人...

anlve
05/01
0
0
C语言/C++编程学习数据结构与算法 通俗易懂讲解 快速排序

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界
03/20
0
0

没有更多内容

加载失败,请刷新页面

加载更多

django 2 urlpatterns 中正则匹配路由

django 2 urlpatterns 中正则匹配路由: 在项目的urls.py中导入re_path:

MichaelShu
16分钟前
0
0
Spring MVC 到 Spring Boot 的简化之路

背景 从Servlet技术到Spring和Spring MVC,开发Web应用变得越来越简捷。但是Spring和Spring MVC的众多配置有时却让人望而却步,相信有过Spring MVC开发经验的朋友能深刻体会到这一痛苦。因为...

别打我会飞
22分钟前
0
0
python做文本内容指定区域字符串替换

需求: 因为公司项目需要做SEO优化,所以对项目中的各种长连接做优化,比如本文中提到的精简路径;之前已经批量吧文本的路径名字等做过修改,这里不再赘述;这里的问题是外部的路径修改了,文...

坦途abc
47分钟前
4
0
MySQL 关键字模糊匹配,并按照匹配度排序

MySQL 关键字模糊匹配,并按照匹配度排序。 方式一、按照关键字搜索,然后根据关键字所占比例排序 SELECTdrug_name,pinyinFROMtbl_drugWHEREpinyin LIKE '%AM%'ORDER BY...

yh32
57分钟前
3
0
虚拟机学习之一:java内存区域与内存溢出异常

1.运行时数据区域 java虚拟机在执行java程序的过程中会把它所管理的内存划分为若干个不同的数据区域。这些区域都有各自的用途和创建、销毁时间,有的区域伴随虚拟机进程的启动而存在,有些区...

贾峰uk
57分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部