上海网站设计与开发公司,网站建站流程图,led灯网站模板,环保网站建设模板免费下载数据结构-二叉树 二叉树的概念二叉树的遍历分类 建立二叉树#xff0c;并遍历二叉树的最小单元二叉树的最小单元初始化初始化二叉树前序遍历的实现中序遍历的实现后序遍历的实现计算节点的个数计算树的深度求第k层的个数查找二叉树的元素分层遍历 全部代码如下 二叉树的概念 二… 数据结构-二叉树 二叉树的概念二叉树的遍历分类 建立二叉树并遍历二叉树的最小单元二叉树的最小单元初始化初始化二叉树前序遍历的实现中序遍历的实现后序遍历的实现计算节点的个数计算树的深度求第k层的个数查找二叉树的元素分层遍历 全部代码如下 二叉树的概念 二叉树的遍历分类
有前序遍历中序遍历后序遍历和层序遍历
规则 1.遇到根可以直接访问根 2.遇到左子树右子树不可以直接访问要将其看作一颗新的二叉树按遍历规则再次循环直至左子树或右子树为空则可访问空。 前序遍历 中序遍历和后序遍历 三者访问根的时机不同
层序遍历一层一层的进行 1 2 4 3 5 6 建立二叉树并遍历
二叉树的最小单元
根左子树和右子树
typedef int BTDataType;typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;二叉树的最小单元初始化
BTNode* BuyNode(BTDataType x)
{BTNode* node(BTNode*)malloc(sizeof(BTNode));if (nodeNULL){perror(malloc fail);return NULL;}node-data x;node-left NULL;node-right NULL;return node;
}初始化二叉树
BTNode* CreatTree()
{BTNode* node1 BuyNode(1);BTNode* node2 BuyNode(2);BTNode* node3 BuyNode(3);BTNode* node4 BuyNode(4);BTNode* node5 BuyNode(5);BTNode* node6 BuyNode(6);node1-left node2;node1-right node4;node2-left node3;node4-left node5;node4-rightnode6;return node1;
}前序遍历的实现
函数的回归条件为root为空或者函数正常结束 按照顺序依次为根左子树右子树
void PreOrder(BTNode* root)
{if (rootNULL){printf(NULL );return;}//root,left,rightprintf(%d ,root-data);PreOrder(root-left);PreOrder(root-right);
}递归调用展开图
结果如下
中序遍历的实现
函数的回归条件为root为空或者函数正常结束 按照顺序依次为左子树根右子树
void InOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}InOrder(root-left);printf(%d , root-data);InOrder(root-right);
}后序遍历的实现
函数的回归条件为root为空或者函数正常结束 按照顺序依次为左子树右子树根
void PostOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}PostOrder(root-left);PostOrder(root-right);printf(%d , root-data);
}计算节点的个数
利用分治法求节点的个数只有节点存在时才会1并返回下层的统计个数
int TreeSize(BTNode* root)
{if (rootNULL){return 0;}else{return TreeSize(root-left) TreeSize(root-right)1;}
}执行结果如下
计算树的深度 int TreeHeight(BTNode* root)
{if (rootNULL){return 0;}int leftHeight TreeHeight(root-left);int rightHeight TreeHeight(root-right);return leftHeight rightHeight ?leftHeight 1 :rightHeight 1;
}代码执行结果如下
求第k层的个数 int TreeLevel(BTNode* root,int k)
{if (rootNULL){return 0;}if (k1){return 1;}return TreeLevel(root-left, k - 1) TreeLevel(root-right, k - 1);
}运行结果如下:
查找二叉树的元素 BTNode* TreeFind(BTNode* root, BTDataType x)
{if (rootNULL){return NULL;}if (root-datax){return root;}BTNode* lret TreeFind(root-left, x);if (lret){return lret;}BTNode* rret TreeFind(root-right, x);if (rret){return rret;}return NULL;
}结果如下
分层遍历
利用队列先将根push进入循环可pop再将层子节点push依次循环。安照队列先进先出的原则可实现分层打印
void LevelOrder(BTNode* root)
{Quene q;QueueInit(q);if (root){QueuePush(q,root);}while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);printf(%d ,front-data);if (front-left){QueuePush(q, front-left);}if (front-right){QueuePush(q, front-right);}}QueueDestroy(q);
}结果如下 判断是否为完全二叉树
bool TreeComplete(BTNode* root)
{Quene q;QueueInit(q);if (root){QueuePush(q, root);}while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);if (frontNULL){break;}else{QueuePush(q, front-left);QueuePush(q, front-right);}}while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);if (front){QueueDestroy(q);return false;}}QueueDestroy(q);return true;
}全部代码如下
test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include stdio.h
#include stdlib.h
#include Queue.htypedef int BTDataType;typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;BTNode* BuyNode(BTDataType x)
{BTNode* node(BTNode*)malloc(sizeof(BTNode));if (nodeNULL){perror(malloc fail);return NULL;}node-data x;node-left NULL;node-right NULL;return node;
}BTNode* CreatTree()
{BTNode* node1 BuyNode(1);BTNode* node2 BuyNode(2);BTNode* node3 BuyNode(3);BTNode* node4 BuyNode(4);BTNode* node5 BuyNode(5);//BTNode* node6 BuyNode(6);//node1-left node2;//node1-right node4;//node2-left node3;//node4-left node5;//node4-rightnode6;node1-left node2;node1-right node3;node2-left node4;//node4-left node5;node3-right node5;return node1;
}void PreOrder(BTNode* root)
{if (rootNULL){printf(NULL );return;}//root,left,rightprintf(%d ,root-data);PreOrder(root-left);PreOrder(root-right);
}void InOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}InOrder(root-left);printf(%d , root-data);InOrder(root-right);
}void PostOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}PostOrder(root-left);PostOrder(root-right);printf(%d , root-data);
}//分治法求节点的个数
int TreeSize(BTNode* root)
{if (rootNULL){return 0;}else{return TreeSize(root-left) TreeSize(root-right)1;}
}int TreeHeight(BTNode* root)
{if (rootNULL){return 0;}int leftHeight TreeHeight(root-left);int rightHeight TreeHeight(root-right);return leftHeight rightHeight ?leftHeight 1 :rightHeight 1;
}int TreeLevel(BTNode* root,int k)
{if (rootNULL){return 0;}if (k1){return 1;}return TreeLevel(root-left, k - 1) TreeLevel(root-right, k - 1);
}//查找元素
BTNode* TreeFind(BTNode* root, BTDataType x)
{if (rootNULL){return NULL;}if (root-datax){return root;}BTNode* lret TreeFind(root-left, x);if (lret){return lret;}BTNode* rret TreeFind(root-right, x);if (rret){return rret;}return NULL;
}//分层遍历
void LevelOrder(BTNode* root)
{Quene q;QueueInit(q);if (root){QueuePush(q,root);}while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);printf(%d ,front-data);if (front-left){QueuePush(q, front-left);}if (front-right){QueuePush(q, front-right);}}QueueDestroy(q);
}//判断是不是完全二叉树
bool TreeComplete(BTNode* root)
{Quene q;QueueInit(q);if (root){QueuePush(q, root);}while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);if (frontNULL){break;}else{QueuePush(q, front-left);QueuePush(q, front-right);}}while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);if (front){QueueDestroy(q);return false;}}QueueDestroy(q);return true;
}
int main()
{BTNode* root CreatTree();PreOrder(root);printf(\n);InOrder(root);printf(\n);PostOrder(root);printf(\n);printf(%d,TreeSize(root));printf(\n);printf(%d , TreeHeight(root));printf(\n);printf(%d , TreeLevel(root,3));printf(\n);printf(%p , TreeFind(root, 5));printf(\n);printf(%p , TreeFind(root, 60));printf(\n);LevelOrder(root);printf(TreeComplete: %d, TreeComplete(root));//二维数组return 0;
}Queue.c
#define _CRT_SECURE_NO_WARNINGS 1
#include Queue.hvoid QueueInit(Quene* pq)
{assert(pq);pq-head pq-tail NULL;pq-size 0;
}void QueueDestroy(Quene* pq)
{assert(pq);QNode* cur pq-head;while(cur){QNode* next cur-next;free(cur);cur next;}pq-head pq-tail NULL;pq-size 0;
}void QueuePush(Quene* pq, QDataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnodeNULL){perror(malloc fail);return;}newnode-next NULL;newnode-data x;//需要判断队列中是否有元素if (pq-headNULL){pq-head pq-tail newnode;}else{pq-tail-next newnode;pq-tail newnode;}pq-size;
}void QueuePop(Quene* pq)
{assert(pq);//确保有队列assert(pq-head ! NULL);//确保队列不为空if (pq-head-nextNULL){free(pq-head);pq-head pq-tail NULL;}else{QNode* next pq-head-next;free(pq-head);pq-head next;}pq-size--;
}int QueueSize(Quene* pq)
{assert(pq);return pq-size;
}bool QueueEmpty(Quene* pq)
{assert(pq);return pq-size0;
}QDataType QueueFront(Quene* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-head-data;
}QDataType QueueBack(Quene* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-tail-data;
}Queue.h
#pragma once
#include stdio.h
#include stdlib.h
#include stdbool.h
#include assert.htypedef struct BinaryTreeNode* QDataType;//单个节点
typedef struct QueneNode
{struct QueneNode* next;QDataType data;
}QNode;//整个队列
typedef struct Quene
{QNode* head;QNode* tail;int size;
}Quene;//初始化
void QueueInit(Quene* pq);
//销毁
void QueueDestroy(Quene* pq);//入队
void QueuePush(Quene* pq, QDataType x);
//出队
void QueuePop(Quene* pq);//计算队列中元素的个数
int QueueSize(Quene* pq);
//判断队列是否为空
bool QueueEmpty(Quene* pq);//队列中的队头元素
QDataType QueueFront(Quene* pq);
//队列中的队尾元素
QDataType QueueBack(Quene* pq);
