文章目录

  • 一、二叉树的概念
  • 二、特殊的二叉树
  • 三、二叉树的性质
  • 四、二叉树的存储结构
  • 五、二叉树链式结构实现
    • （1）创建结构体
    • （2）具体函数实现及实现
      • 1.0 二叉树的构建
      • 1.1 二叉树的销毁
      • 1.2 二叉树节点个数
      • 1.3 二叉树叶子结点个数
      • 1.4 二叉树第k层节点个数
      • 1.5 二叉树查找值为x的节点
      • 1.6 二叉树的高度
      • 1.7 二叉树前序遍历
      • 1.8 二叉树中序遍历
      • 1.9 二叉树后序遍历
      • 2.0 层序遍历
      • 2.1 判断二叉树是否是完全二叉树
    • （3）二叉树实现代码
      • （1）Queue.c
      • （2）Queue.h
      • （3）test.c
      • （4）BinaryTree.h
      • （5）BinaryTree.c
    • （4）二叉树测试结果

一、二叉树的概念

一棵二叉树是结点的一个有限集合，该集合分为两点: 一是为空和二是由一个根节点加上两棵别称为左子树和右子树的二叉树组成从图上看出有2个性质：

  1. 二叉树不存在度大于2的结点
  2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

对于任意的二叉树都是由以下几种情况复合而成的：

二、特殊的二叉树

1、 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是 说，如果一个二叉树的层数为K，且结点总数是 ，则它就是满二叉树。

2、完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K 的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。

如图：

三、二叉树的性质

二叉树数的性质有五点：

  1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1) 个结点.
  2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是 2^h-1
  3. 对任何一棵二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为n2 ,则有 n0＝n2 ＋1
  4. 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=log(n+1) ( 是log以2 为底，n+1为对数)
  5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对 于序号为i的结点有:
    若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点
    若2i+1=n否则无左孩子
    若2i+2=n否则无右孩子

四、二叉树的存储结构

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。
1、顺序存储：
顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

2、链式存储
二叉树的链式存储结构：是用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链，这只讲二叉链。

五、二叉树链式结构实现

（1）创建结构体

typedef int BTDataType;typedef struct BinaryTreeNode{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;}BTNode;

先使用typedef int BTDataType,是为了方便改类型，在结构体里创建3个成员变量，BTDataType a，表示结点数据。struct BinaryTreeNode* left表示存储结点左孩子的地址，struct BinaryTreeNode* right表示存储结点右孩子的地址。

（2）具体函数实现及实现

1.0 二叉树的构建

BTNode* BuyBTNode(BTDataType x)//二叉树的构建{ BTNode* node = (struct BTNode*) malloc(sizeof(BTNode));if (node == NULL){perror("malloc fail");exit(-1);}node->data = x;node->left = NULL;node->right = NULL;return node;}

二叉树构建也就是为每一个结点申请空间，用malloc开辟，地址放在node变量中，如果改指针为空就exit,接着把数据值放到结点数据里，把2它的左右孩子都置为空。

1.1 二叉树的销毁

void BinaryTreeDestory(BTNode* root)//二叉树的销毁{if (root){BinaryTreeDestory(root->left);BinaryTreeDestory(root->right);free(root);}}

二叉树销毁根节点为空就不用销毁，反之，先递归释放左子树，再递归释放右子树，最后释放结点，如果先释放结点，会找不到左右子树的地址。

1.2 二叉树节点个数

int BinaryTreeSize(BTNode* root)// 二叉树节点个数{if (root == NULL){return 0;}return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;}

求二叉树结点个数需要递归左子树和右子树，去建立栈帧，直到它们的子树为空返回0，之后再加1，表示记录一个结点，然后从下到上开始return返回，栈帧逐层销毁，最终返回结点个数。

1.3 二叉树叶子结点个数

int BinaryTreeLeafSize(BTNode* root)//二叉树叶子结点个数{if (root == NULL){return 0;}if (root->left==NULL&&root->right == NULL){return 1;}return  BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);}

求叶子结点个数，也就是求同时没有左右孩子的结点，思路还是递归左子树和右子树，之和即为最终的叶子节点个数。如果结点为空直接返回0，如果它们的左右孩子都为空，则表示它是叶子结点，返回1，最后递归返回总个数。

1.4 二叉树第k层节点个数

int BinaryTreeLevelKSize(BTNode* root, int k)// 二叉树第k层节点个数{if (root == NULL){return 0;}if (k == 1){return 1;}return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);}

求第k层个数，从二叉树结构可以发现，如果k=1，他自己就是第k层，如果k>1,第k层就等于左子树k-1层个数加右子树第k-1层个数，相对位置往下走，层层递进，一直减到1，就是第k层。同样递归左右子树，最后返回最终第k层结点个数。

1.5 二叉树查找值为x的节点

struct BinaryTreeNode* BinaryTreeFind(BTNode* root, BTDataType x)// 二叉树查找值为x的节点{if (root == NULL){return NULL;}if (root->data == x){return root;}struct BinaryTreeNode* ret1 = BinaryTreeFind(root->left, x);if (ret1)return ret1;struct BinaryTreeNode* ret2 = BinaryTreeFind(root->right, x);if (ret2)return ret2;}

二叉树查找，如果结点为空，返回空，如果找到直接返回结点指针，没找到继续分别递归左右子树，为了防止返回出现随机值，这里需要接收一下指针，如果找到返回该结点指针。

1.6 二叉树的高度

int BinaryTreeHeight(BTNode* root)//二叉树的高度{if (root == NULL){return 0;}int leftheight = BinaryTreeHeight(root->left);int rightheight = BinaryTreeHeight(root->right);return leftheight > rightheight " />