文档章节

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

没有更多内容

加载失败,请刷新页面

加载更多

下一页

day63-20180821-流利阅读笔记-待学习

性别歧视在日本:“我是女生,所以社会不让我学医” 毛西 2018-08-21 1.今日导读 大家在看病的时候,有留意过女医生的比例吗?在性别歧视现象十分严重的日本,男医生和女医生的比例达到了惊人...

aibinxiao
45分钟前
2
0
Ubuntu18.04 显卡GF-940MX安装NVIDIA-390.77

解决办法: 下面就给大家一个正确的姿势在Ubuntu上安装Nvidia驱动: (a)首先去N卡官网下载自己显卡对应的驱动:www.geforce.cn/drivers (b)下载后好放在英文路径的目录下,怎么简单怎么来...

AI_SKI
今天
4
0
深夜胡思乱想

魔兽世界 最近魔兽世界出了新版本, 周末两天升到了满级,比之前的版本体验好很多,做任务不用抢怪了,不用组队打怪也是共享拾取的。技能简化了很多,哪个亮按哪个。 运维 服务器 产品 之间的...

Firxiao
今天
1
0
MySQL 8 在 Windows 下安装及使用

MySQL 8 带来了全新的体验,比如支持 NoSQL、JSON 等,拥有比 MySQL 5.7 两倍以上的性能提升。本文讲解如何在 Windows 下安装 MySQL 8,以及基本的 MySQL 用法。 下载 下载地址 https://dev....

waylau
今天
1
0
微信第三方平台 access_token is invalid or not latest

微信第三方开发平台code换session_key说的特别容易,但是我一使用就带来无穷无尽的烦恼,搞了一整天也无济于事. 现在记录一下解决问题的过程,方便后来人参考. 我遇到的这个问题搜索了整个网络也...

自由的开源
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部