#define _CRT_SECURE_NO_DEPRECATE /*取消scanf,printf不安全之类的错误提示*//*
关于非线性的数据结构当然树形结构最重要，而树里面又属二叉树最重要，
所以在后面将列出二叉树的各种使用方法，包括基本的遍历，和我在一些
资料上看到的关于二叉树的面试题型。至于一些很高级的树形结构，如平
衡树，还有线索树等，就暂时不写出来，先完成最基本的，再一点点的加
*/
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
//typedef void * ElemType;
typedef int ElemType;
typedef struct TreeNode
{
ElemType m_nValue;
struct TreeNode *m_pLeft;
struct TreeNode *m_pRight;
}BinaryTreeNode;
/*函数声明*/
//基本操作函数
BinaryTreeNode * CreateTree(BinaryTreeNode *bTree);
BinaryTreeNode * SortedArryTobTree(BinaryTreeNode *bTree, int Node[], int start, int end);
void Preorder(BinaryTreeNode *bTree);//这个是先序遍历，先根，左子树，右子树
void Inorder(BinaryTreeNode *bTree);//中序遍历，左子树，根，右子树
void Postorder(BinaryTreeNode *bTree);//后序遍历，左子树，右子树，根
//应用函数
int GetNodeNum(BinaryTreeNode *pRoot); //二叉树中的节点
int GetNodeNumKthLevel(BinaryTreeNode *pRoot, int K);//求二叉树中第K层的节点个数
bool IsAVL(BinaryTreeNode *pRoot); //判断是否平衡二叉树
int GetLeafNodeNum(BinaryTreeNode * pRoot); //求二叉树中叶子节点的个数
/*
二叉树主要的难点是遍历
基本上所有的算法都是基于二叉树的遍历的
至于创建二叉树就需要在输入的时候把线性的结构转换成非线性的
用输入的方式创建二叉树
*/
//2 3 4 0 0 5 0 6 0 0 7 0 0
int main()
{
static int i = 0;
static int Node[13] = {9,12,14,17,19,23,50,54,67,72,76};
int NodeNum;
BinaryTreeNode *bTree;
bTree = (BinaryTreeNode *)malloc(sizeof(BinaryTreeNode));
//bTree = CreateTree(bTree);
bTree = SortedArryTobTree(bTree, Node, 0,10);
NodeNum = GetNodeNum(bTree); //获取节点数
printf("节点数为：%d\n", NodeNum);
NodeNum = GetNodeNumKthLevel(bTree, 3); //获取第3层节点数
printf("第3层节点数为：%d\n", NodeNum);
printf("先序遍历结果为：\n");
Preorder(bTree);
printf("\n");
printf("中序遍历结果为：\n");
Inorder(bTree);
printf("\n");
printf("后序序遍历结果为：\n");
Postorder(bTree);
printf("\n");
return 0;
system("pause");
}
//将输入独立起来，从键盘输入数据建立二叉树
BinaryTreeNode * CreateTree(BinaryTreeNode *bTree)
{
int input;
scanf("%d", &input);//按先序建立二叉树
if (input == 0)
{
bTree = NULL;//置为NULL后结束
return bTree;
}
bTree = (BinaryTreeNode *)malloc(sizeof(BinaryTreeNode));
bTree->m_nValue = input;
bTree->m_pLeft = CreateTree(bTree->m_pLeft);
bTree->m_pRight = CreateTree(bTree->m_pRight);
return bTree;
}
//将数组转换成二叉树
BinaryTreeNode * SortedArryTobTree(BinaryTreeNode *bTree, int Node[], int start, int end)
{
if (start > end) return NULL; //递归出口
// 这里同（start+left）/2，目的是为了防止溢出.
int mid = start + (end - start) / 2;
bTree = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));
bTree->m_nValue = Node[mid];
bTree->m_pLeft = SortedArryTobTree(bTree, Node, start, mid - 1);
bTree->m_pRight = SortedArryTobTree(bTree,Node,mid+1,end);
return bTree;
}
//三种递归遍历方法
void Preorder(BinaryTreeNode *bTree)//这个是先序遍历，先根，左子树，右子树
{
if (bTree != NULL)
{
printf("%d ", bTree->m_nValue);
Preorder(bTree->m_pLeft);
Preorder(bTree->m_pRight);
}
}
void Inorder(BinaryTreeNode *bTree)//中序遍历，左子树，根，右子树
{
if (bTree != NULL)
{
Inorder(bTree->m_pLeft);
printf("%d ", bTree->m_nValue);
Inorder(bTree->m_pRight);
}
}
void Postorder(BinaryTreeNode *bTree)//后序遍历，左子树，右子树，根
{
if (bTree != NULL)
{
Postorder(bTree->m_pLeft);
Postorder(bTree->m_pRight);
printf("%d ", bTree->m_nValue);
}
}
/*获取二叉树的节点数*/
/*
递归解法：
（1）如果二叉树为空，节点个数为0
（2）如果二叉树不为空，二叉树节点个数 = 左子树节点个数 + 右子树节点个数 + 1
*/
int GetNodeNum(BinaryTreeNode *pRoot)
{
if (pRoot == NULL){
return 0; //栈出口
}
return GetNodeNum(pRoot->m_pLeft) + GetNodeNum(pRoot->m_pRight) + 1;
}
/*求二叉树的深度*/
/*
递归解法：
（1）如果二叉树为空，二叉树的深度为0
（2）如果二叉树不为空，二叉树的深度 = max(左子树深度， 右子树深度) + 1
*/
int GetDepth(BinaryTreeNode *pRoot)
{
if (pRoot == NULL)
return 0;
int depthLeft = GetDepth( pRoot->m_pLeft );
int depthRight = GetDepth( pRoot->m_pRight);
return depthLeft > depthRight?(depthLeft + 1) : (depthRight + 1);
}
/*求二叉树第K层的节点个数*/
/*
递归解法
（1） 如果二叉树为空或者k<1 返回0
（2） 如果二叉树不为空并且k==1，返回1
（3）如果二叉树不为空且k>1，返回左子树中k-1层的节点个数与右子树k-1层节点个数之和
*/
int GetNodeNumKthLevel(BinaryTreeNode *pRoot, int K)
{
if (pRoot == NULL || K < 1){
return 0;
}
if (pRoot != NULL && K == 1){
return 1;
}
int numleft = GetNodeNumKthLevel(pRoot->m_pLeft,K-1); // 左子树中k-1层的节点个数
int numright = GetNodeNumKthLevel(pRoot->m_pRight, K - 1); // 右子树中k-1层的节点个数
return (numleft + numright);
}
/*如何判断一颗二叉树是平衡二叉树*/
/*
递归解法：
（1）如果二叉树为空，返回真
（2）如果二叉树不为空，如果左子树和右子树都是AVL树并且左子树和右子树高度相差不大于1，返回真，其他返回假
*/
bool IsAVL(BinaryTreeNode *pRoot)
{
if (pRoot == NULL){
return true;
}
int leftheight = GetDepth(pRoot->m_pLeft);
int rightheight = GetDepth(pRoot->m_pRight);
int diff = leftheight - rightheight;
if (abs(diff) > 1)
return false;
return IsAVL(pRoot->m_pLeft) && IsAVL(pRoot->m_pRight); //递归判断左右子树，必须左右子树都为平衡二叉树，这颗二叉树才是平衡二叉树
}
/*求二叉树中叶子节点的个数*/
/*
递归解法：
（1）如果二叉树为空，返回0
（2）如果二叉树不为空且左右子树为空，返回1
（3）如果二叉树不为空，且左右子树不同时为空，返回左子树中叶子节点个数加上右子树中叶子节点个数
*/
int GetLeafNodeNum(BinaryTreeNode * pRoot)
{
if (pRoot == NULL)
return 0;
if (pRoot->m_pLeft == NULL && pRoot->m_pRight == NULL)
return 1;
int numLeft = GetLeafNodeNum(pRoot->m_pLeft); // 左子树中叶节点的个数
int numRight = GetLeafNodeNum(pRoot->m_pRight); // 右子树中叶节点的个数
return (numLeft + numRight);
}
