一、树的基本概念
1.结点的度: 结点子结点的个数.
A结点，也就是根节点的度为3分别是BCD
K，L节点的度为0
2.树的度: 树中最大的节点的度为树的度.
栗子树的度为3
3.结点的高度和深度：
高度是自下向上累计
深度是自上向下累计
A节点的高度为4，深度为1
K节点的高度为1，深度为4
4.树的高度和深度：
☆树中结点最大的层数栗子树的高度和深度为4，同时层数也为4
5.路径：
自上而下的有向的，A和E的路径为A->B->E,E和F这样的兄弟结点是不存在路径的。
6.路径长度：
路径上所经历边的个数，A->B->E的路径长度为2
二、树的性质.
1.树中的结点数 = 所有结点度数 + 1
解释：结点度的含义指的就是，结点有几个孩子，那么，每个节点的度都可以和相应的结点对应，因为根结点是最顶层，然没有父结点，所以，所有结点的度 + 根节点 = 树中的结点数
2.度为M的树的，任意结点的度数小于等于M，结点最多M个孩子
3.度为M的树，至少有一个结点的度为M
4.度为M的树，一定是非空树，至少有M+1个节点
5.N叉树，任意结点的度小于等于N
6.N叉树，允许所有结点的度小于N
7.N叉树，可以是空树
8.度为M的树，第i层最多有M^(i-1)个节点，其中i>=1
解析:最多结点树，我们可以假设每个节点的度都为M，i>=1，说明了层数从第一层开始计数，一共层，第一层M0个，第二层M1，第三层就是M2...第i层就是M(i-1)次方个。
9.高度为H的M叉树最多有1-M^H/1-M
解析:高度为H说明了一共有H层，M叉树最多，可以假设，是满M叉二叉树，那么第一层有M^0 第二层有M1...第H层有M(h-1),因为是从零开始计数的0~H-1刚好H项，等比数列求和
1*(1-M^H)/(1-M) = 1-M^H/1-M
10.具有N个结点的M叉树最小高度为logM^(1-N(1-M))
解析：最小高度就是当M叉树为满M叉树的时候，具有N个结点
1-M^H/1-M = N => H = logM^(1-N(1-M))
三、二叉树
基本概念
1.由一个根节点和两个互不相交的左子树和右子树组成，同是左右子树也是一个二叉树，利用递归进行定义的数据结构.
2.二叉树有五种状态：空二叉树、只有左子树，只有右子树，只有根节点，左右子树都有。逻辑结构
几种特殊的二叉树：
1.满二叉树
①高度为h的满二叉树，有2^h -1个结点.
②只有最后一层含有叶子节点，不存在度为1的节点
③按照层序从1开始编号，i节点的左孩子为2i,i节点的右孩子为2i+1,父节点为i/2
④i<=n/2为分支节点，i>n/2为叶子节点.
2.完全二叉树
①当且仅当每个结点都与高度为h的满二叉树中编号为1~n的节点一一对应时，称为完全二叉树
②只有最后两层可能出现叶子节点
③最多只有一个度为1的节点
④结点i的左孩子为2i右孩子为2i+1，父亲节点i/2
⑤i<=n/2为分支节点，i>n/2为叶子节点.
3.二叉排序树
①左子树所有的节点关键字小于根节点小于右子树关键字.
②左右子树又是一颗二叉排序树
4.平衡二叉树
①树上任意结点的左子树和右子树深度只差不超过1
- 二叉树常考性质
1.度为0,1,2的结点个数分别为N0,N1,N2则N0 = N2 + 1
解析：设2插树总结点树为n=>
①n = N0 + N1 + N2
树的结点树 = 总度数 + 1 =>
②n = N1 + 2N2 + 1
①②联立 => N0 = N2 + 1即度数为0的结点数量 = 度数为2的结点 + 1
2.二叉树第i层最多2^(i-1)i>=1
3.高度为h的二叉树最多有 2^h - 1个结点.
- 存储结构
顺序存储
1.顺序存储只适合存储完全二叉树
解析：二叉树是完全二叉树的时候可以通过，2i，2i+1, i/2
来找到结点之间的关系，当树为普通二叉树的时候，我们可以将普通二叉树转换成完全二叉树，这样的话，会有一部分空间导致浪费。
浪费的空间
所以二叉树很少使用顺序存储，一般树为完全二叉树的时候，可以使用.
2.链式存储代码
#include<stdio.h>
#include<stdlib.h>
typedef struct TreeNode {
char data;
struct TreeNode* leftChild;
struct TreeNode* rightChild;
}TreeNode,Tree;
Tree* inintTree(char root);
TreeNode* getTreeNode(char data);
void preOrder(Tree* tree);
void inOrder(Tree* tree);
void postOrder(Tree* tree);
void visit(TreeNode* treeNode);
int main() {
// 构建树.
TreeNode* tree = inintTree('a');
TreeNode* rootA = tree;
TreeNode* nodeB = getTreeNode('b');
TreeNode* nodeC = getTreeNode('c');
TreeNode* nodeD = getTreeNode('d');
TreeNode* nodeE = getTreeNode('e');
rootA->leftChild = nodeB;
rootA->rightChild = nodeC;
nodeB->leftChild = nodeD;
nodeB->rightChild = nodeE;
//前序遍历
preOrder(tree);
printf("\n");
// 中序遍历
inOrder(tree);
printf("\n");
// 层序遍历
postOrder(tree);
printf("\n");
}
Tree* inintTree(char root) {
return getTreeNode(root);
}
TreeNode* getTreeNode(char data) {
TreeNode* treeNode = (TreeNode*)malloc(sizeof(TreeNode));
treeNode->data = data;
treeNode->leftChild = NULL;
treeNode->rightChild = NULL;
return treeNode;
}
void preOrder(Tree* tree){
if(tree!=NULL) {
visit(tree);
preOrder(tree->leftChild);
preOrder(tree->rightChild);
}
}
void inOrder(Tree* tree){
if(tree!=NULL) {
inOrder(tree->leftChild);
visit(tree);
inOrder(tree->rightChild);
}
}
void postOrder(Tree* tree){
if(tree!=NULL) {
postOrder(tree->leftChild);
postOrder(tree->rightChild);
visit(tree);
}
}
void visit(TreeNode* treeNode) {
printf("%c ",treeNode->data);
}
- 二叉树的遍历
①前序遍历
②中序遍历
③后序遍历
④层序遍历
思想：初始化一个辅助队列，根节点入队，若队列非空，队头节点出队，出队节点存在左右孩子则插入队尾，重复上述，直到队列为空.
- 根据遍历顺序推出二叉树的结构
1.前中 √
2.后中√
3.层中√
必须要有中序遍历，否则无法推导二叉树结构.
四、线索二叉树
1.中序线索二叉树
#include<stdio.h>
typedef struct TreeNode {
char data;
struct TreeNode leftChild,rightChild;
int leftFlag,rightFlag;
}TreeNode,Tree;
TreeNode* getTreeNode(char data);
void buildThreadBinaryTree(Tree* tree);
void dealTree(Tree* tree);
TreeNode* pre = NULL;
int main() {
TreeNode* treeNodeA = getTreeNode('a');
TreeNode* treeNodeB = getTreeNode('b');
TreeNode* treeNodeC = getTreeNode('c');
TreeNode* treeNodeD = getTreeNode('d');
TreeNode* treeNodeE = getTreeNode('e');
treeNodeA->leftChild = treeNodeB;
treeNodeA->rightChild = treeNodeC;
treeNodeB->leftChild = treeNodeD;
treeNodeE->rightChild = treeNodeE;
//这里以中序线索二叉树为例.
buildThreadBinaryTree(treeNodeA);
//处理最后一个结点.
if(pre->rightChild == NULL) {
pre->rightFlag = 1;
}
}
TreeNode* getTreeNode(char data) {
TreeNode* treeNode = (TreeNode*)malloc(sizeof(TreeNode));
treeNode->data = data;
treeNode->leftChild = NULL;
treeNode->leftFlag = 0;
treeNode->rightChild = NULL;
treeNode->rightFlag = 0;
return treeNode;
}
void buildThreadBinaryTree(Tree* tree) {
if(tree != NULL) {
buildThreadBinaryTree(tree->leftChild);
dealTree(tree);
buildThreadBinaryTree(tree->rightChild);
}
}
void dealTree(Tree* tree) {
//找前驱
if(tree->leftChild == NULL) {
tree->leftChild = pre;
tree->leftFlag = 1;
}
//找后继
if(pre != NULL && pre->rightChild == NULL) {
pre->rightChild = tree;
pre->rightFlag = 1;
}
pre = tree;
}
2.前序遍历
void buildThreadBinaryTree(Tree* tree) {
if(tree != NULL) {
dealTree(tree);
//为了防止转圈的问题.
if(tree->leftFlag == 0) {
buildThreadBinaryTree(tree->leftChild);
}
buildThreadBinaryTree(tree->rightChild);
}
}
3.后序遍历
void buildThreadBinaryTree(Tree* tree) {
if(tree != NULL) {
buildThreadBinaryTree(tree->leftChild);
buildThreadBinaryTree(tree->rightChild);
dealTree(tree);
}
}
4.找前驱和后继
待更新....
