数据结构 - (4)简单二叉树插入及输出

HanaKoo 2023-03-28 原文

一、概念

二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树，且有左右之分。

二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个节点

二、完整代码

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

/*声明结点*/
typedef struct Node {
	int val;
	struct Node* lchild, * rchild;
}Node;


/*声明树*/
typedef struct Tree {
	int* root;
	int n;
}Tree;


/*初始化新结点*/
Node* getNewNode(int val) {
	Node* node = (Node*)malloc(sizeof(Node));
	node->val = val;
	node->lchild = node->rchild = NULL;
	return node;
}

/*初始化新树*/
Tree *getNewTree() {
	Tree* tree = (Tree*)malloc(sizeof(Tree));
	tree->n = 0;
	tree->root = NULL;
	return tree;
}


/*二叉排序树 插值法 （插入成功：ret = 1,否则：ret=0） [递归] */
Node *insertNode(Node *root,int val,int *ret) {
	if (root == NULL) {
		*ret = 1;
		/*初始化一个新结点，将结点插入树*/
		return getNewNode(val);
	}
	/*如果值相等，返回原树*/
	if (root->val == val)return root;
	/*左小右大*/
	if (root->val > val) {
		root->lchild = insertNode(root->lchild, val,ret);
	}
	else {
		root->rchild = insertNode(root->rchild, val,ret);
	}
	/*左小右大插完后，返回树结点(易遗漏)*/
	return root;
}


void insert(Tree* tree,int val) {
	if (tree == NULL)return;
	/*flag判断是否插入成功(0:失败，1:成功)*/
	int flag = 0;
	/*注意：插入节点后接收返回的树节点*/
	tree->root = insertNode(tree->root,val,&flag);//
	/*节点数+1*/
	tree->n += flag;
	return;
}


/*递归输出结点值 【广义表输出】*/
void outputNode(Node *root) {
	if (root == NULL)return;
	/*先输出根节点的数值*/
	printf("%d", root->val);
	/*判断并递归到左右子树，输出值*/
	if (root->lchild == NULL && root->rchild == NULL)return;
	printf("(");
	outputNode(root->lchild);
	printf(",");
	outputNode(root->rchild);
	printf(")");
}

/*输出树(调用输出结点)*/
void outputTree(Tree *tree) {
	if (tree == NULL)return;
	printf("tree(%d):", tree->n);
	outputNode(tree->root);
	printf("\n");
}

/*清除树结点*/
void clearNode(Node* node) {
	if (node == NULL)return;
	free(node->lchild);
	free(node->rchild);
	free(node);
	return;
}

/*清除树*/
void clearTree(Tree* tree) {
	if (tree == NULL)return;
	clearNode(tree->root);
	free(tree);
	return;
}


/// ////////////////////////////////前序遍历/////////////////////////

/*用了递归，并且要注意Node处判空操作*/
void preorderNode(Node* node) {
	if (node == NULL) return;
	printf("%d ", node->val);
	preorderNode(node->lchild);
	preorderNode(node->rchild);
	return;
}

void preorder(Tree *tree) {
	printf("pre order : ");
	preorderNode(tree->root);
	printf("\n");
	return;
}

////////////////////////////////////中序遍历/////////////////////////
void inorderNode(Node* node) {
	if (node == NULL) return;
	inorderNode(node->lchild);
	printf("%d ", node->val);
	inorderNode(node->rchild);
	return;
}

void inorder(Tree *tree) {
	printf("in order : ");
	inorderNode(tree->root);
	printf("\n");
	return;
}


/// ////////////////////////////////后序遍历/////////////////////////
void postorderNode(Node* node) {
	if (node == NULL) return;
	postorderNode(node->lchild);
	postorderNode(node->rchild);
	printf("%d ", node->val);
	return;
}

void postorder(Tree *tree) {
	printf("post order : ");
	postorderNode(tree->root);
	printf("\n");
	return;
}


