手机网站的模板下载,电子政务门户网站建设汇报,做门户网站开发的技术,建设银行网站维修图片必须有为成功付出代价的决心#xff0c;然后想办法付出这个代价。云边有个稻草人-CSDN博客 这节课挺抽象#xff08;苦笑#xff09;#xff0c;没事#xff0c;我会帮你#xff01;干就完了#xff01;
#xff08;目录在路上#xff09; 正文开始—— 引言
用链表… 必须有为成功付出代价的决心然后想办法付出这个代价。云边有个稻草人-CSDN博客 这节课挺抽象苦笑没事我会帮你干就完了
目录在路上 正文开始—— 引言
用链表来表示一棵二叉树即用链来指示元素的逻辑关系。通常的方法是链表中每个结点有三个域组成数据域和左右指针域左右指针分别用来给出该结点左孩子和右孩子所在链结点的存储地址结构见下
//创建链式结构二叉树的结构-二叉链
typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType* data;struct BinaryTreeNode* left;//指定当前结点的左孩子struct BinaryTreeNode* right;//指定当前结点的右孩子
}BTNode;
二叉树的创建方式比较复杂为了更好地步入到二叉树内容中我们先手动创建一棵链式二叉树。
//申请结点
BTNode* BuyNode(BTDataType x)
{BTNode* newnode (BTNode*)malloc(sizeof(BTNode));if (newnode NULL){perror(malloc faile!);exit(1);}newnode-data x;newnode-left newnode-right NULL;return newnode;
}BTNode* CreateTree()
{BTNode* node1 BuyNode(1);BTNode* node2 BuyNode(2);BTNode* node3 BuyNode(3);BTNode* node4 BuyNode(4);//改变指针指向使其成为一棵链式二叉树node1-left node2;node1-right node3;node2-left node4;return node1;}
回顾二叉树的概念二叉树分为空树和非空二叉树非空二叉树由根节点、根节点的左子树和根节点的右子树组成的。 根节点的左子树和右子树分别又是由子树节点、子树结点的左子树和子树结点的右子树组成的因此二叉树是递归式的后序链式二叉树的操作基本都是按照概念实现的。 一、前中后序遍历
1.1 遍历规则
按照规则二叉树的遍历有前序 /中序/ 后序的遍历结构
前序遍历Preorder Traversal 亦称先序遍历访问根结点的操作发生在遍历其左右子树之前访问的顺序根节点、左子树、右子树中序遍历Inorder Traversal访问根节点的操作发生在遍历其左右子树之间访问顺序左子树、根节点、右子树后序遍历Postorder Traversal访问根节点的操作发生在遍历其左右子树之后访问顺序左子树、右子树、根节点 1.2 代码实现
1前序遍历
//前序遍历
void PreOrder(BTNode* root)
{if (root NULL){return;}printf(%d , root-data);PreOrder(root-left);PreOrder(root-right);
}该图里面前序遍历结果为1 2 4 3 2中序遍历
//中序遍历--左根右
void InOrder(BTNode* root)
{if (root NULL){return;}InOrder(root-left);printf(%d , root-data);InOrder(root-right);
}
中序遍历结果为4 2 1 3 3后序遍历
//后序遍历--左右根
void PosOrder(BTNode* root)
{if (root NULL){return;}PosOrder(root-left);PosOrder(root-right);printf(%d , root-data);
} 二、结点个数以及高度等
2.1 二叉树结点个数 //求二叉树节点的个数
int BinaryTreeSize(BTNode* root)
{if (root NULL){return 0;}return 1 BinaryTreeSize(root-left) BinaryTreeSize(root-right);
}
2.2 二叉树叶子结点的个数 //二叉树叶子结点个数
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);
}2.3 二叉树第K层结点的个数 //第K层节点个数
int BinaryTreeLevelKSize(BTNode* root,int k)
{if (root NULL){return 0;}if (k 1){return 1;}return BinaryTreeLevelKSize(root-left, k - 1) BinaryTreeLevelKSize(root-right, k - 1);
}
2.4 求二叉树的高度/深度 //求二叉树高度/深度
int BinaryTreeDepth(BTNode* root)
{if (root NULL){return 0;}int leftDep BinaryTreeDepth(root-left);int rightDep BinaryTreeDepth(root-right);return leftDep rightDep ? leftDep 1 : rightDep 1;
}
2.5 二叉树查找值为x的节点 //二叉树找值为x的结点
BTNode* BinaryFind(BTNode* root, BTDataType x)
{if (root NULL){return NULL;}if (root-data x){return root;}BTNode* leftFind BinaryFind(root-left, x);if (leftFind){return leftFind;}BTNode* rightFind BinaryFind(root-right, x);if (rightFind){return rightFind;}return NULL;
}
2.6 二叉树的销毁 //二叉树的销毁
void BinaryTreeDestroy(BTNode** root)
{if (*root NULL){return;}BinaryTreeDestroy(((*root)-left));//注意这里的传参传的是地址BinaryTreeDestroy(((*root)-right));free(*root);*root NULL;
} 三、层序遍历 除了先序遍历、中序遍历、后序遍历外还可以对⼆叉树进行层序遍历。设⼆叉树的根结点所在层数为1层序遍历就是从所在⼆叉树的根结点出发⾸先访问第⼀层的树根结点然后从左到右访问第2层上的结点接着是第三层的结点 以此类推⾃上⽽下⾃左⾄右逐层访问树的结点的过程就是层序遍历。 我们要提前实现一个队列的结构1在下面的函数里面我们创建一个队列并且别忘记队列的初始化和销毁2同时要注意我们前面学习的队列里面的数据是整型类型这次我们要将结点插入到队列里面所以我们要将队列里面的数据类型改为二叉树节点的类型并且我们不能直接写二叉树节点的缩写那样我们要写成 struct BinaryTreeNode* / struct BTNode* 反正都不能少 struct不然会报错。3还有一点在我们的层序遍历代码里面当while循环结束的时候队列为NULL下一步再进行队列的销毁的时候就会报错因为我们前面实现的队列的销毁里面队列为空时不能销毁所以assert会报错所以我们可以把队列的销毁里面判断队列是否为空的那一步给注释掉。
提及到的代码需要注意的点都在下面多看看
//创建节点的结构
typedef struct BinaryTreeNode* QUDatatype;//这里需要注意
typedef struct QueueNode
{QUDatatype data;struct QueueNode* next;
}QueueNode;
//销毁
void QueueDestroy(Queue* pq)
{assert(pq);//assert(!QueueEmpty(pq));//往这看注释掉这里也没事就算队列为空也没关系//此时pcur为NULL进不去循环QueueNode* pcur pq-phead;while (pcur){QueueNode* next pcur-next;free(pcur);pcur next;}pq-phead pq-ptail NULL;pq-size 0;
}//层序遍历
void LevelBinaryTree(BTNode* root)
{//先创建一个队列Queue q;QueueInit(q);//取根节点入队列QueuePush(q, root);while (!QueueEmpty(q)){//打印队头数据BTNode* Front QueueFront(q);printf(%d , Front-data);QueuePop(Front);if (Front-left){QueuePush(q, Front-left);}if (Front-right){QueuePush(q, Front-right);}}QueueDestroy(q);
} 四、判断是否是完全二叉树
//判断是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(q);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 ! NULL){QueueDestroy(q);return false;}}QueueDestroy(q);return true;
}【图解】 五、本节课代码汇总 Queue.h
#pragma once
#includestdbool.h
#includestdio.h
#includestdlib.h
#includeassert.h//创建节点的结构
typedef struct BinaryTreeNode* QUDatatype;
typedef struct QueueNode
{QUDatatype data;struct QueueNode* next;
}QueueNode;//创建队列的结构
typedef struct Queue
{QueueNode* phead;QueueNode* ptail;int size;
}Queue;//初始化
void QueueInit(Queue* pq);//入队列
void QueuePush(Queue* pq,QUDatatype x);//判空
bool QueueEmpty(Queue* pq);//出队列
void QueuePop(Queue* pq);//取队头数据
QUDatatype QueueTop(Queue* pq);//去队尾数据
QUDatatype QueueBack(Queue* pq);//去队列中有效数据的个数
int QueueSize(Queue* pq);//销毁
void QueueDestroy(Queue* pq);
Queue.c
#includeQueue.hvoid QueueInit(Queue* pq)
{assert(pq);pq-phead pq-ptail NULL;pq-size 0;
}//入队列
void QueuePush(Queue* pq, QUDatatype x)
{assert(pq);//现申请新的结点QueueNode* newnode (QueueNode*)malloc(sizeof(QueueNode));if (newnode NULL){perror(malloc fail!);exit(1);}newnode-data x;newnode-next NULL;//如果为空if (pq-phead NULL){pq-phead pq-ptail newnode;}else{pq-ptail-next newnode;pq-ptail newnode;}pq-size;
}//判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-phead NULL;
}//出队列
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq-phead pq-ptail){free(pq-phead);pq-phead pq-ptail NULL;}else{QueueNode* pcur pq-phead-next;free(pq-phead);pq-phead pcur;}pq-size--;
}//取队头数据
QUDatatype QueueTop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-phead-data;}//去队尾数据
QUDatatype QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-ptail-data;
}int QueueSize(Queue* pq)
{assert(pq);/*QueueNode* pcur pq-phead;int count 0;while (pcur){count;QueuePop(pq);pcur pq-phead;}*//*return count;*/return pq-size;
}//销毁
void QueueDestroy(Queue* pq)
{assert(pq);//assert(!QueueEmpty(pq));QueueNode* pcur pq-phead;while (pcur){QueueNode* next pcur-next;free(pcur);pcur next;}pq-phead pq-ptail NULL;pq-size 0;
}
Tree.h
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.h//创建链式结构二叉树的结构-二叉链
typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;//指定当前节点的左孩子struct BinaryTreeNode* right;//指定当前节点的右孩子
}BTNode;//申请节点
BTNode* BuyNode(BTDataType x);//前序遍历
void PreOrder(BTNode* root);//中序遍历
void InOrder(BTNode* root);//后序遍历
void PosOrder(BTNode* root);//求二叉树节点的个数
int BinaryTreeSize(BTNode* root);//二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* root);//第K层节点个数
int BinaryTreeLevelKSize(BTNode* root,int k);//求二叉树高度/深度
int BinaryTreeDepth(BTNode* root);//找X的结点
BTNode* BinaryFind(BTNode* root, BTDataType x);//二叉树的销毁
void BinaryTreeDestroy(BTNode** root);//层序遍历
void LevelBinaryTree(BTNode* root);//判断是否是完全二叉树
bool BinaryTreeComplete(BTNode* root);
Tree.c
#includeTree.h
#includeQueue.h//申请节点
BTNode* BuyNode(BTDataType x)
{BTNode* newnode (BTNode*)malloc(sizeof(BTNode));if (newnode NULL){perror(malloc faile!);exit(1);}newnode-data x;newnode-left newnode-right NULL;return newnode;
}//前序遍历-
void PreOrder(BTNode* root)
{if (root NULL){return;}printf(%d , root-data);PreOrder(root-left);PreOrder(root-right);
}//中序遍历--左根右
void InOrder(BTNode* root)
{if (root NULL){return;}InOrder(root-left);printf(%d , root-data);InOrder(root-right);
} //后序遍历--左右根
void PosOrder(BTNode* root)
{if (root NULL){return;}PosOrder(root-left);PosOrder(root-right);printf(%d , root-data);
}//求二叉树节点的个数
int BinaryTreeSize(BTNode* root)
{if (root NULL){return 0;}return 1 BinaryTreeSize(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){return 0;}if (k 1){return 1;}return BinaryTreeLevelKSize(root-left, k - 1) BinaryTreeLevelKSize(root-right, k - 1);
}//求二叉树高度/深度
int BinaryTreeDepth(BTNode* root)
{if (root NULL){return 0;}int leftDep BinaryTreeDepth(root-left);int rightDep BinaryTreeDepth(root-right);return leftDep rightDep ? leftDep 1 : rightDep 1;
}//二叉树找值为x的结点
BTNode* BinaryFind(BTNode* root, BTDataType x)
{if (root NULL){return NULL;}if (root-data x){return root;}BTNode* leftFind BinaryFind(root-left, x);if (leftFind){return leftFind;}BTNode* rightFind BinaryFind(root-right, x);if (rightFind){return rightFind;}return NULL;
}//二叉树的销毁
void BinaryTreeDestroy(BTNode** root)
{if (*root NULL){return;}BinaryTreeDestroy(((*root)-left));BinaryTreeDestroy(((*root)-right));free(*root);*root NULL;
}//层序遍历
void LevelBinaryTree(BTNode* root)
{//先创建一个队列Queue q;QueueInit(q);//取根节点入队列QueuePush(q, root);while (!QueueEmpty(q)){//打印队头数据BTNode* Front QueueFront(q);printf(%d , Front-data);QueuePop(Front);if (Front-left){QueuePush(q, Front-left);}if (Front-right){QueuePush(q, Front-right);}}QueueDestroy(q);
}//判断是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(q);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 ! NULL){QueueDestroy(q);return false;}}QueueDestroy(q);return true;
} test.c
#includeTree.hBTNode* CreateTree()
{BTNode* node1 BuyNode(1);BTNode* node2 BuyNode(2);BTNode* node3 BuyNode(3);BTNode* node4 BuyNode(4);node1-left node2;node1-right node3;node2-left node4;return node1;}int main()
{BTNode* node CreateTree();/*PreOrder(node);printf(\n);InOrder(node);printf(\n);PosOrder(node);*/printf(NodeSize:%d\n, BinaryTreeSize(node));printf(NodeSize:%d\n, BinaryTreeSize(node));printf(NodeSize:%d\n, BinaryTreeSize(node));printf(LeafSize%d\n, BinaryTreeLeafSize(node));printf(%d\n, BinaryTreeLevelKSize(node, 3));printf(%d\n, BinaryTreeDepth(node));BTNode* find BinaryFind(node, 22);printf(%s\n, find NULL ? 没找到\n : 找到了\n);LevelBinaryTree(node);bool ret BinaryTreeComplete(node);printf(%s\n, ret false ? 不是完全二叉树\n : 是完全二叉树\n);BinaryTreeDestroy(node);return 0;
} 我感觉这节递归还是挺难理解的感觉函数递归进行的过程不好想象层层递归就比较难以理解透彻我会忘记自己递归到那个地方了绕不回去了就很烧脑筋难想的时候呢我就得画出函数进行栈帧的创建与销毁这样一步一步来还是比较好的。对了我画的红箭头还有绿箭头可以看成是函数栈帧的创建与销毁。把详细的函数的栈帧的创建与销毁多想几遍函数的递归应该就会好想象一点了。这节课我啃了两天了后续还得多回顾理解多敲代码告诉自己别畏难很难但也得一步一步走下去总不能放弃吧那就坚定不移的前进这节课的博客真难写呀啊啊啊——
知识点有不对的地方还请多多指教抱拳 完—— 终——Relaxing Time
好好休息一下继续战斗昨天又发现了一首好听的歌()V分享给你 ————————————《Falling U》————————————
Falling U_T-ara_高音质在线试听_Falling U歌词|歌曲下载_酷狗音乐 至此结束——
我是云边有个稻草人
期待与你的下一次相遇
