数据结构-二叉树-蓝桥杯

小咪咪 2023-09-24 17:27 6阅读 0赞

# **一、二叉树的性质** #

![ab45f09702f44f33b9abd9398df29440.png][]

# **二、满二叉树、完全二叉树** #

![4b5ab5898ed74dedbf89454b83792b7b.png][]

# **三、平衡二叉树** #

![1499576bcfdc43b2bf80a59e3d2678ac.png][]

# **四、不平衡二叉树** #

![69d07ffac20d48919db4f8bb91b9c6bb.png][]

# **五、二叉树的存储** #

## **1.普通做法** ##

普通做法:二叉树的一个节点，包括结点的值，以及指向左右子节点的指针。

![103f3f7334ce47bbb1012dbfb55a59b2.png][]

## **2.竞赛做法** ##

![2a6d717d49f946ab88f0d33ce92248f8.png][]

# **六、二叉树的遍历** #

## **1.宽度优先遍历** ##

![c04089a744a34169bf306e50031ae766.png][]

## **2.深度优先遍历** ##

![b772aefc8fbd4265af9cfe32c0751bdc.png][]

## **3.先(根)序遍历** ##

![7ebce3c0c737445b9af8e171cc61cf64.png][]

## **4.中(根)序遍历** ##

![b8c0c09a3b9d4c15af8d15491f0e90e5.png][]

### **中(根)序遍历的特点** ###

![b9d3efdfd43e4fa3b950a788960fa55d.png][]

## **5.后(根)序遍历** ##

![a09c3b94d1664d03a1ad21937a160154.png][]

## **6.三种遍历的关系** ##

![856e7cdaeeca428692ad6e8962d5f1c1.png][]

# **七、例题: 完全二叉树的权值** #

![c2cec8ce74224ef3b7013f70c9adecbe.png][]

![d7a7145ad53941089f413b550e91229d.png][]

# **八、例题:FBI树** #

![a3a9febb3b9a4cbd8c5cb0a39576b9ea.png][]

## **1.简介** ##

![a557021c524a4d84884abc04f1cd93b2.png][]

## **2.普通做法** ##

节点用数据结构表示，用1、r分别指向左右子节点

![2b7766e6444e4ad6a53b63b62a36626c.png][]

## **3.竞赛做法** ##

用一维数组存二叉树

![c24f930617664dd49a1f8e0f87e9e33e.png][]

[ab45f09702f44f33b9abd9398df29440.png]: https://img-blog.csdnimg.cn/img_convert/ab45f09702f44f33b9abd9398df29440.png
[4b5ab5898ed74dedbf89454b83792b7b.png]: https://img-blog.csdnimg.cn/img_convert/4b5ab5898ed74dedbf89454b83792b7b.png
[1499576bcfdc43b2bf80a59e3d2678ac.png]: https://img-blog.csdnimg.cn/img_convert/1499576bcfdc43b2bf80a59e3d2678ac.png
[69d07ffac20d48919db4f8bb91b9c6bb.png]: https://img-blog.csdnimg.cn/img_convert/69d07ffac20d48919db4f8bb91b9c6bb.png
[103f3f7334ce47bbb1012dbfb55a59b2.png]: https://img-blog.csdnimg.cn/img_convert/103f3f7334ce47bbb1012dbfb55a59b2.png
[2a6d717d49f946ab88f0d33ce92248f8.png]: https://img-blog.csdnimg.cn/img_convert/2a6d717d49f946ab88f0d33ce92248f8.png
[c04089a744a34169bf306e50031ae766.png]: https://img-blog.csdnimg.cn/img_convert/c04089a744a34169bf306e50031ae766.png
[b772aefc8fbd4265af9cfe32c0751bdc.png]: https://img-blog.csdnimg.cn/img_convert/b772aefc8fbd4265af9cfe32c0751bdc.png
[7ebce3c0c737445b9af8e171cc61cf64.png]: https://img-blog.csdnimg.cn/img_convert/7ebce3c0c737445b9af8e171cc61cf64.png
[b8c0c09a3b9d4c15af8d15491f0e90e5.png]: https://img-blog.csdnimg.cn/img_convert/b8c0c09a3b9d4c15af8d15491f0e90e5.png
[b9d3efdfd43e4fa3b950a788960fa55d.png]: https://img-blog.csdnimg.cn/img_convert/b9d3efdfd43e4fa3b950a788960fa55d.png
[a09c3b94d1664d03a1ad21937a160154.png]: https://img-blog.csdnimg.cn/img_convert/a09c3b94d1664d03a1ad21937a160154.png
[856e7cdaeeca428692ad6e8962d5f1c1.png]: https://img-blog.csdnimg.cn/img_convert/856e7cdaeeca428692ad6e8962d5f1c1.png
[c2cec8ce74224ef3b7013f70c9adecbe.png]: https://img-blog.csdnimg.cn/img_convert/c2cec8ce74224ef3b7013f70c9adecbe.png
[d7a7145ad53941089f413b550e91229d.png]: https://img-blog.csdnimg.cn/img_convert/d7a7145ad53941089f413b550e91229d.png
[a3a9febb3b9a4cbd8c5cb0a39576b9ea.png]: https://img-blog.csdnimg.cn/img_convert/a3a9febb3b9a4cbd8c5cb0a39576b9ea.png
[a557021c524a4d84884abc04f1cd93b2.png]: https://img-blog.csdnimg.cn/img_convert/a557021c524a4d84884abc04f1cd93b2.png
[2b7766e6444e4ad6a53b63b62a36626c.png]: https://img-blog.csdnimg.cn/img_convert/2b7766e6444e4ad6a53b63b62a36626c.png
[c24f930617664dd49a1f8e0f87e9e33e.png]: https://img-blog.csdnimg.cn/img_convert/c24f930617664dd49a1f8e0f87e9e33e.png