二叉树的存储方式、遍历、构建、判定

这篇具有很好参考价值的文章主要介绍了二叉树的存储方式、遍历、构建、判定。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

树的定义

二叉树的定义

二叉树的存储表示

二叉树的创建和前中后序遍历

通过中序遍历和先序遍历来构建树

通过后序遍历加先序遍历构建树

链式存储的树 将其中序遍历

非递归后序遍历

非递归后序遍历第二种方法

非递归中序遍历

非递归前序遍历

层次遍历

求二叉树节点个数

求二叉树深度

判断一个数是不是满二叉树

判断一个数是不是完全二叉树


树的定义

树是由n个结点组成的有限集合,如果 n=0 ,称为空树,如果n>0则

1、有一个特定的称之为根(root)的结点,它只有直接后继,但没有直接前驱;

2、除根以外的其他结点划分为m(m>=0)个互不交互的有限集合,每个集合又是一棵树,称为子树。每个子树的根节点只有一个直接前驱。

节点的度:一个节点含有的子树的个数

树的度:最大节点的度称为树的度

叶节点:度为零的节点

分支节点:度不为零

兄弟节点:含有相同父节点的节点

节点的层次:从根开始定义起,根为第一层,根的子节点为第二层

深度:对于任意节点n,n的深度为从根到n的唯一路径长,根的深度为0;

二叉树的定义

一棵二叉树是结点的一个有限集合,是由一个根节点加上两颗分别称为左子树和右子树的、互不相交的二叉树组成。

二叉树的性质:

每一个结点最多有两个子结点

高度为k的二叉树节点数最多为2的k+1次方-1

满二叉树:

每一层都达到了结点的最大个数

完全二叉树:

高度为h的树,共有h+1层,除h层以外,都达到最大个数,第h层从右向左连续缺若干结点,这就是完全二叉树。

二叉树的存储表示

顺序存储:当从0下标开始时,左孩子:i*2+1 右孩子:i*2+2 父节点:(i-1)/2 

假设只有右孩子 就会导致很多下标处没有数据 太浪费空间 所以存在第二种存储方式,一般只有完全二叉树才用数组存放

链式存储 :分为二叉链表和三叉,区别是结构体里有没有parent指针 便于回溯文章来源地址https://www.toymoban.com/news/detail-446763.html

二叉树的创建和前中后序遍历

typedef char Elemtype;
typedef struct BtNode
{
	struct BtNode* leftchild;
	struct BtNode* rightchild;
	Elemtype data;
}BtNode,*BinartTree;

void InOrder(BtNode* ptr)//中序遍历
{
	if (ptr == NULL) { return; }
	InOrder(ptr->leftchild);
	cout << ptr->data << endl;
	InOrder(ptr->rightchild);
}
void PreOrder(BtNode* ptr)//先序遍历
{
	if (ptr == NULL) { return; }
	cout << ptr->data << endl;
	PreOrder(ptr->leftchild);
	PreOrder(ptr->rightchild);
}
void PastOrder(BtNode* ptr)//后序遍历
{
	if (ptr == NULL) { return; }
	PastOrder(ptr->leftchild);
	PastOrder(ptr->rightchild);
	cout << ptr->data << endl;
}
BtNode* BuyNode()
{
	BtNode* ptr = (BtNode*)malloc(sizeof(BtNode));
	if (ptr == nullptr)exit(1);
	memset(ptr, 0, sizeof(BtNode));
	return ptr;

}
BtNode* CreatTree(const char*& str)
{
	if (str == nullptr && strlen(str) <= 0) { return nullptr; }
	BtNode* s = nullptr;
	if (*str != '#') {
		s = BuyNode();
		s->data = *str;
		s->leftchild = CreatTree(++str);
		s->rightchild = CreatTree(++str);
	}
	return s;
}
int main()
{
	const char* str = "ABC##DE##F##G#H##";
	BinartTree  root = CreatTree(str);
	PastOrder(root);
	PreOrder(root);
	InOrder(root);
	return 0;
}

通过中序遍历和先序遍历来构建树

