公益网站建设的意义,it外包运维服务,南宁市建设工程质量安全协会网站,申请注册公司需要什么材料个人主页~ 链式二叉树基本内容~ 链式二叉树详解 1、通过前序遍历的数组来构建二叉树2、二叉树的销毁3、二叉树节点个数4、二叉树叶子节点个数5、二叉树第k层节点个数6、二叉树查找7、前序遍历8、中序遍历9、后序遍历10、层序遍历与检查二叉树是否为完全二叉树Queue.hQueue.c层序… 个人主页~ 链式二叉树基本内容~ 链式二叉树详解 1、通过前序遍历的数组来构建二叉树2、二叉树的销毁3、二叉树节点个数4、二叉树叶子节点个数5、二叉树第k层节点个数6、二叉树查找7、前序遍历8、中序遍历9、后序遍历10、层序遍历与检查二叉树是否为完全二叉树Queue.hQueue.c层序遍历代码完全二叉树判断 整个链式二叉树以递归定义为主需要详细了解递归的相关概念递归定义在第六条 最需要记住的是递归定义中的return是退出到上一级而不是整个程序
1、通过前序遍历的数组来构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a,int n, int* pi)
{if (*pi n || a[*pi] #){ // 如果到达数组末尾或遇到#则返回NULL (*pi);//移动到下一个数据return NULL;}BTNode* node BuyNode(a[*pi]);(*pi); // 移动到下一个数据node-left BinaryTreeCreate(a, n, pi); // 递归创建左子树 node-right BinaryTreeCreate(a, n, pi); // 递归创建右子树 return node;
}建树过程部分过程省略 2、二叉树的销毁
二叉树销毁是不能够从第一层开始销毁的这样我们不能销毁所有的节点从叶节点开始销毁递归释放才能销毁二叉树所有节点
void BinaryTreeDestory(BTNode* root)
{if (root NULL)return;BinaryTreeDestory(root-left);//找到底层左节点BinaryTreeDestory(root-right);//找完左节点找右节点free(root);
}找到D的左子结点是#返回再找D的右节点是#返回然后释放掉D节点此时B的root-left结束进行root-right以此类推这样会从最底下的叶节点开始将所有节点释放
3、二叉树节点个数
int BinaryTreeSize(BTNode* root)
{//return root NULL ? 0 : BinaryTreeSize(root-left) BinaryTreeSize(root-right) 1;if (root NULL)return 0;return BinaryTreeSize(root-left) BinaryTreeSize(root-right) 1;
}两种表达方式一种是普通表达另一种是三目表达 如果当前节点为空返回0如果左右子节点都遍历完了将结果1返回 递归走到D的左子结点返回到Dreturn 0 右子节点返回到Dreturn 0 函数走完返回到Breturn 001 以此类推
4、二叉树叶子节点个数
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 将左子树的叶节点与右子树的叶节点相加就是二叉树总共的叶子结点个数 A走到BB走到DD的左右节点都为空D是叶子结点返回1返回到B 再走E的左子结点为空返回0走E节点E节点的左右子节点为空为叶子节点返回1以此类推
5、二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{assert(k 0);if (root NULL)return 0;if (k 1)return 1;return BinaryTreeLevelKSize(root-left, k - 1) BinaryTreeLevelKSize(root-right, k - 1);
}当节点为0时返回0 当k为1时只有根节点返回1 每次递归会使k减1到第k层时k1然后就开始返回这样递归的定义可以保证第k层的所有个数都可以算到 当我们想要求第三层的节点个数时我们找到BC两棵子树此时对于BC来说它们需要找到它第二层的节点个数再向下递归此时k1将它们不为空的节点返回1
6、二叉树查找
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root NULL)return NULL;if (root-data x)return root;BTNode* ret1 BinaryTreeFind(root-left, x);if (ret1)return ret1;//不为空就返回BTNode* ret2 BinaryTreeFind(root-right, x);if (ret2)return ret2;//不为空就返回return NULL;
}当节点为空时返回空 当节点数据为想要查找的数据时返回该节点指针 递归调用当左子树中存在这个数时ret1不为空返回的就是那个值右子树同上都没有就返回空
7、前序遍历
void BinaryTreePrevOrder(BTNode* root)
{if (root NULL){printf(N );return;}printf(%c , root-data);BinaryTreePrevOrder(root-left);BinaryTreePrevOrder(root-right);
}前序遍历的顺序根节点-左子树-右子树 先将根节点A打印之后递归到左子结点B打印B递归到B的左子结点D打印DD的左子节点为空打印N查看右子节点也为空打印N返回到B查看右子结点打印E以此类推
8、中序遍历
void BinaryTreeInOrder(BTNode* root)
{if (root NULL){printf(N );return;}BinaryTreeInOrder(root-left);printf(%c , root-data);BinaryTreeInOrder(root-right);
}中序遍历顺序左子树-根-右子树 A到BB到DD到最底的左子节点为空打印N再打印根D右子节点为空打印N然后回到B看E以此类推
9、后序遍历
void BinaryTreePostOrder(BTNode* root)
{if (root NULL){printf(N );return;}BinaryTreeInOrder(root-left);BinaryTreeInOrder(root-right);printf(%c , root-data);
}后序遍历顺序左子树-右子树-根 A到BB到DD到最底的左子节点为空打印N看D的右子节点为空打印N最后打印D 去到B的右子节点E以此类推
10、层序遍历与检查二叉树是否为完全二叉树
层序遍历即一层一层的遍历从第一层开始此时我们需要一个队列因为队列可以实现先入先出并且可以存储数据
Queue.h
#pragma once#include stdio.h
#include stdlib.h
#include assert.htypedef struct BinaryTreeNode* QDataType;// 链式结构表示队列
typedef struct QListNode
{struct QListNode* pNext;QDataType data;
}QNode;
// 队列的结构
typedef struct Queue
{QNode* front;QNode* rear;int size;
}Queue;
// 初始化队列
void QueueInit(Queue* q);
// 队尾入队列
void QueuePush(Queue* q, QDataType node);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QDataType QueueFront(Queue* q);
// 检测队列是否为空如果为空返回非零结果如果非空返回0
int QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);Queue.c
队列我就不添加注释了前边的文章-栈和队列中都有可以自行翻阅
#include Queue.hvoid QueueInit(Queue* q)
{assert(q);q-front q-rear NULL;q-size 0;
}void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail\n);return;}newnode-data x;newnode-pNext NULL;if (pq-rear NULL){assert(pq-front NULL);pq-front pq-rear newnode;}else{pq-rear-pNext newnode;pq-rear newnode;}pq-size;
}void QueuePop(Queue* q)
{assert(q);assert(!QueueEmpty(q));if (q-front-pNext NULL){free(q-front);q-front q-rear NULL;}else{QNode* next q-front-pNext;free(q-front);q-front next;}q-size--;
}QDataType QueueFront(Queue* q)
{assert(q);assert(!QueueEmpty(q));if (q-front NULL){return NULL;}return q-front-data;
}int QueueEmpty(Queue* q)
{assert(q);return q-size 0;
}void QueueDestroy(Queue* q)
{assert(q);QNode* pur q-front;while (pur){QNode* next pur-pNext;free(pur);pur next;}q-front q-rear NULL;q-size 0;
}层序遍历代码
void BinaryTreeLevelOrder(BTNode* root)
{Queue q;QueueInit(q);if (root)QueuePush(q, root);//把根节点作为队列的队头while (!QueueEmpty(q)){BTNode* front QueueFront(q);//将要出队的队头数据存储一下QueuePop(q);//将队头弹出printf(%c , front-data);//打印被存储的队头数据if (front-left)QueuePush(q, front-left);if (front-right)QueuePush(q, front-right);}//从队头开始检查左右子节点若不为空则添加入队printf(\n);QueueDestroy(q);
}完全二叉树判断
int BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(q);if (root)QueuePush(q, root);while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);
//到此的解释如上层序遍历同if (front NULL)break;
// 遇到空就跳出只要有空后面也是空的话那就是完全二叉树如果后面不都为空那么就不是QueuePush(q, front-left);QueuePush(q, front-right);//将空之前的数据全部入队}// 检查后面的节点有没有非空while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);if (front){QueueDestroy(q);return 0;}}QueueDestroy(q);return 1;
}今日分享完毕瑞思拜~
