数据结构项目——二叉树实现

数据结构项目——二叉树实现案例分析:写出下面二叉树的先、中、后序遍历输出的结果:注:先自己推算,然后用程序验算。先序遍历的结果:A F H D C B J G E I K中序遍历的结果:D H C F J B G A I E K后序遍历的结果:D C H J G B F I K E A代码如下:#include “pch.h”#include &…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

案例分析:

写出下面二叉树的先、中、后序遍历输出的结果:
注:先自己推算,然后用程序验算。

在这里插入图片描述
先序遍历的结果:A F H D C B J G E I K
中序遍历的结果:D H C F J B G A I E K
后序遍历的结果:D C H J G B F I K E A

代码如下:

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

int top = -1;
typedef struct Bitnode
{ 
   
	char data;
	Bitnode *lchild, *rchild;
}Bitnode,*bittree;

//创建一个二叉树
void Createbittree(bittree *t)
{ 
   
	*t =(Bitnode *) malloc(sizeof(Bitnode));
	(*t)->data = 'A';
	(*t)->lchild= (Bitnode *)malloc(sizeof(Bitnode));
	(*t)->rchild =(Bitnode *)malloc(sizeof(Bitnode));
	(*t)->lchild->data = 'F';
	(*t)->rchild->data = 'E';
	(*t)->lchild->lchild = (Bitnode *)malloc(sizeof(Bitnode));
	(*t)->lchild->rchild = (Bitnode *)malloc(sizeof(Bitnode));
	(*t)->rchild->lchild = (Bitnode *)malloc(sizeof(Bitnode));
	(*t)->rchild->rchild = (Bitnode *)malloc(sizeof(Bitnode));
	(*t)->lchild->lchild->data = 'H';
	(*t)->lchild->rchild->data = 'B';
	(*t)->rchild->lchild->data = 'I';
	(*t)->rchild->rchild->data = 'K';
	(*t)->rchild->lchild->lchild= NULL;
	(*t)->rchild->lchild->rchild= NULL;
	(*t)->rchild->rchild->lchild = NULL;
	(*t)->rchild->rchild->rchild = NULL;
	(*t)->lchild->lchild->lchild = (Bitnode *)malloc(sizeof(Bitnode));
	(*t)->lchild->lchild->lchild->lchild = NULL;
	(*t)->lchild->lchild->lchild->rchild = NULL;
	(*t)->lchild->lchild->rchild = (Bitnode *)malloc(sizeof(Bitnode));
	(*t)->lchild->lchild->rchild->lchild = NULL;
	(*t)->lchild->lchild->rchild->rchild = NULL;
	(*t)->lchild->rchild->lchild = (Bitnode *)malloc(sizeof(Bitnode));
	(*t)->lchild->rchild->lchild->lchild = NULL;
	(*t)->lchild->rchild->lchild->rchild = NULL;
	(*t)->lchild->rchild->rchild = (Bitnode *)malloc(sizeof(Bitnode));
	(*t)->lchild->rchild->rchild->lchild = NULL;
	(*t)->lchild->rchild->rchild->rchild = NULL;
	(*t)->lchild->lchild->lchild->data = 'D';
	(*t)->lchild->lchild->rchild->data = 'C';
	(*t)->lchild->rchild->lchild->data = 'J';
	(*t)->lchild->rchild->rchild->data = 'G';
}
//先序遍历入栈
void Push(Bitnode **a,Bitnode *elem)
{ 
   
	a[++top] = elem;
}
//先序遍历出栈
void Pop()
{ 
   
	if (top==-1)
	{ 
   
		return;
	}
	top--;
}
//获取栈顶元素
Bitnode *Get_top(Bitnode**a)
{ 
   
	return a[top];
}
//输出节点数据
void Printelem(Bitnode *elem)
{ 
   
	cout << elem->data << " ";
}
//实现先序遍历算法
void preorder(Bitnode*tree)
{ 
   
	Bitnode *a[30];
	Bitnode *p;
	Push(a, tree);
	while (top!=-1)
	{ 
   
		p = Get_top(a);
		Pop();
		while (p)
		 { 
   
			Printelem(p);
			if (p->rchild)
			{ 
   
				Push(a,p->rchild);
			}
			p = p->lchild;
		}
	}
}
//中序遍历二叉树
void inorder(bittree tree)
{ 
   
	Bitnode *a[30];	//定义一个顺序栈
	Bitnode *p;		//临时指针
	Push(a, tree);	//根节点入栈
	while (top != -1)	//top!=-1来判定栈是否为空
	{ 
   
		while ((p=Get_top(a))&&p)//获取栈顶元素不为空
		{ 
   
			//左子树节点入栈,如果没有,null入栈
			Push(a, p->lchild);
		}
		Pop();//跳出循环,栈顶元素是空,
		if (top!=-1)
		{ 
   
			p = Get_top(a);//获取栈顶元素
			Pop();
			Printelem(p);
			Push(a,p->rchild);//右子树节点入栈
		}
	}
}



