数据结构之二叉树的定义及实现
1. 树的概念
主要的定义：
节点的度：一个节点含有的子树的个数称为该节点的度；如上图：A的为6
叶节点或终端节点：度为0的节点称为叶节点；如上图：B，C，H，I等节点为叶节点
分支节点或非终端节点：度不为0的节点；如上图：D，E，F，G等节点为分支节点
父节点或者双亲结点节点：若一个节点含有子节点，则这个节点成为其子节点的父节点
子节点或孩子节点：一个节点含有的子树的根节点称为该节点的子节点
兄弟节点：具有相同父节点的节点互称为兄弟节点
树的度：一棵树中最大节点的度称为树的度
节点的层次：从根开始定义起，根为第一层，根的子节点为第二层
树的高度或深度：树中结点的最大层次
节点的祖先：从根到该结点所经分支上的所有节点
子孙：以某节点为根的子树中任一节点都称为该节点的子孙
森林：由m(m>0)颗互不相交的多棵树的集合称为森林
2. 对各知识点的进一步画图解析：
- 节点的度
- 叶节点（终端节点）
- 分支节点（非终端节点）
- 父节点（双亲节点）
- 子节点（孩子节点）
- 兄弟节点
- 树的高度
- 节点的高度：从下往上数
- 堂兄弟节点
- 节点的祖先
- 子孙
3. 二叉树概念及结构
3.1概念
一棵二叉树是节点的有限集合，该集合或者为空，或者是由一个根节点加上两颗别称为左子树和右子树的二叉树组成。
3.2 二叉树的特点：
1. 每个节点最多有两颗子树，即二叉树不存在度大于2的节点。
2. 二叉树的子树有左右之分，其子树的次序不能颠倒。
3.3 链式二叉树存储的概念
二叉树的链式存储结构是指：用链表来表示一颗二叉树，即用链来指示元素的逻辑关系。
通常的方式是链表中每个节点由三个域组成，数据域和左右指针域，左右指针分别用来给出该节点左孩子和右孩子所在的链接点的存储地址。
链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链，后面课程学到高阶数据结构如红黑树等会用到三叉链。
3.4 二叉树的遍历
学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。访问节点所做的操作依赖于具体的应用问题。遍历时二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。
- 前序遍历(Preorder Traversal)
亦称先序遍历，访问根结点的操作发生在遍历其左右子树之前。
- 中序遍历(Inorder Traversal)
访问根节点的操作发生在遍历其左右子树之间
- 后序遍历(Postorder Traversal)
访问根节点的操作在遍历其左右子树之后。
由于被访问的节点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历
- 层序遍历（LevelOrder）
设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。
4. 二叉树功能的实现
- 二叉树结构定义（struct BinaryTreeNode)
代码实现：
typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;- 二叉树节点的创建（CreatBinaryTree)
BTNode* BuyNode(BTDataType x)//树中一个节点的创建
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("malloc fail");return NULL;}node->data = x;node->left = NULL;node->right = NULL;return node;
}1. 二叉树的前序遍历函数(PrevOrder)
递归不可能一直调用函数，因为这个过程一直在创建栈帧，即使栈再大，也会栈溢出。所以肯定会回归，回归的本质就是销毁栈帧。
递归是由两个部分构成：
1. 子问题
2. 返回条件
代码实现：
void PrevOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}printf("%d ", root->data);PrevOrder(root->left);PrevOrder(root->right);
}2. 二叉树的中序遍历函数(InOrder)
void InOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right);}3.二叉树的后序遍历函数(PostOrder)
void PostOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->data);
}4. 统计二叉树节点个数(BTreeSize)
int TreeSize(BTNode* root)
{//写法一if (root == NULL)return 0;return BTreeSize(root->left) + BTreeSize(root->right) + 1;//写法二return root == NULL ? 0 : BTreeSize(root->left) + BTreeSize(root->right) + 1;
}5. 求出叶子节点的数量(TreeLeafSize)
int BTreeLeafSize(BTNode* root)//接受一个指向二叉树节点的指针root作为参数
{if (root == NULL)//代码检查根节点是否为空{return 0;}if ( root->left==NULL &&root->right==NULL){return 1;}return BTreeLeafSize(root->left) + BTreeLeafSize(root->right);}6. 二叉树的层序遍历(LevelOrder)
前序中序后序遍历 深度优先遍历
层序遍历 广度优先遍历 用队列去实现
void LevelOrder(BTNode* root)
{Queue q;//在函数内部，定义了一个队列q，并通过调用QueueInit函数对队列进行初始化。QueueInit(&q);//如果根节点root不为空，将根节点入队，即调用QueuePush函数将root指针插入到队列q中。if (root)QueuePush(&q,root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);//首先通过调用QueueFront函数获取队列q的队首元素，并将其赋值给指针变量frontQueuePop(&q);//调用QueuePop函数将队首元素出队printf("%d ", front->data);//通过printf函数打印front指向的节点的数据值//如果front的左子节点不为空，将左子节点入队，//即调用QueuePush函数将front->left指针插入到队列q中 if (front->left)QueuePush(&q, front->left);//后面这个参数是一个值，不是地址//如果front的右子节点不为空，将右子节点入队，//即调用QueuePush函数将front->right指针插入到队列q中。if (front->right)QueuePush(&q, front->right);//后面这个参数是一个值，不是地址//循环体内的操作完成后，继续下一次循环，直到队列q为空。}//最后，打印换行符表示层序遍历结束，
//并调用QueueDestroy函数销毁队列q，释放内存。printf("\n");QueueDestroy(&q);
}