文档章节

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

指尖残雪
 指尖残雪
发布于 2016/05/22 23:56
字数 736
阅读 3
收藏 0
点赞 2
评论 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;
}



© 著作权归作者所有

共有 人打赏支持
指尖残雪
粉丝 7
博文 73
码字总数 0
作品 0
上海
后端工程师
C语言/C++编程新手入门基础知识整理学习

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

小辰带你看世界 ⋅ 04/01 ⋅ 0

面试常考的常用数据结构与算法【简】

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

anlve ⋅ 05/01 ⋅ 0

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

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

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

二叉树创建与遍历,递归和非递归实现

title: 二叉树最大的权值和 date: 2017-09-16 09:32:32 category: 默认分类 本文介绍 二叉树最大的权值和 二叉树最大的权值和 本文由在当地较为英俊的男子金天大神原创,版权所有,欢迎转载,...

Nicholas_Jela ⋅ 2017/09/18 ⋅ 0

二叉树常见面试题

树是一种比较重要的数据结构,尤其是二叉树。二叉树是一种特殊的树,在二叉树中每个节点最多有两个子节点,一般称为左子节点和右子节点(或左孩子和右孩子),并且二叉树的子树有左右之分,其...

笨拙的小Q ⋅ 2016/09/22 ⋅ 0

数据结构基础(16) --树与二叉树

树的基本术语 1.结点:{数据元素+若干指向子树的分支} 2.结点的度:分支的个数(子树的个数) 3.树的度:树中所有结点的度的最大值 4.叶子结点:度为零的结点 5.分支结点:度大于零的结点(包含根和...

翡青 ⋅ 2015/01/11 ⋅ 0

Java学习资料-Java常用算法-二叉树算法

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

晓阳 ⋅ 2015/01/28 ⋅ 0

Tommy Yang/BinaryTree

二叉树(Binary Tree)定义: 二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。 二...

Tommy Yang ⋅ 2017/03/31 ⋅ 0

12.遍历二叉树与二叉树的建立

一、遍历二叉树 1.定义 二叉树的遍历(travering binary tree)是指从根结点出发。依照某种次序依次訪问二叉树中的全部结点,使得每一个结点被訪问一次且仅被訪问一次。 2.前序遍历 (1)规则:若...

技术mix呢 ⋅ 2017/12/01 ⋅ 0

非递归遍历二叉树的四种策略-先序、中序、后序和层序

遍历二叉树的递归算法,是比较容易理解的,但是非递归的循环算法不是很容易一眼看穿。下面的五个算法是参考严蔚敏的《数据结构》和USTC的张昱老师的讲义后,写下来的,部分有改动。 先序遍历...

晨曦之光 ⋅ 2012/04/24 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Spring MVC基本概念

只写Controller

颖伙虫 ⋅ 12分钟前 ⋅ 0

微软重金收购GitHub的背后逻辑原来是这样的

全球最大的开发者社区GitHub网站花落谁家的问题已经敲定,微软最终以75亿美元迎娶了这位在外界看来无比“神秘”的小家碧玉。尽管此事已过去一些时日,但整个开发者世界,包括全球各地的开源社...

linux-tao ⋅ 13分钟前 ⋅ 0

磁盘管理—逻辑卷lvm

4.10-4.12 lvm 操作流程: 磁盘分区-->创建物理卷-->划分为卷组-->划分成逻辑卷-->格式化、挂载-->扩容。 磁盘分区 注: 创建分区时需要更改其文件类型为lvm(代码8e) 分区 3 已设置为 Linu...

弓正 ⋅ 33分钟前 ⋅ 0

Spring源码解析(六)——实例创建(上)

前言 经过前期所有的准备工作,Spring已经获取到需要创建实例的 beanName 和对应创建所需要信息 BeanDefinition,接下来就是实例创建的过程,由于该过程涉及到大量源码,所以将分为多个章节进...

MarvelCode ⋅ 53分钟前 ⋅ 0

js模拟栈和队列

栈和队列 栈:LIFO(先进后出)一种数据结构 队列:LILO(先进先出)一种数据结构 使用的js方法 1.push();可以接收任意数量的参数,把它们逐个推进队尾(数组末尾),并返回修改后的数组长度。 2....

LIAOJIN1 ⋅ 今天 ⋅ 0

180619-Yaml文件语法及读写小结

Yaml文件小结 Yaml文件有自己独立的语法,常用作配置文件使用,相比较于xml和json而言,减少很多不必要的标签或者括号,阅读也更加清晰简单;本篇主要介绍下YAML文件的基本语法,以及如何在J...

小灰灰Blog ⋅ 今天 ⋅ 0

IEC60870-5-104规约传送原因

1:周期循环2:背景扫描3:自发4:初始化5:请求6:激活7:激活确认8:停止激活9:停止激活确认10:激活结束11:远程命令引起的返送信息12:当地命令引起的返送信息13:文件传送20:响应总召...

始终初心 ⋅ 今天 ⋅ 0

【图文经典版】冒泡排序

1、可视化排序过程 对{ 6, 5, 3, 1, 8, 7, 2, 4 }进行冒泡排序的可视化动态过程如下 2、代码实现    public void contextLoads() {// 冒泡排序int[] a = { 6, 5, 3, 1, 8, 7, 2, ...

pocher ⋅ 今天 ⋅ 0

ORA-12537 TNS-12560 TNS-00530 ora-609解决

oracle 11g不能连接,卡住,ORA-12537 TNS-12560 TNS-00530 TNS-12502 tns-12505 ora-609 Windows Error: 54: Unknown error 解决方案。 今天折腾了一下午,为了查这个问题。。找了N多方案,...

lanybass ⋅ 今天 ⋅ 0

IDEA反向映射Mybatis

1.首先在pom文件的plugins中添加maven对mybatis-generator插件的支持 ` <!-- mybatis逆向工程 --><plugin><groupId>org.mybatis.generator</groupId><artifactId>mybatis-generator-ma......

lichengyou20 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部