网站首页做301,网站建设冖金手指花总十四,h5制作的网站,门户网站素材文章目录 前言一、树的概念及结构1.什么是树2. 树的相关概念3.树的表示 二、二叉树概念及结构1.二叉树概念2.特殊的二叉树3.二叉树的性质4.二叉树的存储结构 三、平衡二叉树实现1.创建树和树的前中后遍历1.前中后遍历2.创建树且打印前中后遍历 2.转换为平衡二叉树和相关操作1.转… 文章目录 前言一、树的概念及结构1.什么是树2. 树的相关概念3.树的表示 二、二叉树概念及结构1.二叉树概念2.特殊的二叉树3.二叉树的性质4.二叉树的存储结构 三、平衡二叉树实现1.创建树和树的前中后遍历1.前中后遍历2.创建树且打印前中后遍历 2.转换为平衡二叉树和相关操作1.转换为平衡二叉树2.二叉树的层序遍历3.判断是否为完全二叉树4.平衡二叉树的节点删除 3.二叉树其他操作 总结 前言
在实现二叉树前我们要先对树产生一些基本的认识才可以去实现它。树的用途非常广泛向文件系统的目录树结构等。 一、树的概念及结构
1.什么是树
树是一种非线性的数据结构它是由nn0个有限结点组成一个具有层次关系的集合。有一个特殊的结点称为根结点根节点没有前驱结点。除根节点外其余结点被分成M(M0)个互不相交的集合T1、T2、……、Tm其中每一个集合Ti(1 i m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱可以有0个或多个后继。因此树是递归定义的。 如图所示 注意树形结构中子树之间不能有交集否则就不是树形结构 如图所示 这个就不可以在称为树这个构成了环形结构这个是一个图。
2. 树的相关概念 节点的度一个节点含有的子树的个数称为该节点的度。如上图A的度为3 树的深度树中节点的最大层次。如上图树的深度为4 叶子节点度为0的节点称为叶节点。如上图K为叶子节点 孩子节点一个节点含有的子树的根节点称为该节点的子节点。如上图B是A的孩子节点 兄弟节点具有相同父节点的节点互称为兄弟节点。 如上图B、C是兄弟节点 堂兄弟节点双亲在同一层的节点互为堂兄弟。如上图F、G是堂兄弟节点
3.树的表示
树结构相对线性表就比较复杂了要存储表示起来就比较麻烦了既然保存值域也要保存结点和结点之间的关系实际中树有很多种表示方式如双亲表示法孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法。
typedef int DataType;
struct Node
{struct Node* firstChild1; // 第一个孩子结点struct Node* pNextBrother; // 指向其下一个兄弟结点DataType data; // 结点中的数据域
};上面树的表示形式如下
二、二叉树概念及结构
1.二叉树概念
二叉树不存在度大于2的结点 如图所示
2.特殊的二叉树
满二叉树一个二叉树如果每一个层的结点数都达到最大值则这个二叉树就是满二叉树。 完全二叉树对于深度为K的有n个结点的二叉树当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
3.二叉树的性质
1. 若规定根节点的层数为1则一棵非空二叉树的第i层上最多有2的(i-1)次方个结点。 2. 若规定根节点的层数为1则深度为h的二叉树的最大结点数是2的h次方减1个。 3. 对任何一棵二叉树如果度为0其叶结点个数为X个 , 度为2的分支结点个数为Y个,则有XY1 4.对于具有n个结点的完全二叉树如果按照从上至下从左至右的数组顺序对所有节点从0开始编号则对 于序号为i的结点有 1.若i0i位置节点的双亲序号(i-1)/2i0i为根节点编号无双亲节点 2. 若2i1n左孩子序号2i12i1n否则无左孩子 3. 若2i2n右孩子序号2i22i2n否则无右孩子
4.二叉树的存储结构
1. 顺序存储顺序结构存储就是使用数组来存储一般使用数组只适合表示完全二叉树因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储二叉树顺序存储在物理上是一个数组在逻辑上是一颗二叉树。 2. 链式存储二叉树的链式存储结构是指用链表来表示一棵二叉树即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成数据域和左右指针域左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。 如上图所示上面二叉树的储存形式如下 链式存储的结构体如下
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;三、平衡二叉树实现
1.创建树和树的前中后遍历
1.前中后遍历
所谓二叉树遍历(Traversal)是按照某种特定的规则依次对二叉树中的节点进行相应的操作并且每个节点只操作一次。 前序遍历根左子树右子树 中序遍历左子树根右子树 后序遍历左子树右子树根 中序和后续的遍历同理。
2.创建树且打印前中后遍历
要实现的函数
//创建二叉树
void TreeCreate(BTDataType* a, int n);
// 二叉树前序遍历
void BinaryTreePrevOrder(BTNode* root);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);
// 二叉树销毁
void BinaryTreeDestory(BTNode** root);实现代码如下
//创建二叉树
void TreeCreate(BTNode** root ,BTDataType num)
{if (*root NULL)//如果节点为空证明该位置为要插入的位置{BTNode* pos (BTNode*)malloc(sizeof(BTNode));//开辟节点if (pos NULL)//判断节点是否开辟成功{perror(malloc);exit(-1);}pos-data num;pos-left NULL;pos-right NULL;*root pos;//把该节点连接到树上return;}if (num (*root)-data)//比根节点小则在左边插入{TreeCreate((*root)-left, num);}else//比根节点大则在右边插入{TreeCreate((*root)-right, num);}
}
// 二叉树前序遍历
void BinaryTreePrevOrder(BTNode* root)
{if (root NULL){return;}printf(%d , root-data);BinaryTreePrevOrder(root-left);BinaryTreePrevOrder(root-right);
}
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{if (root NULL){return;}BinaryTreeInOrder(root-left);printf(%d , root-data);BinaryTreeInOrder(root-right);
}
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{if (root NULL){return;}BinaryTreePostOrder(root-left);BinaryTreePostOrder(root-right);printf(%d , root-data);
}
// 二叉树销毁
void BinaryTreeDestory(BTNode** root)
{if (*root NULL){return;}BinaryTreeDestory((*root)-left);BinaryTreeDestory((*root)-right);free(*root);
}测试函数
void test()
{int arr[] { 2,1,3,7,6,5,9,8,4 };int size sizeof(arr) / sizeof(arr[0]);BTNode* root NULL;int i 0;for (i 0; i size; i){TreeCreate(root, arr[i]);//创建二叉树}BinaryTreePrevOrder(root);//前printf(\n);BinaryTreeInOrder(root);//中printf(\n);BinaryTreePostOrder(root);//后printf(\n);BinaryTreeDestory(root);//销毁
}
int main()
{test();return 0;
}构建的二叉树如下 前序递归部分过程如下 前序要先打印根节点的值在进行递归中序要先进行左递归在打印值最后进行右递归而后续则是先进行左右递归在打印相应的值。 注意销毁二叉树要进行后续遍历只有把根的左右子树都进行释放才可以释放根节点。根节点先于左右子树释放会找不到相应左右节点造成内存泄漏。
2.转换为平衡二叉树和相关操作
我们刚才构建的树明显一边节点多一边节点少所以我们把上面的树转化为左右子树的节点相差在1以内进行左右平衡
1.转换为平衡二叉树
// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{if (root NULL){return 0;}return BinaryTreeSize(root-left) 1 BinaryTreeSize(root-right);
}
//左旋
BTNode* get_min(BTNode* root)
{if (root-left NULL){return root;}return get_min(root-left);//返回最左边的节点
}
void turn_left(BTNode** root)
{BTNode* pos *root;(*root) pos-right;//更换头节点pos-right NULL;//避免出现野指针get_min(*root)-left pos;//把最左边的节点链接此接点
}
//右旋
BTNode* get_max(BTNode* root)
{if (root-right NULL){return root;}return get_max(root-right);//返回最右边的节点
}
void turn_right(BTNode** root)
{BTNode* pos *root;(*root) pos-left;pos-left NULL;get_max(*root)-right pos;//把最右边的节点链接此接点
}
//转换为平衡二叉树
void BalanceTree(BTNode** root)
{if (*root NULL){return;}while(1){int a BinaryTreeSize((*root)-left);int b BinaryTreeSize((*root)-right);int num BinaryTreeSize((*root)-left) - BinaryTreeSize((*root)-right);if (num -1)//右边多{//*root中和*抵消了所以传一个root就可以了但接收要用二级指针turn_left(root);//进行左旋}else if (num 1)//左边多{turn_right(root);//进行右旋}else{break;}}BalanceTree((*root)-left);//开始平衡左子树BalanceTree((*root)-right);//开始平衡右子树
}我们需要对树进行判断是否平衡就需要求出左右节点的个数我们还要对左边节点数量大于右边节点数量和右边大于左边的情况分别进行左右旋转。 这是进行一次循环当当前根节点的左右平衡时开始进行左右子树的平衡。 这样我们的平衡树就构建好了。 注意我们进行左右旋转要连接在最后一个节点上这样可以保障我们旋转后依然有序左子树的结果比根节点小右子树节点比根节点大。
2.二叉树的层序遍历
层序遍历就是按照层来访问二叉树的节点
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{Queue qu;//创建队列QueueInit(qu);//初始化队列QueuePush(qu, root);//把根节点带入while (!QueueEmpty(qu))//如果不为空则一直进行循环{BTNode*pos QueueFront(qu);// 获取队列头部元素 printf(%d , pos-data);QueuePop(qu);//头部元素出队列if(pos-left ! NULL)//如果左孩子不为空则进队列QueuePush(qu, pos-left);if (pos-right ! NULL)//如果右孩子不为空则进队列QueuePush(qu, pos-right);}QueueDestroy(qu);
}层序遍历需要我们用队列进行辅助操作 层序遍历需要我们用队列进行辅助操作由父节点来带动子节点当子节点不为空就进入队列。 测试代码
void test()
{int arr[] { 2,1,3,7,6,5,9,8,4 };int size sizeof(arr) / sizeof(arr[0]);BTNode* root NULL;int i 0;for (i 0; i size; i){TreeCreate(root, arr[i]);//创建二叉树}BalanceTree(root);//构建BinaryTreeLevelOrder(root);//层BinaryTreeDestory(root);//销毁
}
int main()
{test();return 0;
}3.判断是否为完全二叉树
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{Queue qu;//创建队列QueueInit(qu);//初始化队列QueuePush(qu, root);//把根节点带入while (!QueueEmpty(qu))//如果不为空则一直进行循环{BTNode* pos QueueFront(qu);// 获取队列头部元素 QueuePop(qu);//头部元素出队列if (pos ! NULL){QueuePush(qu, pos-left);QueuePush(qu, pos-right);}else{while (!QueueEmpty(qu))//一直出队列直到队列为空停止循环{pos QueueFront(qu);// 获取队列头部元素 if (pos ! NULL)//如果头部不为空则证明不为完全二叉树{QueueDestroy(qu);//销毁队列return false;}QueuePop(qu);//头部元素出队列}}}QueueDestroy(qu);return true;
}判断是否为完全二叉树也需要用到队列当为完全二叉树时队列不会出现数据和空交替出队列的情况而非完全二叉树会出现数据和空交替出队列的情况 测试代码如下
void test()
{int arr[] { 2,1,3,7,6,5,9,8,4 };int size sizeof(arr) / sizeof(arr[0]);BTNode* root NULL;int i 0;for (i 0; i size; i){TreeCreate(root, arr[i]);//创建二叉树}BalanceTree(root);//构建if (BinaryTreeComplete(root))//完全{printf(YES\n);}else{printf(NO\n);}BinaryTreeDestory(root);//销毁
}
int main()
{test();return 0;
}4.平衡二叉树的节点删除
//删除头节点,可以改为按查找节点删除
void DelTree(BTNode** root)//进行左旋
{BTNode* del *root;//保存要删除的元素节点*root del-left;//更换头节点get_max(*root)-right del-right;free(del);BalanceTree(root);//从新构建平衡树
}我们选择的是删除头根节点然后进行左旋从新构建成树在进行平衡树的构建。我们也可以选择删除指定的节点树的节点删除一般没有意义。 过程如下
3.二叉树其他操作
// 二叉树最深节点
int DeepTree(BTNode* root)
{if (root NULL){return 0;}//三目表达式返回左子树和右子树最大的那个return DeepTree(root-left) DeepTree(root-right) ? DeepTree(root-left) 1 : DeepTree(root-right) 1;
}
// 二叉树叶子节点个数
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);//返回左右子树的总和}
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (k 1)//从第一层开始所以递减到1就可以了{return 1;}return BinaryTreeLevelKSize(root-left, k - 1) BinaryTreeLevelKSize(root-right, k - 1);//返回左右子树的总和
}
// 二叉树查找值为x的节点
//BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
//{
// if (root NULL)//如果没找到则返回空
// {
// return NULL;
// }
// if (root-data x)
// {
// return root;
// }
// BTNode* left BinaryTreeFind(root-left, x);
// BTNode* right BinaryTreeFind(root-right, x);
// if (left NULL)//如果左子树没找到该值则返回右子树的值右子树树中也没找到返回的空找到则返回相应的节点
// {
// return right;
// }
// return left;//要找的节点在左子树上
//}
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{BTNode* pos root;while (pos ! NULL){if (pos-data x)//该节点的值小于查找的值则在树的右边{pos pos-right;}else if(pos-data x)//该节点的值大于查找的值则在树的左边{pos pos-left;}else{break;}}return pos;
}二叉树节点的查找可以用正常方式的查找也可以针对我们所构建的平衡二叉树设计一个函数我们所设计的平衡二叉树的节点都满足左孩子的值小于父节点的值右孩子的值都大于父节点的值这样设计便于我们进行查找。 测试函数
void test()
{int arr[] { 2,1,3,7,6,5,9,8,4 };int size sizeof(arr) / sizeof(arr[0]);BTNode* root NULL;int i 0;for (i 0; i size; i){TreeCreate(root, arr[i]);//创建二叉树}BalanceTree(root);//构建printf(%d\n, DeepTree(root));//深度printf(%d\n, BinaryTreeLeafSize(root));//节点个数printf(%d\n, BinaryTreeLevelKSize(root,3));//k层printf(%d\n, BinaryTreeFind(root,3)-data);//查找节点BinaryTreeDestory(root);//销毁
}
int main()
{test();return 0;
}总结
树的更加高阶的内容我们会在进一步的学习中逐步的解锁 下面是本次的全部代码 main.c:
#includemain.h
void test()
{int arr[] { 2,1,3,7,6,5,9,8,4 };int size sizeof(arr) / sizeof(arr[0]);BTNode* root NULL;int i 0;for (i 0; i size; i){TreeCreate(root, arr[i]);//创建二叉树}BinaryTreePrevOrder(root);//前printf(\n);BinaryTreeInOrder(root);//中printf(\n);BinaryTreePostOrder(root);//后printf(\n);printf(%d, BinaryTreeSize(root));//节点个数printf(\n);BalanceTree(root);//构建BinaryTreeLevelOrder(root);//层printf(\n);if (BinaryTreeComplete(root))//完全{printf(YES\n);}else{printf(NO\n);}printf(%d\n, DeepTree(root));//深度printf(%d\n, BinaryTreeLeafSize(root));//节点个数printf(%d\n, BinaryTreeLevelKSize(root,3));//k层printf(%d\n, BinaryTreeFind(root,3)-data);//查找节点DelTree(root);BinaryTreeLevelOrder(root);//层BinaryTreeDestory(root);//销毁
}
int main()
{test();return 0;
}main.h:
#pragma once
#define _CRT_SECURE_NO_WARNINGS
#includestdio.h
#includestdlib.h
#includestdbool.h
#includeassert.h
typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;
// 链式结构表示队列
typedef BTNode* QDataType;
typedef struct QListNode
{struct QListNode* next;QDataType data;
}QNode;
// 队列的结构
typedef struct Queue
{QNode* front;QNode* rear;
}Queue;
// 初始化队列
void QueueInit(Queue* q);
// 队尾入队列
void QueuePush(Queue* q, QDataType data);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QDataType* QueueFront(Queue* q);
// 检测队列是否为空如果为空返回非零结果如果非空返回0
bool QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);
//创建二叉树
void TreeCreate(BTDataType* a, int n);
// 二叉树前序遍历
void BinaryTreePrevOrder(BTNode* root);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);
// 二叉树销毁
void BinaryTreeDestory(BTNode** root);
// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
//转换为平衡二叉树
void BalanceTree(BTNode** root);
//删除头节点
void DelTree(BTNode** root);
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root);
// 二叉树最深节点
int DeepTree(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);test.c:
#includemain.h// 初始化队列
void QueueInit(Queue* q)
{assert(q);q-front q-rear NULL;
}
// 队尾入队列
void QueuePush(Queue* q, QDataType data)
{assert(q);QNode* pos (QNode*)malloc(sizeof(QNode));if (pos NULL){perror(malloc);exit(-1);}pos-data data;pos-next NULL;if (q-rear NULL){q-front q-rear pos;}else{q-rear-next pos;q-rear pos;}
}
// 队头出队列
void QueuePop(Queue* q)
{assert(q);assert(q-front);if (q-front-next NULL){free(q-front);q-front q-rear NULL;}else{QNode* next q-front-next;free(q-front);q-front next;}
}
// 获取队列头部元素
QDataType* QueueFront(Queue* q)
{assert(q);assert(q-front);return q-front-data;
}
// 检测队列是否为空如果为空返回非零结果如果非空返回0
bool QueueEmpty(Queue* q)
{assert(q);return q-front NULL;
}
// 销毁队列
void QueueDestroy(Queue* q)
{assert(q);QNode* pos q-front;while (pos){QNode* next pos-next;free(pos);pos next;}q-front q-rear NULL;
}
//创建二叉树
void TreeCreate(BTNode** root ,BTDataType num)
{if (*root NULL)//如果节点为空证明该位置为要插入的位置{BTNode* pos (BTNode*)malloc(sizeof(BTNode));//开辟节点if (pos NULL)//判断节点是否开辟成功{perror(malloc);exit(-1);}pos-data num;pos-left NULL;pos-right NULL;*root pos;//把该节点连接到树上return;}if (num (*root)-data)//比根节点小则在左边插入{TreeCreate((*root)-left, num);}else//比根节点大则在右边插入{TreeCreate((*root)-right, num);}
}
// 二叉树前序遍历
void BinaryTreePrevOrder(BTNode* root)
{if (root NULL){return;}printf(%d , root-data);BinaryTreePrevOrder(root-left);BinaryTreePrevOrder(root-right);
}
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{if (root NULL){return;}BinaryTreeInOrder(root-left);printf(%d , root-data);BinaryTreeInOrder(root-right);
}
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{if (root NULL){return;}BinaryTreePostOrder(root-left);BinaryTreePostOrder(root-right);printf(%d , root-data);
}
// 二叉树销毁
void BinaryTreeDestory(BTNode** root)
{if (*root NULL){return;}BinaryTreeDestory((*root)-left);BinaryTreeDestory((*root)-right);free(*root);
}
// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{if (root NULL){return 0;}return BinaryTreeSize(root-left) 1 BinaryTreeSize(root-right);
}
//左旋
BTNode* get_min(BTNode* root)
{if (root-left NULL){return root;}return get_min(root-left);//返回最左边的节点
}
void turn_left(BTNode** root)
{BTNode* pos *root;(*root) pos-right;//更换头节点pos-right NULL;//避免出现野指针get_min(*root)-left pos;//把最左边的节点链接此接点
}
//右旋
BTNode* get_max(BTNode* root)
{if (root-right NULL){return root;}return get_max(root-right);//返回最右边的节点
}
void turn_right(BTNode** root)
{BTNode* pos *root;(*root) pos-left;pos-left NULL;get_max(*root)-right pos;//把最右边的节点链接此接点
}
//转换为平衡二叉树
void BalanceTree(BTNode** root)
{if (*root NULL){return;}while(1){int a BinaryTreeSize((*root)-left);int b BinaryTreeSize((*root)-right);int num BinaryTreeSize((*root)-left) - BinaryTreeSize((*root)-right);if (num -1)//右边多{//*root中和*抵消了所以传一个root就可以了但接收要用二级指针turn_left(root);//进行左旋}else if (num 1)//左边多{turn_right(root);//进行右旋}else{break;}}BalanceTree((*root)-left);//开始平衡左子树BalanceTree((*root)-right);//开始平衡右子树
}
//删除头节点,可以改为按查找节点删除
void DelTree(BTNode** root)//进行左旋
{BTNode* del *root;//保存要删除的元素节点*root del-left;//更换头节点get_max(*root)-right del-right;free(del);BalanceTree(root);//从新构建平衡树
}
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{Queue qu;//创建队列QueueInit(qu);//初始化队列QueuePush(qu, root);//把根节点带入while (!QueueEmpty(qu))//如果不为空则一直进行循环{BTNode*pos QueueFront(qu);// 获取队列头部元素 printf(%d , pos-data);QueuePop(qu);//头部元素出队列if(pos-left ! NULL)//如果左孩子不为空则进队列QueuePush(qu, pos-left);if (pos-right ! NULL)//如果右孩子不为空则进队列QueuePush(qu, pos-right);}QueueDestroy(qu);
}
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{Queue qu;//创建队列QueueInit(qu);//初始化队列QueuePush(qu, root);//把根节点带入while (!QueueEmpty(qu))//如果不为空则一直进行循环{BTNode* pos QueueFront(qu);// 获取队列头部元素 QueuePop(qu);//头部元素出队列if (pos ! NULL){QueuePush(qu, pos-left);QueuePush(qu, pos-right);}else{while (!QueueEmpty(qu))//一直出队列直到队列为空停止循环{pos QueueFront(qu);// 获取队列头部元素 if (pos ! NULL)//如果头部不为空则证明不为完全二叉树{QueueDestroy(qu);//销毁队列return false;}QueuePop(qu);//头部元素出队列}}}QueueDestroy(qu);return true;
}
// 二叉树最深节点
int DeepTree(BTNode* root)
{if (root NULL){return 0;}//三目表达式返回左子树和右子树最大的那个return DeepTree(root-left) DeepTree(root-right) ? DeepTree(root-left) 1 : DeepTree(root-right) 1;
}
// 二叉树叶子节点个数
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);//返回左右子树的总和}
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (k 1)//从第一层开始所以递减到1就可以了{return 1;}return BinaryTreeLevelKSize(root-left, k - 1) BinaryTreeLevelKSize(root-right, k - 1);//返回左右子树的总和
}
// 二叉树查找值为x的节点
//BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
//{
// if (root NULL)//如果没找到则返回空
// {
// return NULL;
// }
// if (root-data x)
// {
// return root;
// }
// BTNode* left BinaryTreeFind(root-left, x);
// BTNode* right BinaryTreeFind(root-right, x);
// if (left NULL)//如果左子树没找到该值则返回右子树的值右子树树中也没找到返回的空找到则返回相应的节点
// {
// return right;
// }
// return left;//要找的节点在左子树上
//}
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{BTNode* pos root;while (pos ! NULL){if (pos-data x)//该节点的值小于查找的值则在树的右边{pos pos-right;}else if(pos-data x)//该节点的值大于查找的值则在树的左边{pos pos-left;}else{break;}}return pos;
}
