首页 > 其他分享 >数据结构-------------二叉树后续(单链表实现二叉树)

数据结构-------------二叉树后续(单链表实现二叉树)

时间：2024-10-27 22:20:33浏览次数：6  
标签：单链 Trnode right ------------- 二叉树 return NULL root left

1:前中后序遍历 在用链表实现二叉树的时候我们要首先了解一下二叉树的遍历，让我们来看一下二叉树都有那些遍历 1.1  遍历规则 按照二叉树的遍历规则遍历有:前序.中序.后序。 (1)前序:首先访问根节点再去访问左右子树( 访 问顺序为：根结点、左⼦树、右⼦树) 例如上图：前序遍历：是A B D NULL NULL NULL C E NULL NULL F NULL NULL. (2)中序: 访问根结点的操作发⽣在遍历其左右⼦树之中( 访问顺序为：左⼦树、根结点、右⼦树 ) 例如上图:  中序遍历： NULL D NULL B NULL A NULL E NULL C NULL F NULL (3)后序: 访问根结点的操作发⽣在遍历其左右⼦树之后( 左⼦树、右⼦树、根结点 ) 例如上图：后续遍历： NULL NULL D NULL B NULL NULL E NULL NULL F C A  掌握这些规则后接下来我们来实现以下代码： 2:实现链式结构⼆叉树 用链表来表示二叉树，就是链表来表示元素的逻辑关系，和单链表的组成其实差不多二叉树里面要保函两个指针一个指向左子树一个指向右子树定义如下、 

typedef char TrDatatype;

typedef struct Treenode {
	TrDatatype data;
	struct Treenode* left;
	struct Treenode* right;

}Trnode;

前面提到了遍历方式那么我们如何用代码来实现前中后序列遍历呢？我们要首先手动构造一个二叉树如下。让各个结点指向该有的位置。

Trnode* buynode(TrDatatype x){
	Trnode* node = (Trnode*)malloc(sizeof(Trnode));
	node->data = x;
	node->left = node->right = NULL;

	return node;
}

Trnode *creadnode()
{
	Trnode*NodeA = buynode('A');
	Trnode*NodeB = buynode('B');
	Trnode*NodeC = buynode('C');
	Trnode*NodeD = buynode('D');
	Trnode*NodeE = buynode('E');
	Trnode*NodeF = buynode('F');
	NodeA->left = NodeB;
	NodeA->right = NodeC;
	NodeB->left = NodeD;
	NodeC->left = NodeE;
	NodeC->right = NodeF;
	return NodeA;
}

void test()
{
	Trnode* tree= creadnode();
}
根结点的左⼦树和右⼦树分别⼜是由⼦树结点、⼦树结点的左⼦树、⼦树结点的右⼦树组成的，因此 ⼆叉树定义是递归式的,后序链式⼆叉树的操作中基本都是按照该概念实现的。首先我们来实现前序遍历： 
void preorder(Trnode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%c ", root->data);
	preorder(root->left);
	preorder(root->right);
}

首先我们要先判断根是否为空为空或就打印NULL然后return 如果不为空我们就要打印根节点的值然后走到根结点的右字数然后因为右子树也是一个根节点我们也需要判断是否为空如果不为空继续打印然后继续重复操作直到最后一个为空然后依次返回，这个时候左子树遍历完了我们需要去递归的来遍历右边的字数所以继续走到遍历右边的代码直到结束可以根据下面流程图来看一下

中序：因为中序首先要遍历左节点所以要遍历遍历左节点然后就紧跟着打印数据

void Inorder(Trnode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	Inorder(root->left);
	printf("%c ", root->data);
	Inorder(root->right);
}

后序：因为这个要先遍历子树再去遍历根所以要先遍历再去打印

void Postorder(Trnode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	Postorder(root->left);
	Postorder(root->right);
	printf("%c ", root->data);
}

//二叉树的结点个数

首先判断跟根是否为空然后再去递归。

int treesize(Trnode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return 1 + treesize(root->left) + treesize(root->right);
}

// ⼆叉树叶⼦结点个数

首先要判断叶子结点，叶子的结点的特征是左右子节点都为空所以直接判断两个都为空就是叶子结点

int treeleafsize(Trnode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	return treeleafsize(root->left) + treeleafsize(root->right);
}

// ⼆叉树第k层结点个数

