目录一、树的概念及结构1.树的概念2.树的相关概念3.树的表示二、二叉树概念及结构1.概念2.特殊的二叉树1满二叉树2完全二叉树3.二叉树的性质4.二叉树的存储结构1顺序存储2链式存储三、二叉树链式结构的实现1.二叉树的创建函数声明函数定义函数测试2.二叉树销毁函数声明函数定义3.二叉树的遍历1前序遍历、中序遍历、后序遍历的递归实现函数声明函数定义函数测试测试结果2二叉树的层序遍历4.二叉树结点个数函数声明函数定义函数测试5.二叉树叶子节点个数函数声明函数定义函数测试6.二叉树第k层结点个数函数声明函数定义函数测试7.二叉树查找值为x的节点函数声明函数定义函数测试8.完整代码BinaryTree.hBinaryTree.cTest.c一、树的概念及结构1.树的概念树是一种非线性的数据结构。它由nn0个有限结点组成的一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒置的树也就是说它是根朝上、叶朝下的。在树形结构中子树之间不能有交集否则就不是树结构。除了根节点以外每个节点有且只有一个父节点一棵n个节点的树有(n-1)条边2.树的相关概念节点的度一个节点含有的子树的个数称作该节点的度如上图A的度是3。叶子节点或终端节点度为0的节点称为叶子节点如上图K、L、F……等节点都是叶子节点。非终端节点或分支节点度不为0的节点如上图B、C、D……等节点为分支节点。双亲节点或父节点若一个节点含有子节点则这个结点称为其子节点的父节点如上图A是B的父节点。孩子节点或子节点一个节点含有的子树的根节点称为该节点的子节点如上图B是A的子节点。兄弟节点具有相同父节点的节点互为兄弟节点如上图B、C、D互为兄弟节点。树的度一棵树中最大的结点的度称为树的度。例如上图树的度为3。节点的层次从根开始定义起根为第一次层根节点的子节点为第二层以此类推。树的高度或深度树中节点的最大层次如上图树的高度为4。堂兄弟结点双亲在同一层的结点互为堂兄弟如上图E和G互为堂兄弟。结点的祖先从根到该结点所经分支上的所有节点如上图A是所有节点的祖先。子孙以某节点为根的子树中任一节点都称为该节点的子孙如上图所有节点都是A的子孙。森林由m(m0)棵互不相交的树组成的集合称为森林。3.树的表示树有很多种表示方式如双亲表示法、孩子表示法、孩子双亲表示法以及孩子兄弟表示法。二、二叉树概念及结构1.概念一棵二叉树是节点的一个有限集合该节点1或为空2由一个根节点加上左右两棵子树左子树和右子树组成从上图可以看出1二叉树不存在度大于2的结点2二叉树的子树有左右之分次序不能颠倒因此二叉树是有序树注意对于任意的二叉树都是由以下几种情况复刻而成的2.特殊的二叉树1满二叉树一个二叉树如果每一层的结点数量都达到最大值则该二叉树为满二叉树。也就是说如果一个高度为k的二叉树结点总数是(2^k-1)则它就是满二叉树。2完全二叉树完全二叉树是效率很高的数据结构。完全二叉树是由满二叉树引出来的。对于深度为k的二叉树当且仅当其每个结点都与深度为k的满二叉树的编号一一对应时称其为完全二叉树。满二叉树是特殊的完全二叉树。高度为k的完全二叉树中最少有2^(k-1)个节点。3.二叉树的性质1若规定根节点的层数为1则一棵非空二叉树的第i层上最多有2^(i-1)个节点2若规定根节点的层数为1则深度为h的二叉树的最大节点数是2^h-13对任意一棵二叉树如果度为0的叶子结点的个数为n0度为2的分支节点的个数为n2则n0 n2 14若规定根节点的层数为1具有n个节点的满二叉树的深度h log2(n1)5对于具有n个节点的完全二叉树如果按照从上至下从左至右的数组顺序对所有节点从0开始编号则对于序号为i的节点有若i0i位置结点的双亲序号(i-1)/2i 0时i为根节点无双亲结点若2i1n左孩子序号2i12i1n否则无左孩子若2i2n左孩子序号2i22i2n否则无左孩子4.二叉树的存储结构1顺序存储顺序存储就是用数组来存储一般使用数组只适合表示完全二叉树因为不是完全二叉树会有空间的浪费。而现实中只有堆才会使用数组存储。二叉树顺序存储在物理上是一个数组在逻辑上是一棵二叉树。2链式存储二叉树的链式存储结构是指用链表来表示一棵二叉树即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域数据域和左右指针域组成左右指针分别指向左右孩子所在的结点。链式结构分为二叉链和三叉链。typedef int BTDataType; // 二叉链 struct BinaryTreeNode { struct BinaryTreeNode* left; // 指向当前结点的左孩子 struct BinaryTreeNode* right; // 指向当前结点的右孩子 BTDataType data; // 当前结点值域 }; // 三叉链 struct BinaryTreeNode { struct BinaryTreeNode* parent; // 指向当前结点的双亲 struct BinaryTreeNode* left; // 指向当前结点的左孩子 struct BinaryTreeNode* right; // 指向当前结点的右孩子 BTDataType data; // 当前结点值域 };三、二叉树链式结构的实现1.二叉树的创建传入二叉树的前序遍历序列字符串和字符串大小、起始下标用来创建二叉树函数声明// 通过前序遍历的数组ABD##E#H##CF##G##构建二叉树 BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi);函数定义// 通过前序遍历的数组ABD##E#H##CF##G##构建二叉树 BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi) { if (*pi n || a[*pi] #) { (*pi); return NULL; } BTNode* cur (BTNode*)malloc(sizeof(BTNode)); cur-_data a[*pi]; (*pi); cur-_left BinaryTreeCreate(a, n, pi); cur-_right BinaryTreeCreate(a, n, pi); return cur; }函数测试char a[] ABD##E#H##CF##G##; int i 0; BTNode* BinaryTree BinaryTreeCreate(a, sizeof(a) / sizeof(a[0]), i);2.二叉树销毁二叉树的销毁要以后序的顺序销毁函数声明// 二叉树销毁 void BinaryTreeDestory(BTNode** root);函数定义// 二叉树销毁 void BinaryTreeDestory(BTNode** root) { if (*root) { BinaryTreeDestory((*root)-_left); BinaryTreeDestory((*root)-_right); free(*root); *root NULL; } }3.二叉树的遍历二叉树遍历(Traversal)按照某种特定的规则依次对二叉树中的结点进行相应的操作并且每个结点只操作一次。访问结点所做的操作依赖于具体的应用问题。遍历二叉树是二叉树上最重要的运算之一也是二叉树上进行其他运算的基础。二叉树的遍历有四种前序遍历、中序遍历、后序遍历、层序遍历前序遍历Preorder Traversal 也叫先序遍历——访问根节点的操作发生在遍历其左右子树之前根左右。中序遍历Inorder Traversal——访问根节点的操作发生在遍历其左右子树之中左根右后序遍历Postorder Traversal——访问根节点的操作发生在遍历其左右子树之后左右根由于被访问的结点必须是某子树的根所以N(Node)、L(Left subtree)和R(Right subtree)又可解释为根、根的左子树、根的右子树。NLR、LNR和LRN又称为先根遍历、中根遍历和后根遍历。1前序遍历、中序遍历、后序遍历的递归实现递归的本质是把问题拆成当前问题和子问题。递归的返回条件本质是最小规模的子问题。函数声明// 二叉树前序遍历 void BinaryTreePrevOrder(BTNode* root); // 二叉树中序遍历 void BinaryTreeInOrder(BTNode* root); // 二叉树后序遍历 void BinaryTreePostOrder(BTNode* root);函数定义// 二叉树前序遍历 void BinaryTreePrevOrder(BTNode* root) { if (root NULL) { return; } printf(%c, root-_data); BinaryTreePrevOrder(root-_left); BinaryTreePrevOrder(root-_right); } // 二叉树中序遍历 void BinaryTreeInOrder(BTNode* root) { if (root NULL) { return; } BinaryTreeInOrder(root-_left); printf(%c, root-_data); BinaryTreeInOrder(root-_right); } // 二叉树后序遍历 void BinaryTreePostOrder(BTNode* root) { if (root NULL) { return; } BinaryTreePostOrder(root-_left); BinaryTreePostOrder(root-_right); printf(%c, root-_data); }可以看到前序遍历、中序遍历、后序遍历的代码非常相似只是递归调用的位置不同。函数测试BinaryTreePrevOrder(BinaryTree); printf(\n); BinaryTreeInOrder(BinaryTree); printf(\n); BinaryTreePostOrder(BinaryTree); printf(\n);测试结果2二叉树的层序遍历层序遍历是从所在二叉树的根节点出发从上到下从左到右依次访问每一层的每一个结点。层序遍历的实现需要使用队列上一层结点出队列时下一层结点入队列4.二叉树结点个数递归遍历二叉树若当前结点为空则返回0不为空则返回左子树结点个数右子树结点个数1函数声明// 二叉树节点个数 int BinaryTreeSize(BTNode* root);函数定义// 二叉树节点个数 int BinaryTreeSize(BTNode* root) { if (root NULL) { return 0; } int leftNum BinaryTreeSize(root-_left); int rightNum BinaryTreeSize(root-_right); return leftNum rightNum 1; }函数测试printf(%d\n, BinaryTreeSize(BinaryTree));5.二叉树叶子节点个数递归遍历二叉树若当前结点为空则返回0当前结点为叶子节点则返回1其他情况则返回左子树叶子结点个数右子树叶子结点个数函数声明// 二叉树叶子节点个数 int BinaryTreeLeafSize(BTNode* root);函数定义// 二叉树叶子节点个数 int BinaryTreeLeafSize(BTNode* root) { if (root NULL) { return 0; } if (root-_left NULL root-_right NULL) { return 1; } int leftNum BinaryTreeLeafSize(root-_left); int rightNum BinaryTreeLeafSize(root-_right); return leftNum rightNum; }函数测试printf(%d\n, BinaryTreeLeafSize(BinaryTree));6.二叉树第k层结点个数当前结点为空时返回0当k0时无法查找返回0当k1时说明当前结点就是第k层的结点返回1全部判断完毕后再依次遍历左右子树的k-1层并分别记录左右子树第k层的结点数量防止重复递归调用最后返回(leftCount rightCount)函数声明// 二叉树第k层节点个数 int BinaryTreeLevelKSize(BTNode* root, int k);函数定义// 二叉树第k层节点个数 int BinaryTreeLevelKSize(BTNode* root, int k) { if (root NULL) { return 0; } if (k 0) { return 0; } if (k 1) { return 1; } int leftCount BinaryTreeLevelKSize(root-_left, k - 1); int rightCount BinaryTreeLevelKSize(root-_right, k - 1); return leftCount rightCount; }函数测试printf(%d\n, BinaryTreeLevelKSize(BinaryTree, 3));7.二叉树查找值为x的节点遍历二叉树当该节点为空时返回NULL不为空时判断data是否与x相同相同则返回root不同则查找左右子树。函数声明// 二叉树查找值为x的节点 BTNode* BinaryTreeFind(BTNode* root, BTDataType x);函数定义// 二叉树查找值为x的节点 BTNode* BinaryTreeFind(BTNode* root, BTDataType x) { if (root NULL) { return NULL; } if (root-_data x) { return root; } else { BinaryTreeFind(root-_left, x); BinaryTreeFind(root-_right, x); } }函数测试BinaryTreeFind返回的是BTNode*所以需要通过判断返回值是否为空来判断是否找到值为x的结点。BTNode* find BinaryTreeFind(BinaryTree, C); if (find) { printf(%c\n, find-_data); } else { printf(没有找到); }8.完整代码BinaryTree.h#pragma once #includestdio.h #includestdlib.h #includeassert.h typedef char BTDataType; typedef struct BinaryTreeNode { BTDataType _data; struct BinaryTreeNode* _left; struct BinaryTreeNode* _right; }BTNode; // 通过前序遍历的数组ABD##E#H##CF##G##构建二叉树 BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi); // 二叉树销毁 void BinaryTreeDestory(BTNode** root); // 二叉树节点个数 int BinaryTreeSize(BTNode* root); // 二叉树叶子节点个数 int BinaryTreeLeafSize(BTNode* root); // 二叉树第k层节点个数 int BinaryTreeLevelKSize(BTNode* root, int k); // 二叉树查找值为x的节点 BTNode* BinaryTreeFind(BTNode* root, BTDataType x); // 二叉树前序遍历 void BinaryTreePrevOrder(BTNode* root); // 二叉树中序遍历 void BinaryTreeInOrder(BTNode* root); // 二叉树后序遍历 void BinaryTreePostOrder(BTNode* root);BinaryTree.c#define _CRT_SECURE_NO_WARNINGS 1 #includeBinaryTree.h // 通过前序遍历的数组ABD##E#H##CF##G##构建二叉树 BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi) { if (*pi n || a[*pi] #) { (*pi); return NULL; } BTNode* cur (BTNode*)malloc(sizeof(BTNode)); cur-_data a[*pi]; (*pi); cur-_left BinaryTreeCreate(a, n, pi); cur-_right BinaryTreeCreate(a, n, pi); return cur; } // 二叉树销毁 void BinaryTreeDestory(BTNode** root) { if (*root) { BinaryTreeDestory((*root)-_left); BinaryTreeDestory((*root)-_right); free(*root); *root NULL; } } // 二叉树节点个数 int BinaryTreeSize(BTNode* root) { if (root NULL) { return 0; } int leftNum BinaryTreeSize(root-_left); int rightNum BinaryTreeSize(root-_right); return leftNum rightNum 1; } // 二叉树叶子节点个数 int BinaryTreeLeafSize(BTNode* root) { if (root NULL) { return 0; } if (root-_left NULL root-_right NULL) { return 1; } int leftNum BinaryTreeLeafSize(root-_left); int rightNum BinaryTreeLeafSize(root-_right); return leftNum rightNum; } // 二叉树第k层节点个数 int BinaryTreeLevelKSize(BTNode* root, int k) { if (root NULL) { return 0; } if (k 0) { return 0; } if (k 1) { return 1; } int leftCount BinaryTreeLevelKSize(root-_left, k - 1); int rightCount BinaryTreeLevelKSize(root-_right, k - 1); return leftCount rightCount; } // 二叉树查找值为x的节点 BTNode* BinaryTreeFind(BTNode* root, BTDataType x) { if (root NULL) { return NULL; } if (root-_data x) { return root; } else { BinaryTreeFind(root-_left, x); BinaryTreeFind(root-_right, x); } } // 二叉树前序遍历 void BinaryTreePrevOrder(BTNode* root) { if (root NULL) { return; } printf(%c, root-_data); BinaryTreePrevOrder(root-_left); BinaryTreePrevOrder(root-_right); } // 二叉树中序遍历 void BinaryTreeInOrder(BTNode* root) { if (root NULL) { return; } BinaryTreeInOrder(root-_left); printf(%c, root-_data); BinaryTreeInOrder(root-_right); } // 二叉树后序遍历 void BinaryTreePostOrder(BTNode* root) { if (root NULL) { return; } BinaryTreePostOrder(root-_left); BinaryTreePostOrder(root-_right); printf(%c, root-_data); }Test.c#define _CRT_SECURE_NO_WARNINGS 1 #includeBinaryTree.h void BTreeTest() { char a[] ABD##E#H##CF##G##; int i 0; BTNode* BinaryTree BinaryTreeCreate(a, sizeof(a) / sizeof(a[0]), i); printf(%d\n, BinaryTreeSize(BinaryTree)); printf(%d\n, BinaryTreeLeafSize(BinaryTree)); printf(%d\n, BinaryTreeLevelKSize(BinaryTree, 3)); BTNode* find BinaryTreeFind(BinaryTree, C); if (find) { printf(%c\n, find-_data); } else { printf(没有找到); } BinaryTreePrevOrder(BinaryTree); printf(\n); BinaryTreeInOrder(BinaryTree); printf(\n); BinaryTreePostOrder(BinaryTree); printf(\n); BinaryTreeDestory(BinaryTree); } int main() { BTreeTest(); return 0; }完