//二叉树后序遍历(非递归法)
struct Snode
{ 
   
	bittree p;
	int tag;
};
//后序遍历的入栈函数
void PostPush(Snode*a, Snode sdata)
{ 
   
	a[++top] = sdata;
}
//后序遍历
void PostOrder(bittree tree)
{ 
   
	Snode a[20];
	Bitnode*p;		//节点指针
	int tag;
	Snode sdata;
	p = tree;
	while (p||top!=-1)//用的或,这两种都行
	{ 
   
		while (p)
		{ 
   
			sdata.p = p;
			sdata.tag = 0;//遍历左子树,设置标记位为0
			PostPush(a, sdata);//入栈
			p = p->lchild;//以该节点为根节点,遍历左子树
		}
		sdata=a[top];
		Pop();
		p = sdata.p;
		tag = sdata.tag;

		if (tag==0)//条件为真,左子树遍历完成,该节点需要遍历右子树
		{ 
   
			sdata.p = p;
			sdata.tag = 1;
			PostPush(a, sdata);//更改节点标志位,重新入栈
			p = p->rchild;//将该节点的右子树设置为根节点,重新循环

		}
		else
		{ 
   
			Printelem(p);
			p = NULL;
		}
	}
}
int main()
{ 
   
	bittree tree;
	Createbittree(&tree);
	cout << "先序遍历的结果为:";
	preorder(tree);
	cout << endl;
	cout << "中序遍历的结果为:";
	inorder(tree);
	cout << endl;
	cout << "后序遍历的结果为:";
	PostOrder(tree);
	cout << endl;
	return 0;
}

结果为:
在这里插入图片描述

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/170980.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • activiti 事件监听_js监听事件和处理事件

    activiti 事件监听_js监听事件和处理事件本文个人博客地址:Activiti7事件监听(leafage.top)好久没有记录笔记了,最近做了一些关于工作流的事情,记录一下使用activiti7的一些经验。需求:在流程发起和流程操作的过程中,给相关人员发送流程审批的通知提醒;不要在配置流程时手动添加,不能侵入到流程操作的过程,影响流程执行;这个怎么入手呢?没搞过activiti,activiti7的官方文档写的跟屎一样烂,感觉好难呀????…文档参考性不高,那就试试看官方的示例,找到activiti的repositor

  • leetcode-50Pow(x, n)(快速幂)

    leetcode-50Pow(x, n)(快速幂)实现 pow(x, n) ,即计算 x 的 n 次幂函数(即,xn)。示例 1:输入:x = 2.00000, n = 10输出:1024.00000示例 2:输入:x = 2.10000, n = 3输出:9.26100示例 3:输入:x = 2.00000, n = -2输出:0.25000解释:2-2 = 1/22 = 1/4 = 0.25 提示:-100.0 < x < 100.0-231 <= n <= 231-1-104 <=

  • cnpm 安装命令

    cnpm 安装命令  npm包管理器是每一位js开发者的得力助手,利用npm我们不仅能下载到别人写好的组件,也可以快速搭建我们的项目……但对于国内的开发者,npm的下载速度有是实在是令人捉鸡,因此国内的许多开发者都会使用更加快速的cnpm简单代替npm。打开控制台,输入命令npminstall-gcnpm–registry=https://registry.npm.taobao.org耐心等待一下安装即可此后我们再使用npm下载包的时候,就可以将npm命令替换为cnpm,下载下来的内容完全一样,但是速度

    2022年10月15日
  • Vue(5)计算属性computed

    Vue(5)计算属性computed前言一般情况下属性都是放到data中的,但是有些属性可能是需要经过一些逻辑计算后才能得出来,那么我们可以把这类属性变成计算属性。比如以下:<divid="example&quot

  • 利用JS跨域做一个简单的页面訪问统计系统

    利用JS跨域做一个简单的页面訪问统计系统

  • idea激活码2021分享【2021.10最新】

    (idea激活码2021分享)最近有小伙伴私信我,问我这边有没有免费的intellijIdea的激活码,然后我将全栈君台教程分享给他了。激活成功之后他一直表示感谢,哈哈~https://javaforall.cn/100143.htmlIntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,上面是详细链接哦~1STL…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号