int Findpos(const char* ptr, int n, char first)
{
	int pos = -1;
	for (int i = 0; i < n; i++)
	{
		if (ptr[i] == first) { pos = i;  break; }
	}
	return pos;
}
BtNode* CreateBTreePI(const char* str, const char* ptr, int n)
{
	BtNode* s = nullptr;
	if (n > 0) 
	{
		s = BuyNode();
		s->data = str[0];
		int pos = Findpos(ptr, n, str[0]);
		if (pos == -1) { exit(1); }
		s->leftchild = CreateBTreePI(str+1, ptr, pos);
		s->rightchild = CreateBTreePI(str+pos+1, ptr+pos+1, n-pos-1);
	}
		return s;
}
BtNode* CreatBinartTreePI(const char* str, const char* ptr)
{
	int n = strlen(str);
	int m = strlen(ptr);
	if (nullptr == ptr || nullptr == str || n < 1 || m < 1 || n != m) { return nullptr; }
	else { return CreateBTreePI(str, ptr,n); }
}

int main()
{
	const char* str = "ABCDEFGH";
	const char* ptr = "CBEDFAGH";
	BinartTree  root = CreatBinartTreePI(str, ptr);
	return 0;
}

通过后序遍历加先序遍历构建树

int Findpos(const char* ptr, int n, char first)
{
	int pos = -1;
	for (int i = 0; i < n; i++)
	{
		if (ptr[i] == first) { pos = i;  break; }
	}
	return pos;
}
BtNode* CreateBTreePL(const char* ptr, const char* ltr, int n)
{
	BtNode* s = nullptr;
	if (n > 0)
	{
		s = BuyNode();
		s->data = ltr[n-1];
		int pos = Findpos(ptr, n, ltr[n-1]);
		if (pos == -1) { exit(1); }
		s->leftchild = CreateBTreePL(ptr, ltr, pos);
		s->rightchild = CreateBTreePL(ptr + pos+1 , ltr + pos, n - pos - 1);
	}
		return s;
}
BtNode* CreatBinartTreePL(const char* ptr, const char* ltr)
{
	int n = strlen(ptr);
	int m = strlen(ltr);
	if (nullptr == ptr || nullptr == ltr || n < 1 || m < 1 || n != m) { return nullptr; }
	else { return CreateBTreePL(ptr, ltr, n); }
}

int main()
{
	const char* str = "ABCDEFGH";
	const char* ptr = "CBEDFAGH";
	const char* ltr = "CEFDBHGA";
	BinartTree  root = CreatBinartTreePL(ptr, ltr);
	return 0;
}

链式存储的树 将其中序遍历

void InOrder_Ar(const int* ar, int n, int i)
{
	if (i < n) {
		InOrder_Ar(ar, n, i * 2 + 1);
		if (ar[i] != -1)
		{
			cout << ar[i] << " ";
		}
		InOrder_Ar(ar, n, i * 2 + 2);
	}
}
int main()
{
	int ar[] = { 31,23,12,66,-1,5,17,70,62,-1,-1,-1,88,-1,55 };
	int n = sizeof(ar) / sizeof(ar[0]);
	InOrder_Ar(ar, n, 0);


	return 0;
}

非递归后序遍历

if (nullptr == ptr) { return; }
	stack<BtNode*> st;
	BtNode* tag = nullptr;
	while (!st.empty() || ptr != nullptr) {
		while (ptr != nullptr)
		{
			st.push(ptr);
			ptr = ptr->leftchild;
		}
		ptr = st.top();
		st.pop();
		if (ptr->rightchild == nullptr || ptr->rightchild == tag)
		{
			cout << ptr->data << " ";
			tag = ptr;
			ptr = nullptr;
		}
		else
		{
			st.push(ptr);
			ptr = ptr->rightchild;
		}
	}

非递归后序遍历第二种方法

struct StkNode
{
	BtNode* Pnode;
	int popnum;
};

void NicePastOrder_2(BtNode* ptr)
{
	if (ptr == nullptr) { return; }
	stack<StkNode>st;
	st.push(StkNode{ ptr,0 });
	while (!st.empty())
	{
		StkNode node = st.top(); st.pop();
		if (++node.popnum == 3)
		{
			cout << node.Pnode->data << " ";
		}
		else
		{
			st.push(node);
			if (node.popnum == 1 &&node.Pnode->leftchild != nullptr)
			{
				st.push(StkNode{ node.Pnode->leftchild,0 });
			}
			else if(node.popnum == 2 &&node.Pnode->rightchild!=nullptr)
			{
				st.push(StkNode{ node.Pnode->rightchild,0 });
			}
		}
	}
	cout << endl;
}

