哪个网站做的系统好用吗,如何分析网站的设计,最新房地产新闻,3d动画制作软件中文版目录 前言
二叉树的遍历
层序遍历
队列的代码 queuepush和queuepushbujia的区别
判断二叉树是否是完全二叉树
前序
中序
后序
功能展示
创建二叉树
初始化
销毁
简易功能介绍
二叉树节点个数
二叉树叶子节点个数
二叉树第k层节点个数
二叉树查找值为x的节点
判…目录 前言
二叉树的遍历
层序遍历
队列的代码 queuepush和queuepushbujia的区别
判断二叉树是否是完全二叉树
前序
中序
后序
功能展示
创建二叉树
初始化
销毁
简易功能介绍
二叉树节点个数
二叉树叶子节点个数
二叉树第k层节点个数
二叉树查找值为x的节点
判断是否为单值二叉数
判断二叉数高度 前言
本文讲解关于二叉树的创建和各种功能的实现重点讲解前中后和层序遍历的写法
层序遍历放到了本文前面先讲如果是刚接触二叉数可以先看功能展示
前中后序的遍历都用到了递归都写法
而层序遍历却不方便只能创建队列来解决
二叉树的遍历
层序遍历
层序遍历这里重点讲解一下
因为不能使用递归只好创建队列来帮助实现
队列的代码
头文件
typedef BTNode* QDataType;typedef struct QueueNode
{struct QueueNode* next;QDataType val;
}QNode;typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);// 队尾插入
void QueuePush(Queue* pq, QDataType x);
void QueuePushbujia(Queue* pq, QDataType x);
// 队头删除
void QueuePop(Queue* pq);// 取队头和队尾的数据
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);int QueueSize(Queue* pq);
bool QueueEmpty(Queue* pq);
源码
void QueueInit(Queue* pq)
{assert(pq);pq-phead NULL;pq-ptail NULL;pq-size 0;
}void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur pq-phead;while (cur){QNode* next cur-next;free(cur);cur next;}pq-phead pq-ptail NULL;pq-size 0;
}// 队尾插入
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);return;}newnode-next NULL;newnode-val x;if (pq-ptail NULL){pq-phead pq-ptail newnode;}else{pq-ptail-next newnode;pq-ptail newnode;}pq-size;
}void QueuePushbujia(Queue* pq, QDataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);return;}newnode-next NULL;newnode-val x;if (pq-ptail NULL){pq-phead pq-ptail newnode;}else{pq-ptail-next newnode;pq-ptail newnode;}
}
// 队头删除
void QueuePop(Queue* pq)
{assert(pq);assert(pq-size ! 0);/*QNode* next pq-phead-next;free(pq-phead);pq-phead next;if (pq-phead NULL)pq-ptail NULL;*/// 一个节点if (pq-phead-next NULL){free(pq-phead);pq-phead pq-ptail NULL;}else // 多个节点{QNode* next pq-phead-next;free(pq-phead);pq-phead next;}pq-size--;
}QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq-phead);return pq-phead-val;
}QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq-ptail);return pq-ptail-val;
}int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}bool QueueEmpty(Queue* pq)
{assert(pq);return pq-size 0;
}queuepush和queuepushbujia的区别
两个都是将数据尾插进去但bujia函数并不会对size加加
这样我们不仅可以正常打印N还不影响真实数据的打印
void BinaryTreeLevelOrder(BTNode* root)
{assert(root);Queue a;QueueInit(a);BTNode* n BuyNode1(root-_data);n root;BTNode* null BuyNode1(N);printf(%c , n-_data);while (1){if (n-_left ! NULL){QueuePush(a, n-_left);}else{QueuePushbujia(a,null);}if (n-_right ! NULL){QueuePush(a, n-_right);}else{QueuePushbujia(a,null);}if (QueueEmpty(a)){break;}n QueueFront(a);QueuePop(a);if (n-_data N){a.size;}printf(%c , n-_data);}
}
每拿出一个头数据时就会对size--这样的话如果为N的话很有可能会出现size减完了但实际数据没有打印完的情况
所以这里加入了判断n-_data等于N时应该让size
利用写出来的层序遍历就可以实现
判断二叉树是否是完全二叉树
i和x的作用
如果是完全二叉树遇到一个N后不可能再遇到N意外的数了
否则就是非完全二叉树
利用这一特征
当遇到第一个N时让i
如果i不等于0说明遇到过N了如果此时遇到了非N的数那么就让n
如果两个数同时不为0则为非完全二叉树
int BinaryTreeComplete(BTNode* root)
{assert(root);Queue a;QueueInit(a);BTNode* n BuyNode1(root-_data);n root;BTNode* null BuyNode1(N);//printf(%c , n-_data);char pan x;int i 0;int x 0;while (1){if (n-_left ! NULL){QueuePush(a, n-_left);}else{QueuePushbujia(a, null);}if (n-_right ! NULL){QueuePush(a, n-_right);}else{QueuePushbujia(a, null);}if (QueueEmpty(a)){break;}n QueueFront(a);QueuePop(a);if (n-_data N){a.size;}//printf(%c , n-_data);pan n-_data;if (pan N){i;}if (i !0){if (pan ! N){x;}}if (i!0x!0){return 1;}}return 0;
}
前序
void BinaryTreePrevOrder(BTNode* root)
{if (root NULL){printf(N );return;}printf(%c , root-_data);BinaryTreePrevOrder(root-_left);BinaryTreePrevOrder(root-_right);
}
中序
void BinaryTreeInOrder(BTNode* root)
{if (root NULL){printf(N);return;}BinaryTreeInOrder(root-_left);printf(%c , root-_data);BinaryTreeInOrder(root-_right);
}
后序
void BinaryTreePostOrder(BTNode* root)
{if (root NULL){printf(N);return;}BinaryTreePostOrder(root-_left);BinaryTreePostOrder(root-_right);printf(%c , root-_data);
}
功能展示
完成关于二叉树的如下功能
//初始化
BTNode* BuyNode1(BTDataType x);// 通过前序遍历的数组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);
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root);
//判断是否为单值二叉数
bool isUnivalTree(struct BTNode* root);
//判断二叉数高度
int maxDepth(struct BTNode* root);
创建二叉树
手动创建一个二叉树可以让后面的功能更方便调试
首先确定结构体内容如下
typedef char BTDataType;typedef struct BinaryTreeNode
{BTDataType _data;struct BinaryTreeNode* _left;struct BinaryTreeNode* _right;
}BTNode;
在进行手动创建一个二叉树
创建之前需要初始化结构体
初始化
//初始化
BTNode* BuyNode1(BTDataType x)
{BTNode* n (BTNode*)malloc(sizeof(BTNode));if (n NULL){perror(malloc false);return NULL;}n-_data x;n-_left NULL;n-_right NULL;return n;
}
有了初始化代码就可以正式创建二叉树了
BTNode* headadd()
{BTNode* a1 BuyNode1(a);BTNode* a2 BuyNode1(b);BTNode* a3 BuyNode1(c);BTNode* a4 BuyNode1(d);BTNode* a5 BuyNode1(e);a1-_left a2;a1-_right a3;a2-_left a4;a4-_right a5;return a1;
}
此时二叉树就建好了
有了初始化就需要有销毁防止内存泄漏
销毁
使用递归思想比较方便
void BinaryTreeDestory(BTNode** root)
{assert(root);assert(*root);BinaryTreeDestory(((*root)-_left));BinaryTreeDestory(((*root)-_right));free(*root);*root NULL;
}
简易功能介绍
大多数采用递归的方法即可轻松解决
二叉树节点个数
int BinaryTreeSize(BTNode* root)
{if (root NULL){return 0;}return 1BinaryTreeSize(root-_left)BinaryTreeSize(root-_right);
二叉树叶子节点个数
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 (root NULL||k1){return 0;}if (root!NULLk 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* lf BinaryTreeFind(root-_left, x);if (lf ! NULL){return lf;}BTNode* lr BinaryTreeFind(root-_right, x);if (lr ! NULL){return lr;}return NULL;
}
判断是否为单值二叉数
bool isUnivalTree(BTNode* root)
{if (root NULL){return true;}if (root-_left){if (root-_data! root-_left-_data){return false;}}if (!isUnivalTree(root-_left)){return false;}if (root-_right){if (root-_data ! root-_right-_data){return false;}}if (!isUnivalTree(root-_right)){return false;}return true;
}
判断二叉数高度
int maxDepth(BTNode* root)
{if (root NULL){return 0;}int leftsize maxDepth(root-_left);int rightsize maxDepth(root-_right);return leftsize rightsize ? leftsize 1 : rightsize 1;
}