int main()
{
	srand(time(0));
	/*先声明一个树*/
	Tree* tree = getNewTree();
	for (int i = 0; i < 10; i++) {
		int val = rand() % 100;
		insert(tree,val);
		/*每插入一个值，打印一次*/
		outputTree(tree);
	}
	printf("\n");
	preorder(tree);
	inorder(tree);
	postorder(tree);
	clearTree(tree);
	return 0;
}

三、分块理解

引入头文件，定义结点和数的数据类型

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

/*声明结点*/
typedef struct Node {
	int val;
	struct Node* lchild, * rchild;
}Node;


/*声明树*/
typedef struct Tree {
	int* root;
	int n;
}Tree;

初始化新结点和树（结点包含值和左右子树，数则存放根节点及节点数量）

/*初始化新结点*/
Node* getNewNode(int val) {
	Node* node = (Node*)malloc(sizeof(Node));
	node->val = val;
	node->lchild = node->rchild = NULL;
	return node;
}

/*初始化新树*/
Tree *getNewTree() {
	Tree* tree = (Tree*)malloc(sizeof(Tree));
	tree->n = 0;
	tree->root = NULL;
	return tree;
}

定义插入二叉树的方法（向二叉树内插入数值，采用左小右大的插入方法 [二叉搜索树]）这里需要用到递归，务必认真

/*二叉排序树 插值法 （插入成功：ret = 1,否则：ret=0） [递归] */
Node *insertNode(Node *root,int val,int *ret) {
	if (root == NULL) {
		*ret = 1;
		/*初始化一个新结点，将结点插入树*/
		return getNewNode(val);
	}
	/*如果值相等，返回原树*/
	if (root->val == val)return root;
	/*左小右大*/
	if (root->val > val) {
		root->lchild = insertNode(root->lchild, val,ret);
	}
	else {
		root->rchild = insertNode(root->rchild, val,ret);
	}
	/*左小右大插完后，返回树结点(易遗漏)*/
	return root;
}


void insert(Tree* tree,int val) {
	if (tree == NULL)return;
	/*flag判断是否插入成功(0:失败，1:成功)*/
	int flag = 0;
	/*注意：插入节点后接收返回的树节点*/
	tree->root = insertNode(tree->root,val,&flag);//
	/*节点数+1*/
	tree->n += flag;
	return;
}

通过递归将树打印出，同样需要细心

/*递归输出结点值 【广义表输出】*/
void outputNode(Node *root) {
	if (root == NULL)return;
	/*先输出根节点的数值*/
	printf("%d", root->val);
	/*判断并递归到左右子树，输出值*/
	if (root->lchild == NULL && root->rchild == NULL)return;
	printf("(");
	outputNode(root->lchild);
	printf(",");
	outputNode(root->rchild);
	printf(")");
}

/*输出树(调用输出结点)*/
void outputTree(Tree *tree) {
	if (tree == NULL)return;
	printf("tree(%d):", tree->n);
	outputNode(tree->root);
	printf("\n");
}

定义清除树的方法

/*清除树结点*/
void clearNode(Node* node) {
	if (node == NULL)return;
	free(node->lchild);
	free(node->rchild);
	free(node);
	return;
}

/*清除树*/
void clearTree(Tree* tree) {
	if (tree == NULL)return;
	clearNode(tree->root);
	free(tree);
	return;
}

前、中、后序遍历


/// ////////////////////////////////前序遍历/////////////////////////

/*用了递归，并且要注意Node处判空操作*/
void preorderNode(Node* node) {
	if (node == NULL) return;
	printf("%d ", node->val);
	preorderNode(node->lchild);
	preorderNode(node->rchild);
	return;
}

void preorder(Tree *tree) {
	printf("pre order : ");
	preorderNode(tree->root);
	printf("\n");
	return;
}

////////////////////////////////////中序遍历/////////////////////////
void inorderNode(Node* node) {
	if (node == NULL) return;
	inorderNode(node->lchild);
	printf("%d ", node->val);
	inorderNode(node->rchild);
	return;
}

