普通的二叉树其实在实际运用中并不能发挥出什么作用。但是它是我们学习后续的二叉搜索树、AVL树、红黑树等数据结构时必备的基础，常见的二叉树面试题中使用的基本上也是普通二叉树，所以学好普通二叉树也是十分重要的。
一、树的概念及其结构
1.1 树的概念
树是一种非线性的数据结构，它是由n(n>=0)个有限结点组成一个具有层次关系的集合。把它称为树，是因为它看起来像一棵倒挂的树，根部分朝上，叶子部分朝下。
特点:
1. 树有一个特殊的结点，称为根结点，根节点没有前驱结点
2. 除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1 <= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继
3. 树是递归定义的
注意：树形结构中，子树之间不能有交集，否则就不是树形结构
1.2 树的相关概念
1.3 树的表示法
树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。
我们这里就简单的了解其中最常用的孩子兄弟表示法
typedef int DataType; struct Node { struct Node* _firstChild1; //第一个孩子结点 struct Node* _pNextBrother; //指向其下一个兄弟结点 DataType _data; };
二、二叉树的概念及其结构
2.1 概念
二叉树是n(n>=0)个结点的有限集合，由一个根结点以及两棵互不相交，分别称为左子树和右子树的二叉树组成
2.2 特殊二叉树
1. 满二叉树:
一棵深度为h且有2^h - 1个结点的二叉树(即每层的结点数都达到最大值)
2. 完全二叉树:
除最后一层外，每层上的结点数都达到最大值，在最后一层上只缺少右边的若干结点
(对于深度为k的且有n个结点的二叉树，当且仅当其每一个结点与深度为k的满二叉树中编号从1到n的结点一一对应时，该二叉树被称为完全二叉树)
满二叉树是一种特殊的完全二叉树
2.3 二叉树的性质
1.每个结点最多有两棵子树，即二叉树不存在度大于2的结点
2.二叉树的子树有左右之分，其子树的次序不能颠倒(有序树)
3.在二叉树的第i层上至多有 2^(i-1) 个结点 (i>0)
4.深度为k的二叉树至多有 2^k - 1 个结点(k>0)
5.对于任何一棵二叉树，若度为2的结点树有m个，则叶子数n必为m+1(即n = m+1)
6.具有N个结点的满二叉树的深度为 以2为底(N+1)的对数
7.对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有:
(1)若i > 0，i位置结点的双亲序号: (i-1)/2 若i = 0，i为根节点编号，无双亲节点
(2)若2i + 1 < n，i位置结点左孩子序号: 2i + 1 若2i + 1 >= n则无左孩子
(3)若2i + 2 < n，i位置结点右孩子序号: 2i + 2 若2i + 2 >= n则无右孩子
2.4 二叉树的存储结构
顺序存储
利用数组存储，一般数组只适合表示完全二叉树(不是完全二叉树会有空间上的浪费)，现实中使用中只有堆才会使用数组来存储
二叉树顺序存储在物理上是一个数组，在逻辑上是一个二叉树
具体可以看我的另一篇博客:
(10条消息) 堆结构的深度理解_GG_Bond19的博客-CSDN博客
https://blog.csdn.net/GG_Bruse/article/details/127742947
链式存储
二叉树的链式存储结构是指用链表来表示一棵二叉树，即用链来指示元素之间的逻辑关系。
通常的方法:链表的每个结点由三个域组成，数据域和左右指针域(即二叉链)。
链式结构又分为二叉链(left和right)和三叉链(left、right和parent)
typedef int BTDataType; // 二叉链 struct BinaryTreeNode { struct BinTreeNode* _pLeft; // 指向当前节点左孩子 struct BinTreeNode* _pRight; // 指向当前节点右孩子 BTDataType _data; // 当前节点值域 } // 三叉链 struct BinaryTreeNode { struct BinTreeNode* _pParent; // 指向当前节点的双亲 struct BinTreeNode* _pLeft; // 指向当前节点左孩子 struct BinTreeNode* _pRight; // 指向当前节点右孩子 BTDataType _data; // 当前节点值域 }
三、链式二叉树
3.1 遍历方式
深度优先遍历:DFS
先序(根)遍历: 根 左子树 右子树 NLR 最符合深度优先
中序(根)遍历: 左子树 根 右子树 LNR
后序(根)遍历: 左子树 右子树 根 LRN
typedef char BTDataType; struct BinaryTreeNode { struct BinaryTreeNode* left; struct BinaryTreeNode* right; BTDataType data; }; void PrevOrder(struct BinaryTreeNode* root)//前序 { if (root == NULL) { printf("NULL "); return; } printf("%c ", root->data); PrevOrder(root->left); PrevOrder(root->right); } void InOrder(struct BinaryTreeNode* root)//中序 { if (root == NULL) { printf("NULL "); return; } InOrder(root->left); printf("%c ", root->data); InOrder(root->right); } void PostOrder(struct BinaryTreeNode* root)//后序 { if (root == NULL) { printf("NULL "); return; } PostOrder(root->left); PostOrder(root->right); printf("%c ", root->data); }
层序遍历:BFS(广度优先遍历)
设二叉树的根结点所在层数为1，层序遍历就是从所在二叉树的根结点出发，
首先访问第一层的树根结点，然后从左到右访问第二层上的结点，以此类推，从上到下，从左到右，逐层访问树的结点。
void LevelOrder(BinaryTreeNode* root)//层序遍历 { Queue q; QueueInit(&q); if (root != NULL) QueuePush(&q, root); while (!QueueIsEmpty(&q)) { struct BinaryTreeNode* front = QueueFront(&q); QueuePop(&q); printf("%c ", front->data); if (front->left != NULL) QueuePush(&q, front->left); if (front->right != NULL) QueuePush(&q, front->right); } QueueDestory(&q); }
思路: 利用队列完成非递归的层序遍历
1、首先将二叉树的根节点push到队列中，判断队列不为空，就输出队头的元素，
2、遍历过的节点出队列
3、判断节点如果有孩子，就将孩子push到队列中
4、循环以上操作，直到Tree == NULL。
3.2 二叉树的创建和销毁
通过前序遍历的数组来构建二叉树
#include <stdio.h> #include <stdlib.h> #include <assert.h> typedef char BTDataType; typedef struct BinaryTreeNode { struct BinaryTreeNode* left; struct BinaryTreeNode* right; BTDataType data; }BinaryTreeNode; BinaryTreeNode* BuyNode(BTDataType x) { BinaryTreeNode* node = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode)); assert(node); node->data = x; node->left = node->right = NULL; return node; } BinaryTreeNode* CreateTree(char* str, int* pi) { if (str[*pi] == '#') { ++(*pi); return NULL; } BinaryTreeNode* root = BuyNode(str[(*pi)++]); root->left = CreateTree(str, pi); root->right = CreateTree(str, pi); return root; } void InOrder(BinaryTreeNode* root) { if (root == NULL) return; InOrder(root->left); printf("%c ", root->data); InOrder(root->right); } void DestoryTree(BinaryTreeNode* root)//后序销毁 { if (root == NULL) return; DestoryTree(root->left); DestoryTree(root->right); free(root); } int main() { char str[101] = { 0 }; scanf("%s", str); int i = 0; BinaryTreeNode* root = CreateTree(str, &i); InOrder(root); DestoryTree(root); return 0; }
四、常见面试题
未完