当k为1就说是根节点这个结点，然后每次递归的时候让k减一。

int brandtreesize(Trnode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return brandtreesize(root->left,k-1) + brandtreesize(root->right,k-1);
}

//⼆叉树的深度/⾼度

在我们要代码实现实现深度的时候，我们只要判断左右子节点那边的深度最深就可以了例如下图

两个都是度为三的二叉树我们第二个我们只需要去遍历右子结点的深度就可以实现

int treedepth(Trnode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int leftdep = treedepth(root->left);
	int rightdep = treedepth(root->right);
	return  1+(leftdep>rightdep?leftdep:rightdep);
}

// ⼆叉树查找值为x的结点

我们在查找值的时候可以先遍历左边的然后左边没找都的情况下再去遍历右边的这样完全没有必要挨个遍历。

Trnode* brandtreefind(Trnode* root, TrDatatype x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}
	 Trnode	*lefrnode= brandtreefind(root->left, x);
	 if(lefrnode)
	 return lefrnode;
	 Trnode* rightnode = brandtreefind(root->right, x);
	 if (rightnode)
	 {
		 return rightnode;
	 }

//二叉树销毁

void treedestory(Trnode* root)
{
	if (root == NULL)
	{
		return;
	}
	treedestory(root->left);
	treedestory(root->right);
	free(root);
}

下面放上总体代码

Tree.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>

typedef char TrDatatype;

typedef struct Treenode {
	TrDatatype data;
	struct Treenode* left;
	struct Treenode* right;

}Trnode;
//前序遍历
void preorder(Trnode *root);
//中序遍历
void Inorder(Trnode* root);
//后续遍历
void Postorder(Trnode* root);
//二叉树的结点个数
int treesize(Trnode *root);
// ⼆叉树叶⼦结点个数
int treeleafsize(Trnode* root);
// ⼆叉树第k层结点个数
int brandtreesize(Trnode* root,int k);
//⼆叉树的深度/⾼度
int treedepth(Trnode* root);
// ⼆叉树查找值为x的结点
Trnode* brandtreefind(Trnode* root, TrDatatype x);
// ⼆叉树销毁
void treedestory(Trnode* root);

Tree.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Tree.h"
void preorder(Trnode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%c ", root->data);
	preorder(root->left);
	preorder(root->right);
}
void Inorder(Trnode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	Inorder(root->left);
	printf("%c ", root->data);
	Inorder(root->right);
}
void Postorder(Trnode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	Postorder(root->left);
	Postorder(root->right);
	printf("%c ", root->data);
}

int treesize(Trnode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return 1 + treesize(root->left) + treesize(root->right);
}
int treeleafsize(Trnode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	return treeleafsize(root->left) + treeleafsize(root->right);
}

int brandtreesize(Trnode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return brandtreesize(root->left,k-1) + brandtreesize(root->right,k-1);
}


int treedepth(Trnode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int leftdep = treedepth(root->left);
	int rightdep = treedepth(root->right);
	return  1+(leftdep>rightdep?leftdep:rightdep);
}

Trnode* brandtreefind(Trnode* root, TrDatatype x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}
	 Trnode	*lefrnode= brandtreefind(root->left, x);
	 if(lefrnode)
	 return lefrnode;
	 Trnode* rightnode = brandtreefind(root->right, x);
	 if (rightnode)
	 {
		 return rightnode;
	 }
	 return NULL;
}

