首页 / 算法 / 树---二叉树(进阶)

树---二叉树(进阶)

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了树---二叉树(进阶)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2837字，纯文字阅读大概需要5分钟。

内容图文

文章目录

前言

二叉树的进阶内容

一、二叉树的存储

1、顺序存储

说白了，就是数组存储。不多说，直接上图：
树---二叉树(进阶) - 文章图片这个是一颗完全二叉树，可以发现如果按照层序编号，编号即数组下标，就会发现一个规律：左儿子 = 父节点 ×2；右节点=父节点×2 +1 ；
树---二叉树(进阶) - 文章图片

这样的话，就可以利用这一下标变换，表达一个节点的父节点和左右子节点，很方便、快捷。
缺点在于：很浪费空间。刚才上面特意提到了“完全二叉树”，就是除了叶节点最下面一层，上面所有层必须都满，这样才能保证数组空间的充分利用。
然而一旦遇到非完全二叉树，这种就会显得很浪费空间。
树---二叉树(进阶) - 文章图片 所以既然都提到了存储方式，就自然引出了链表。

2、链表存储：二叉链表

之前学习链表都是一个数据域、一个指针域。 就是单纯的线性形状。
这次的二叉树，很明显我们需要两个指针，左儿子、右儿子。
树---二叉树(进阶) - 文章图片
这样所形成的图形就是二叉的样子：
树---二叉树(进阶) - 文章图片

示例：pandas 是基于NumPy 的一种工具，该工具是为了解决数据分析任务而创建的。
代码：

typedef int ElemType;

typedef struct BinTree{
	ElemType data;//都默认结构体数组数据域为0 
	struct BinTree *LeftSon,*RightSon;
}BinTree;

二、二叉树的遍历

之前只学习了线性的数组、单链表的时候，遍历这个概念基本上是很简单的：从头至尾走一遍 就完事了。
但是二叉树不再是简单的线性关系，那么遍历的顺序肯定就不唯一，根据不同的规则走完所有节点，就有了不同遍历法则。

1.前序遍历

先访问根节点，然后前序遍历左子树，再前序遍历右子树

树---二叉树(进阶) - 文章图片这是前序遍历顺序，其实这里很容易联想到深度优先搜索，一直搜到最底层再一步步返回。这个对我而言最好理解

2、中序遍历

若树为空，则空操作返回，否则从根节点开始（注意并不是先访问根节点），中序遍历根节点的左子树，然后访问根节点，最后中序遍历右子树

树---二叉树(进阶) - 文章图片这里的意思差不多是：
先走到最左边（没有左子就找右子），然后根，再右子树。这样一个优先级。

代码如下（示例）：

data = pd.read_csv(
    'https://labfile.oss.aliyuncs.com/courses/1283/adult.data.csv')
print(data.head())

3、后序遍历

规则是若树为空，则空操作返回，否则从左到右先叶子后节点的方式遍历左、右子树，最后回根节点。

树---二叉树(进阶) - 文章图片

4、层序遍历

这个就是很好理解的，按照之前存放在数组的顺序一个个遍历，一层一层地走，比如第一层的根节点，然后第二层的2、3节点；再然后的第三层的4、5、6、7节点，从上到下、从左往右。非常友好

树---二叉树(进阶) - 文章图片输出结果就是ABCDEFGHI

5、代码实现：

除去层序遍历，其他的三种顺序遍历都有代码，而且代码非常清晰的体现出了各自的特色。

void PreOrderTravel()
{
   if(T==NULL)
     return ;
     
   printf("%c",T->data);
   PreOrderTravel(T->left);
   PreOrderTravel(T->right);
}

这个是前序的代码，可以很明显的看出，先打印当前的节点，然后进入左儿子，利用了递归的思想。
而中序、后续的代码就很形象。

void MidOrderTravel()
{
   if(T==NULL)
     return ;
     
   MidOrderTravel(T->left);
    printf("%c",T->data);
   MidOrderTravel(T->right);
}

void LastOrderTravel()
{
   if(T==NULL)
     return ;
     
   LastOrderTravel(T->left);
   LastOrderTravel(T->right);
   printf("%c",T->data);
}

很明显发现，X序就是printf访问的地方

总结

提示：这里对文章进行总结：
例如：以上就是今天要讲的内容，本文仅仅简单介绍了pandas的使用，而pandas提供了大量能使我们快速便捷地处理数据的函数和方法。

内容总结

以上是互联网集市为您收集整理的树---二叉树(进阶)全部内容，希望文章能够帮你解决树---二叉树(进阶)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

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

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1011501.html

来源：【匿名】