#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 ", NodeNum); NodeNum = GetNodeNumKthLevel(bTree, 3); //获取第3层节点数 printf("第3层节点数为：%d ", NodeNum); printf("先序遍历结果为： "); Preorder(bTree); printf(" "); printf("中序遍历结果为： "); Inorder(bTree); printf(" "); printf("后序序遍历结果为： "); Postorder(bTree); printf(" "); 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); }