非递归中序遍历

void NiceInOrder(BtNode* ptr)
{
	if (nullptr == ptr) {return;}
	stack<BtNode*> st;
	while (!st.empty() || ptr != nullptr) {
		while (ptr != nullptr)
		{
			st.push(ptr);
			ptr = ptr->leftchild;
		}
		ptr = st.top();
		st.pop();
		cout << ptr->data << " ";
		ptr = ptr->rightchild;
	}
}

非递归前序遍历

void NicePerOrder(BtNode* ptr)
{
	if (nullptr == ptr) { return; }
	stack<BtNode*>st;
	st.push(ptr);
	while (!st.empty())
	{
		ptr = st.top();
		st.pop();
		cout << ptr->data << " ";
		if (ptr->rightchild != nullptr)
		{
			st.push(ptr->rightchild);
		}
		if(ptr->leftchild!= nullptr)
		{
			st.push(ptr->leftchild);
		}
	}
	cout << endl;

}

层次遍历

void LevelOrder(BtNode* ptr)
{
	if (ptr == nullptr)return;
	queue<BtNode*> qu;
	qu.push(ptr);
	while (!qu.empty())
	{
		ptr = qu.front();
		qu.pop();
		cout << ptr->data << " ";
		if (ptr->leftchild != nullptr)
		{
			qu.push(ptr->leftchild);
		}
		if (ptr->rightchild != nullptr)
		{
			qu.push(ptr->rightchild);
		}
	}
	cout << endl;
}

求二叉树节点个数

int GetSize(BtNode *ptr)
{
	if (ptr == nullptr) {
		return 0;
	}
	return GetSize(ptr->leftchild) + GetSize(ptr->rightchild) + 1;
}

求二叉树深度

int Max(const int a, const int b)
{
	return a > b ? a : b;
}
int GetDepth(BtNode* ptr)
{
	if (ptr == nullptr) {
		return 0;
	}
	return Max(GetDepth(ptr->leftchild) , GetDepth(ptr->rightchild))+1;
}

判断一个数是不是满二叉树

bool IfFullBinartTree(BtNode* ptr)
{
	bool ret = true;
	if (ptr == nullptr)return ret;
	queue<BtNode*>qua;
	queue<BtNode*>qub;
	int i = 0;
	int n = 1;
	qua.push(ptr);
	while (!qua.empty() || !qub.empty())
	{
		for (; i < n && !qua.empty(); i++)
		{
			ptr = qua.front(); qua.pop();
			if (ptr->leftchild != nullptr)
			{
				qub.push(ptr->leftchild);
			}
			if (ptr->rightchild != nullptr)
			{
				qub.push(ptr->rightchild);
			}
		}
		if (i < n)
		{
			ret == false;
			break;
		}
		if (qub.empty())break;
		n += n;
		for (i = 0; i < n && !qub.empty(); i++)
		{
			ptr = qub.front(); qub.pop();
			if (ptr->leftchild != nullptr)
			{
				qua.push(ptr->leftchild);
			}
			if (ptr->rightchild != nullptr)
			{
				qua.push(ptr->rightchild);
			}
		}
		if (i < n)
		{
			ret = false;
			break;
		}
		if (qua.empty())break;
		n += n;
	}
	return ret;
}

判断一个数是不是完全二叉树

bool isfull(BtNode* ptr)
{
	bool ret = true;
	if (ptr != nullptr)return 0;
	queue<BtNode*>qu1;
	qu1.push(ptr);
	while (!qu1.empty())
	{
		ptr = qu1.front(); qu1.pop();
		if (ptr == nullptr)break;
		qu1.push(ptr->leftchild);
		qu1.push(ptr->rightchild);
	}
	while (!qu1.empty())
	{
		if (qu1.front() != nullptr) {
			ret = false;
			break;
		}
		qu1.pop();
	}
	return ret;
}

