数据结构-二叉树

归志宁无五亩园，读书本意在元元。这篇文章主要讲述数据结构-二叉树相关的知识，希望能为你提供帮助。
前言

带你图解二叉树的多种递归遍历

下面开始本节课的学习

目录
二叉树的构建
结点类型的定义
构建二叉树之间的关系
深度优先遍历
前序遍历
1.代码实现
2.图解递归
中序遍历
1.代码实现
2.图解递归
后序遍历
1.代码实现
2.图解递归
广度优先遍历
1.层序遍历
2.代码实现
面试题
C语言面试题

二叉树的构建定义：
二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树，且有左右之分。
特点：
每个结点最多有俩孩子（二叉树中不存在度大于2的结点）。
二叉树可以是空集合，根可以有空的左子树和空的右子树。
二叉树有左右之分，次序不能颠倒。
二叉树的性质：
1.在二叉树的第i层上至多有2^（i-1）个结点（i> 1）。
2.深度为k的二叉树至多有2^k-1个结点（k> =1）。
3.对任何一颗二叉树T，如果其叶子数为n0，度为2的结点数为n2，则n0=n2+1.
4. 具有n个结点的完全二叉树的深度为(log2N)+1。

文章图片

思路（借助一个队列）：
先把根入队列，然后开始从队头出数据。
出队头的数据，把它的左孩子和右孩子依次从队尾入队列（NULL不入队列）。
重复进行步骤2，直到队列为空为止。

代码实现

void BinaryLevelOrder(BT* n1)

Queue q;
QueueInit(& q);
if (n1!=NULL)

QueuePush(& q, n1);

while (!QueueEmpty(& q))

BT* front = QueueTop(& q);
QueuePop(& q);
printf("%c ", front-> x);
// 不把NULL打印出来
//if (front-> left!=NULL)
//
//QueuePush(& q, front-> left);
//
//if (front-> right != NULL)
//
//QueuePush(& q, front-> right);
//
if (front-> left != NULL)

QueuePush(& q, front-> left);

else

printf("NULL ");

if (front-> right != NULL)

QueuePush(& q, front-> right);

else

printf("NULL ");

QueueDestory(& q);

面试题已知一颗二叉树的中序序列和后序序列分别是BDCEAFHG和DECBHGFA,画出这颗树（1）由后序遍历特征，根结点比在后序序列尾部，即根结点是A;
（2）由中序遍历特征，根结点必在中间，而且其左边必须全部是左子树子孙(BDCE),其右部必全部是右子树子孙(FHG);
（3）继而根据后序中的DECB子树可确定B为A的左孩子，根据HGF得出F为A的右孩子；依次类推，可以唯一确定一棵二叉树如图1所示。
但是，由一棵二叉树的先序序列和后序序列不能唯一确定一棵二叉树，因为无法确定左右子树两部分。例如，如果有先序序列AB,后序序列BA,因为无法确定B为左子树还是右子树，所以可以得到如图2所示的两棵不同的二叉树。

二叉树的后序序列为DBFEGCA中序序列为DBAFECG,求它的先序序列(1) 由后序序列为DBFEGCA得到二叉树的根为A,由中序序列为DBAFECG得到二叉树的左子树子孙为：DB，右子树子孙为：FECG。
(2)我们先看它的左子树子孙，由后序序列为DB，中序序列为DB得到B为A的左孩子，D为B的左孩子。
(3)再看它的右子树子孙，由后序序列FEGC，中序序列FECG得到C为A的右孩子，C的左子树子孙为FE右孩子为G,又由后序序列FE，中序序列FE得到E为G的左孩子，F为G的左孩子
得到二叉树如下图：

它的先序序列为：ABDCEFG

C语言面试题(11-21)11.全局变量和局部变量在内存中是否有区别？如果有，是什么区别？
答：全局变量储存在静态数据区，局部变量在堆栈中。
12.什么是平衡二叉树？
答：左右子树都是平衡二叉树且左右子树的深度差值的绝对值不大于1。
13.堆栈溢出一般是由什么原因导致的？

1.没有回收垃圾资源
2.层次太深的递归调用

14.冒泡排序算法的时间复杂度是什么？
答：O(n^2)
15.什么函数不能声明为虚函数？
答：constructor
16、队列和栈有什么区别？
答：队列先进先出，栈后进先出
17、不能做switch()的参数类型
答：switch的参数不能为实型。
18、局部变量能否和全局变量重名？
答：能，局部会屏蔽全局。
19.什么是预编译,何时需要预编译?
答：预编译又称为预处理,是做些代码文本的替换工作。处理#开头的指令,比如拷贝#include包含的文件代码，#define宏定义的替换,条件编译等，就是为编译做的预备工作的阶段，主要处理#开始的预编译指令，预编译指令指示了在程序正式编译前就由编译器进行的操作，可以放在程序中的任何位置。
c编译系统在对程序进行通常的编译之前，先进行预处理。c提供的预处理功能主要有以下三种：1）宏定义　2）文件包含　3）条件编译