void treedestory(Trnode* root)
{
	if (root == NULL)
	{
		return;
	}
	treedestory(root->left);
	treedestory(root->right);
	free(root);
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Tree.h"

Trnode* buynode(TrDatatype x){
	Trnode* node = (Trnode*)malloc(sizeof(Trnode));
	node->data = x;
	node->left = node->right = NULL;

	return node;
}

Trnode *creadnode()
{
	Trnode*NodeA = buynode('A');
	Trnode*NodeB = buynode('B');
	Trnode*NodeC = buynode('C');
	Trnode*NodeD = buynode('D');
	Trnode*NodeE = buynode('E');
	Trnode*NodeF = buynode('F');
	NodeA->left = NodeB;
	NodeA->right = NodeC;
	NodeB->left = NodeD;
	NodeC->left = NodeE;
	NodeC->right = NodeF;
	return NodeA;
}

void test()
{
	Trnode* tree= creadnode();
	/*preorder(tree);*/
	/*Inorder(tree);*/
	Postorder(tree);
	int size = treesize(tree);
	printf(" size:%d\n", size);
	printf(" size:%d\n", size);
	printf("leafsize:%d \n", treeleafsize(tree));
	printf("klevelsize:%d \n", brandtreesize(tree, 2));
	printf("kleveldepth:%d \n", treedepth(tree));
	Trnode *node= brandtreefind(tree, 'A');
	if (node == NULL)
	{
		printf("没找到\n");
	}
	else
	{
		printf("找到了\n");
	}
	treedestory(tree);
}

int main()
{
	test();
}

谢谢大家如果有不对的地方望指正

标签：单链,Trnode,right,-------------,二叉树,return,NULL,root,left
From： https://blog.csdn.net/qwer55588/article/details/143273300

相关文章

  • 鸿蒙NEXT开发-应用数据持久化之用户首选项（基于最新api12稳定版）
    注意：博主有个鸿蒙专栏，里面从上到下有关于鸿蒙next的教学文档，大家感兴趣可以学习下如果大家觉得博主文章写的好的话，可以点下关注，博主会一直更新鸿蒙next相关知识专栏地址:https://blog.csdn.net/qq_56760790/category_12794123.html目录1.应用数据持久化2.应用数据持久......
  • 7-7 求n以内最大的k个素数以及它们的和
    嵌套循环7-7求n以内最大的k个素数以及它们的和题目解答#include<stdio.h>intmain(){intn,k;inta[5000]={0};intc=0;//计数器，后面与k比较scanf("%d%d",&n,&k);intsum=0;for(inti=n;i>1;i--)//从n开始向前遍历{......
  • CSP-S 2024 游记/题解
    CSP-S2024去年S打成屎了，我要蓝√！！！！！！！！CSP怎么能不CS？CS了一个上午，顺便背了下快读。进厂！看见了退役的同学在做志愿者，祝他未来可期吧。也希望自己能够超常发挥。垃圾鼠标真难用。很好，全是传统题。只有T2开了两秒。T1，这不排个序然后优先队列乱搞就好了。5min过了，NOIP我来......
  • 图书进销存管理系统-登录页面-c#
    <Windowx:Class="Book.LoginWindow"xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"xmlns:d="http://schemas.microsoft.com......
  • 视野修炼-技术周刊第107期 | 2024 CSS 现状
    欢迎来到第107期的【视野修炼-技术周刊】，下面是本期的精选内容简介......
  • ctfshow(171,172，173)--SQL注入--联合注入
    Web171进入靶场，是一个SQL查询界面：审计：查询语句如下：$sql="selectusername,passwordfromuserwhereusername!='flag'andid='".$_GET['id']."'limit1;";语句功能从数据表user中查询username,password两个字段。查询条件是username!='fla......
  • 手撕单例模式懒汉式-饿汉式以及volatile双重检验锁
    设计----单例模式饿汉式和懒汉式区别懒汉式--资源用的时候才分配---可通过synchronized关键字实现线程安全可使用双重检验锁---懒汉式的方式实现publicclassSingleton{privatevolatilestaticSingletonuniqueInstance;privateSingleton(){}......
  • 3D数学基础：图形和游戏开发（第二版）--读书笔记（1）
    简介：本书是关于3D数学、三维空间的几何和代数的入门教材。它旨在告诉你如何使用数学描述三维中的物体及其位置、方向和轨迹。这不是一本关于计算机图形学、模拟，甚至计算几何的书，但是，如果读者打算研究这些科目，那么肯定需要这里的信息。这是一本适宜视频游戏程序开发人员阅读的图......
  • IT软件部落-Emoji表情字符大全增强你的表达能力-记事本也可以有情感，总有一个您用得上，
    这是手绘的吗？不，它是Emoji表情字符，就是普通的文本，你不相信？ ......
  • 2024-2025-1 20241329 《计算机基础与程序设计》第五周学习总结
    作业信息作业归属课程：https://edu.cnblogs.com/campus/besti/2024-2025-1-CFAP作业要求：https://www.cnblogs.com/rocedu/p/9577842.html#WEEK05作业目标：Pep/9虚拟机、机器语言与汇编语言、算法与伪代码、测试：黑盒，白盒作业正文：https://www.cnblogs.com/incamellia/p/18508448......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99