二叉树的链式存储和顺序存储对比

举报
肥学 发表于 2022/05/07 00:58:03 2022/05/07
【摘要】 目录标题 顺序存储需要注意的是 链式存储值得注意的是 点击直接资料领取 顺序存储 需要注意的是 对于节点个数为n的二叉树,在顺序存储的时候对于位置为i的节点 i...

顺序存储

在这里插入图片描述

需要注意的是

对于节点个数为n的二叉树,在顺序存储的时候对于位置为i的节点

  • i的左孩子为2i
  • i的右孩子为2i+1
  • i的父节点为(i/2)向下取整

特别的如果这棵树是完全二叉树那就爽了又多了几个可以用的条件

  • 当i<=(n/2)向下取整 为分支节点
  • 当i>(n/2)向下取整 为叶子节点
#include<stdio.h>

#define SIZE 100

typedef struct Node {
	int data;
	bool isEmpty=true;
}ListNode,*n;

int main() {

	ListNode listNode[SIZE];
	for (int i = 1; i < 20; i++) {
		Node node = { i,false };
		listNode[i] = node;
		
	}

	printf("取节点序号为5的左右孩子\n");
	printf("左节点为:%d\n", listNode[5 * 2].data);
	printf("右节点为:%d\n", listNode[5 * 2+1].data);

	return 0;
}

  
 

链式存储

在这里插入图片描述

值得注意的是

  • 存在n+1个空链域
#include<stdio.h>
#include<malloc.h>
#include<queue>
using namespace std;

typedef struct Node {
	int data;
	Node* leftchild;
	Node* rightchild;
}BiTNode,*BiTree ;
//广度优先初始化二叉树,图像和上面图片一样
void order(BiTree head) {
	queue<BiTree> q;
	BiTree node = (BiTree)malloc(sizeof(BiTree));
	q.push(head);
	int i = 2;
	while (i <16) {
		BiTree lnode = (BiTree)malloc(sizeof(BiTree));
		lnode->data = i;
		lnode->leftchild = NULL;
		lnode->rightchild = NULL;
		i++;
		BiTree rnode = (BiTree)malloc(sizeof(BiTree));
		rnode->data = i;
		rnode->leftchild = NULL;
		rnode->rightchild = NULL;
		i++;
		q.front()->leftchild = lnode;
		q.front()->rightchild = rnode;
		q.pop();
		q.push(lnode);
		q.push(rnode);
	}

}

//先序遍历该二叉树
void preOrder(BiTree temphead) {
	if (!temphead)
		return;
	printf("%d ", temphead->data);
	preOrder(temphead->leftchild);
	preOrder(temphead->rightchild);

}
int main() {

	BiTree head = (BiTree)malloc(sizeof(BiTNode));
	head->data = 1;
	order(head);
	//先序遍历试试看验证一下
	BiTree temphead = head;
	preOrder(temphead);
}

  
 

点击直接资料领取

如果你在学习python或者Java哪怕是C遇到问题都可以来给我留言,因为在学习初期新手总会走很多弯路,这个时候如果没有有个人来帮一把的话很容易就放弃了。身边很多这样的例子许多人学着学着就转了专业换了方向,不仅是自身问题还是没有正确的学习。所以作为一个过来人我希望有问题给我留言,说不上是帮助就是顺手敲几行字的事情。

这里有python,Java学习资料还有有有趣好玩的编程项目,更有难寻的各种资源。反正看看也不亏。

文章来源: blog.csdn.net,作者:肥学,版权归原作者所有,如需转载,请联系作者。

原文链接:blog.csdn.net/jiahuiandxuehui/article/details/124581357

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。