5.二叉树的顺序存储和链式存储
5-1二叉树的顺序存储
结论：完全二叉树很适合顺序存储，但是普通二叉树不适合顺序存储
不难看出：完全二叉树只要按照结点层次放到数组中即可
但是普通二叉树由于有些位置的空缺，而二叉树的左右结点是有顺序的，所以会导致一部分空缺，造成空间的浪费，及不推荐。
5-2链式存储
利用二叉链表就可以解决上面普通链表不适合用顺序存储的缺点，如果左孩子不存在则为NULL
typedef int DataType; typedef struct Btree { DataType data; struct Btree* lchild, rchild; }Btree;
5-3变式：三叉链表
在实际问题中，我们有时候还需要访问双亲结点，二叉链表存储则需要从根节点出发查找到双亲结点，这样显得有点麻烦，所以有的时候，为了方便我们往往还可以使用到三叉链表，也就是在二叉链表，存储左孩子和右孩子的地址的同时，额外存储结点的双亲结点。
6.二叉树的前中后序遍历
二叉树的遍历就是按照某条路径访问二叉树的每一个结点有且仅有一次，二叉树的访问范围很广：输出，查找，插入，修改，删除等，如果我们规定左右子树的访问顺序只能是先左后右，那么就只有3种访问顺序：DLR,LDR,LRD,按照根访问的时机先后，分别叫做先序遍历，中序遍历和后序遍历。
这里其实使用的是一种递归的思想：以前序遍历为例，我们规定一种规则，就是先访问他的根，再访问他的左子树和右子树，而左子树又是一棵二叉树，同样是递归访问他的左子树，再去访问他的右子树....以此类推。
这就好比是：要把所有的犯人抓住，我们规定了一种方式就是先抓住头头，然后抓完了头头的所有左翼，才能抓头头的右翼，然后抓左翼的时候，又有头头，又是抓完了头头的所有左翼，才能抓头头的右翼...
下面以下图为例，给大家写一下代码：
#include<stdio.h> #include<stdlib.h> #include<stdbool.h> typedef struct BTNode { int val; struct BTNode* left; struct BTNode* right; }BTNode; BTNode* CreateBTree() { BTNode* n1 = (BTNode*)malloc(sizeof(BTNode)); BTNode* n2 = (BTNode*)malloc(sizeof(BTNode)); BTNode* n3 = (BTNode*)malloc(sizeof(BTNode)); BTNode* n4 = (BTNode*)malloc(sizeof(BTNode)); BTNode* n5 = (BTNode*)malloc(sizeof(BTNode)); BTNode* n6 = (BTNode*)malloc(sizeof(BTNode)); n1->val = 1; n2->val = 2; n3->val = 3; n4->val = 4; n5->val = 5; n6->val = 6; n1->left = n2; n1->right = n4; n2->left = n3; n2->right=NULL; n3->left = NULL; n3->right = NULL; n4->left = n5; n4->right = n6; n5->left = NULL; n5->right = NULL; n6->left = NULL; n6->right = NULL; return n1; } void PrevOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } printf("%d ", root->val); PrevOrder(root->left); PrevOrder(root->right); } void InOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } InOrder(root->left); printf("%d ", root->val); InOrder(root->right); } void PostOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } PostOrder(root->left); PostOrder(root->right); printf("%d ", root->val); } int main() { BTNode* root = CreateBTree(); //前序遍历 PrevOrder(root); printf("\n"); //中序遍历 InOrder(root); printf("\n"); //后序遍历 PostOrder(root); return 0; }
7.求二叉树总结点个数
相信你理解了二叉树的三种常见的遍历方式，这道题不难破解，似乎就是在把打印的部分换成一个计数器计数就可以了，但是事情似乎没有你想象的那么简单，因为你或许会犯以下的小错误：（不加static是大错，加static就是有一点小毛病，static只初始化一次）
错误示范1: int TreeSize(BTNode* root) { int size = 0;//每一次递归调用都会初始化size=0;使得最终的结果为1 if (root == NULL) { return 0; } ++size; TreeSize(root->left); TreeSize(root->right); return size; }
于是聪明的你又想到了使用satic只能初始化一次，但是似乎....
static int size = 0;//这样使得以后这个程序里所有再次调用这个TreeSize函数都不会再初始化 //但是这也是问题所在，直接封杀了我如果想再次调用这个函数求一下TreeSize的
int TreeSize(BTNode* root) { static int size = 0;//这样使得以后这个程序里所有再次调用这个TreeSize函数都不会再初始化 //但是这也是问题所在，直接封杀了我如果想再次调用这个函数求一下TreeSize的想法。 if (root == NULL) { return 0; } ++size; TreeSize(root->left); TreeSize(root->right); return size; }
所以最好的方法还得是下面这种方法：
int TreeSize(BTNode* root) { if (root == NULL) { return 0; } return 1 + TreeSize(root->left) + TreeSize(root->right); }
return 1 + TreeSize(root->left) + TreeSize(root->right); //这里值得注意的是，因为要求二叉树的总结点，必然要遍历整个二叉树，那么遍历采用的是 //前序遍历还是中序遍历还是后序遍历都是无所谓的，所以1的位置相对于非空结点的左右子树递归都是任意的(这里其实左右子树的递归顺序也是未定义的)
8.求二叉树的叶子结点
求二叉树的叶子结点，遍历整棵二叉树是一定的，但是这次我们要计数的不是所有的结点，而是叶子结点,
到了这里，我觉得我们应该把一棵二叉树分成空结点&非空节点
或者将非空节点再细分为非叶子结点和叶子结点吗，也就是空结点，非叶子结点，叶子结点
在这题的话就是说对于空结点统计为0，叶子结点统计为1，非叶子结点就递归他的左子树和右子树就完了,并且统计为0(这里代码中隐式为0,没有写出)
if (root == NULL) { return 0; } //这里过滤掉的是空节点，并且返回0后面统计
if (root->left == NULL && root->right == NULL) { return 1; } //这里过滤的是叶子结点,并且叶子结点要返回1给后面统计
return TreeLeftSize(root->left) + TreeLeftSize(root->right); //这里就是对非空结点中的非叶子结点的左子树和右子树进行递归(并且既然root是非叶子结点的话就不用+1)
这里我觉得递归的 return TreeLeftSize(root->left) + TreeLeftSize(root->right);这段从近root的来看就是意味着是root的左右节点,从远的递归的角度来看却是左右子树的性质,显然是第二种远的角度来看合理一点.
int TreeLeftSize(BTNode* root) { if (root == NULL) { return 0; } if (root->left == NULL && root->right == NULL) { return 1; } return TreeLeftSize(root->left) + TreeLeftSize(root->right); }
到了这里我希望你能看出这道题和上道题目的一点区别:(画框的区域代表的是遍历的区域)
9.求二叉树的高度
这里我们要求二叉树的高度,首先我们就得知道针对得对象是非叶子节点,就得先递归求出左子树和右子树的高度,然后进行比较再分析一下才能求出整个二叉树的高度,所以这里我们得采用类似后序遍历得方式进行求二叉树的高度,
思路:父亲的高度=左右子树高度的最大值+1
int TreeHeight(BTNode* root) { if (root == NULL) { return 0; } return TreeHeight(root->left) > TreeHeight(root->right) ? TreeHeight(root->left)+1 : TreeHeight(root->right)+1; }