到了这里,关于二叉树的存储方式、遍历、构建、判定的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 根据二叉树的先序、中序、后序遍历构建二叉树-图文详解

    引言:根据一颗二叉树,可以得出他的先序、中序、后序三种遍历方式,那么如果我们知道了他的前序、中序、后序遍历,如何绘制出这颗二叉树呢? 特性A,对于前序遍历,第⼀个肯定是根节点; 特性B,对于后序遍历,最后⼀个肯定是根节点; 特性C,利⽤前序或后序遍历

    2024年02月06日
    浏览(45)
  • 【数据结构之二叉树的构建和遍历】

    前言: 前篇学习了 数据结构之树和二叉树的基本概念知识,那么这篇继续完善二叉树的相关知识并完成实现二叉树的构建和遍历的内容。 / 知识点汇总 / 因为前篇已经非常详细的单独学习了数和二叉树的基本知识概念,那么这里就简单回顾一下即可。 概念 : 二叉树(Bina

    2024年02月21日
    浏览(47)
  • 数据结构——二叉树的创建与遍历(链式存储结构)

    二叉树(binary tree)是指树中节点的度不大于2的有序树,它是一种最简单且最重要的树。二叉树的递归定义为:二叉树是一棵空树,或者是一棵由一个根节点和两棵互不相交的,分别称作根的左子树和右子树组成的非空树;左子树和右子树又同样都是二叉树。以下是对链式存

    2024年02月05日
    浏览(51)
  • 数据结构:图文详解 树与二叉树(树与二叉树的概念和性质,存储,遍历)

    目录 一.树的概念 二.树中重要的概念 三.二叉树的概念 满二叉树 完全二叉树 四.二叉树的性质 五.二叉树的存储 六.二叉树的遍历 前序遍历 中序遍历  后序遍历  树是一种 非线性数据结构 ,它由节点和边组成。树的每个节点可以有零个或多个子节点,其中一个节点被指定为

    2024年02月04日
    浏览(49)
  • 按照前序遍历创建二叉树及树的四种遍历方式

    一.二叉树的介绍         二叉树的特点是二叉树的每个结点的度都不大于2,可以视为每个结点都有左孩子和右孩子。故二叉树结点的数据结构为   二.二叉树的特点     1.设根结点所在的层数为第1层,则第i层最多有个结点。     2.深度为k的二叉树最多有个结点。    

    2024年02月04日
    浏览(38)
  • 【数据结构】前中后层序遍历 --二叉树的结构特点与遍历方式

      Halo,这里是Ppeua。平时主要更新C语言,C++,数据结构算法......感兴趣就关注我吧!你定不会失望。 🌈个人主页:主页链接 🌈算法专栏:专栏链接       我会一直往里填充内容哒! 🌈LeetCode专栏:专栏链接       目前在刷初级算法的LeetBook 。若每日一题当中有力所能

    2023年04月09日
    浏览(85)
  • 【数据结构】树与森林(树的存储结构、森林与二叉树的转化、树与森林的遍历)

    树与二叉树知识点文章: 【数据结构】树与二叉树(递归法先序、中序、后序、层次遍历二叉树、二叉树的建立以及求树高的方法) 二叉树遍历算法的应用: 【数据结构】树与二叉树遍历算法的应用(求叶子节点个数、求树高、复制二叉树、创建二叉树、二叉树存放表达式、

    2024年04月13日
    浏览(38)
  • 数据结构|二叉树的三种遍历方式,你掌握了几种?

    目录 1、遍历方式 2、前序遍历 3、中序遍历 学习二叉树的结构,最简单的方式就是遍历二叉树。遍历二叉树就是 通过某条线路对二叉树的各个结点进行一次访问 ,访问的方法有三种分为前序遍历、中序遍历、后续遍历,层序遍历它们的遍历顺序如下所示: 前序遍历: 根节点

    2023年04月16日
    浏览(49)
  • 【数据结构】16 二叉树的定义,性质,存储结构(以及先序、后序、中序遍历)

    一个二叉树是一个有穷的结点集合。 它是由根节点和称为其左子树和右子树的两个不相交的二叉树组成的。 二叉树可具有以下5种形态。 一个二叉树第i层的最大结点数为 2 i − 1 2^{i-1} 2 i − 1 , i ≥ 1 i geq 1 i ≥ 1 每层最大结点可以对应完美二叉树(满二叉树),其所有分支结

    2024年02月20日
    浏览(45)
  • Java 数据结构篇-二叉树的深度优先遍历(实现:递归方式、非递归方式)

    🔥博客主页: 【 小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍    文章目录         1.0 二叉树的说明         1.1 二叉树的实现         2.0 二叉树的优先遍历说明         3.0 用递归方式实现二叉树遍历         3.1 用递归方式实现遍历 - 前序遍历         3.2 用递归

    2024年02月05日
    浏览(53)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包