void inorder(Tree *tree) {
	printf("in order : ");
	inorderNode(tree->root);
	printf("\n");
	return;
}


/// ////////////////////////////////后序遍历/////////////////////////
void postorderNode(Node* node) {
	if (node == NULL) return;
	postorderNode(node->lchild);
	postorderNode(node->rchild);
	printf("%d ", node->val);
	return;
}

void postorder(Tree *tree) {
	printf("post order : ");
	postorderNode(tree->root);
	printf("\n");
	return;
}

主函数：随机对树进行10次插值操作，再调用前中后序遍历，清空二叉树

int main()
{
	srand(time(0));
	/*先声明一个树*/
	Tree* tree = getNewTree();
	for (int i = 0; i < 10; i++) {
		int val = rand() % 100;
		insert(tree,val);
		/*每插入一个值，打印一次*/
		outputTree(tree);
	}
	printf("\n");
	preorder(tree);
	inorder(tree);
	postorder(tree);
	clearTree(tree);
	return 0;
}

数据结构数据 tree return root 算法与数据结构

有关数据结构 - (4)简单二叉树插入及输出的更多相关文章

ruby - 使用 ruby 将 HTML 转换为纯文本并维护结构/格式 - 2
我想将html转换为纯文本。不过，我不想只删除标签，我想智能地保留尽可能多的格式。为插入换行符标签，检测段落并格式化它们等。输入非常简单，通常是格式良好的html(不是整个文档，只是一堆内容，通常没有anchor或图像)。我可以将几个正则表达式放在一起，让我达到80%，但我认为可能有一些现有的解决方案更智能。最佳答案首先，不要尝试为此使用正则表达式。很有可能你会想出一个脆弱/脆弱的解决方案，它会随着HTML的变化而崩溃，或者很难管理和维护。您可以使用Nokogiri快速解析HTML并提取文本:require'nokogiri'h
ruby - 解析 RDFa、微数据等的最佳方式是什么，使用统一的模式/词汇(例如 schema.org)存储和显示信息 - 2
我主要使用Ruby来执行此操作，但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式，例如使用这个yaml文件，它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i
ruby - 检查 "command"的输出应该包含 NilClass 的意外崩溃 - 2
为了将Cucumber用于命令行脚本，我按照提供的说明安装了arubagem。它在我的Gemfile中，我可以验证是否安装了正确的版本并且我已经包含了require'aruba/cucumber'在'features/env.rb'中为了确保它能正常工作，我写了以下场景:@announceScenario:Testingcucumber/arubaGivenablankslateThentheoutputfrom"ls-la"shouldcontain"drw"假设事情应该失败。它确实失败了，但失败的原因是错误的:@announceScenario:Testingcucumber/ar
ruby - 通过 erb 模板输出 ruby 数组 - 2
我正在使用puppet为ruby程序提供一组常量。我需要提供一组主机名，我的程序将对其进行迭代。在我之前使用的bash脚本中，我只是将它作为一个puppet变量hosts=>"host1,host2"我将其提供给bash脚本作为HOSTS=显然这对ruby不太适用——我需要它的格式hosts=["host1","host2"]自从phosts和putsmy_array.inspect提供输出["host1","host2"]我希望使用其中之一。不幸的是，我终其一生都无法弄清楚如何让它发挥作用。我尝试了以下各项:我发现某处他们指出我需要在函数调用前放置“function_”……这
ruby - 如何进行排列以有效地定制输出 - 2
这是一道面试题，我没有答对，但还是很好奇怎么解。你有N个人的大家庭，分别是1,2,3,...,N岁。你想给你的大家庭拍张照片。所有的家庭成员都排成一排。“我是家里的friend，建议家庭成员安排如下:”1岁的家庭成员坐在这一排的最左边。每两个坐在一起的家庭成员的年龄相差不得超过2岁。输入:整数N，1≤N≤55。输出:摄影师可以拍摄的照片数量。示例->输入:4，输出:4符合条件的数组:[1,2,3,4][1,2,4,3][1,3,2,4][1,3,4,2]另一个例子:输入:5输出:6符合条件的数组:[1,2,3,4,5][1,2,3,5,4][1,2,4,3,5][1,2,4,5,3][
ruby - 简单获取法拉第超时 - 2
有没有办法在这个简单的get方法中添加超时选项？我正在使用法拉第3.3。Faraday.get(url)四处寻找，我只能先发起连接后应用超时选项，然后应用超时选项。或者有什么简单的方法？这就是我现在正在做的:conn=Faraday.newresponse=conn.getdo|req|req.urlurlreq.options.timeout=2#2secondsend 最佳答案试试这个:conn=Faraday.newdo|conn|conn.options.timeout=20endresponse=conn.get(url
ruby - Ruby 有 `Pair` 数据类型吗？ - 2
有时我需要处理键/值数据。我不喜欢使用数组，因为它们在大小上没有限制(很容易不小心添加超过2个项目，而且您最终需要稍后验证大小)。此外，0和1的索引变成了魔数(MagicNumber)，并且在传达含义方面做得很差(“当我说0时，我的意思是head...”)。散列也不合适，因为可能会不小心添加额外的条目。我写了下面的类来解决这个问题:classPairattr_accessor:head,:taildefinitialize(h,t)@head,@tail=h,tendend它工作得很好并且解决了问题，但我很想知道:Ruby标准库是否已经带有这样一个类？最佳
ruby - 用 Ruby 编写一个简单的网络服务器 - 2
我想在Ruby中创建一个用于开发目的的极其简单的Web服务器(不，不想使用现成的解决方案)。代码如下:#!/usr/bin/rubyrequire'socket'server=TCPServer.new('127.0.0.1',8080)whileconnection=server.acceptheaders=[]length=0whileline=connection.getsheaders想法是从命令行运行这个脚本，提供另一个脚本，它将在其标准输入上获取请求，并在其标准输出上返回完整的响应。到目前为止一切顺利，但事实证明这真的很脆弱，因为它在第二个请求上中断并出现错误:/usr/b
ruby-on-rails - 简单的 Ruby on Rails 问题——如何将评论附加到用户和文章？ - 2
我意识到这可能是一个非常基本的问题，但我现在已经花了几天时间回过头来解决这个问题，但出于某种原因，Google就是没有帮助我。(我认为部分问题在于我是一个初学者，我不知道该问什么......)我也看过O'Reilly的RubyCookbook和RailsAPI，但我仍然停留在这个问题上.我找到了一些关于多态关系的信息，但它似乎不是我需要的(尽管如果我错了请告诉我)。我正在尝试调整MichaelHartl'stutorial创建一个包含用户、文章和评论的博客应用程序(不使用脚手架)。我希望评论既属于用户又属于文章。我的主要问题是:我不知道如何将当前文章的ID放入评论Controller。
ruby - 是否有用于序列化和反序列化各种格式的对象层次结构的模式？ - 2
给定一个复杂的对象层次结构，幸运的是它不包含循环引用，我如何实现支持各种格式的序列化？我不是来讨论实际实现的。相反，我正在寻找可能会派上用场的设计模式提示。更准确地说:我正在使用Ruby，我想解析XML和JSON数据以构建复杂的对象层次结构。此外，应该可以将该层次结构序列化为JSON、XML和可能的HTML。我可以为此使用Builder模式吗？在任何提到的情况下，我都有某种结构化数据-无论是在内存中还是文本中-我想用它来构建其他东西。我认为将序列化逻辑与实际业务逻辑分开会很好，这样我以后就可以轻松支持多种XML格式。最佳答案我最

数据结构 - (4)简单二叉树 插入及输出

一、概念

二、完整代码

三、分块理解

有关数据结构 - (4)简单二叉树 插入及输出的更多相关文章

随机推荐

数据结构 - (4)简单二叉树插入及输出

有关数据结构 - (4)简单二叉树插入及输出的更多相关文章