数据结构——链式二叉树

🐶博主主页：@ᰔᩚ. 一怀明月ꦿ

❤️‍🔥专栏系列：线性代数，C初学者入门训练，题解C，C的使用文章，「初学」C++

🔥座右铭：“不要等到什么都没有了，才下定决心去做”

🚀🚀🚀大家觉不错的话，就恳求大家点点关注，点点小爱心，指点指点🚀🚀🚀

链式二叉树的实现

链式二叉树的结构创建

链式二叉树节点的创建

链式二叉树的创建

链式二叉树的前序遍历

链式二叉树的中序遍历

链式二叉树的后序遍历

链式二叉树的节点个数

链式二叉树叶子节点个数

链式二叉树的高度

链式二叉树的k层节点个数

链式二叉树中寻找某个值

链式二叉树的层序遍历

链式二叉树的销毁

源码：

链式二叉树的实现

链式二叉树的结构创建

typedef int BTDataType;
typedef struct BinarytreeNode
{struct BinarytreeNode* left;struct BinarytreeNode* right;BTDataType data;
}BTNode;

链式二叉树节点的创建

BTNode* BuyNodde(BTDataType x)
{BTNode* newnode=(BTNode*)malloc(sizeof(BTNode));if(newnode==NULL){perror("malloc fail");return  NULL;}newnode->data=x;newnode->left=NULL;newnode->right=NULL;return newnode;
}

链式二叉树的创建

这里的二叉树是[1,2,4,3,null,5,6]

BTNode* CreatBinaryTree(void)
{BTNode* node1=BuyNodde(1);BTNode* node2=BuyNodde(2);BTNode* node3=BuyNodde(3);BTNode* node4=BuyNodde(4);BTNode* node5=BuyNodde(5);BTNode* node6=BuyNodde(6);node1->left=node2;node1->right=node4;node2->left=node3;node4->left=node5;node4->right=node6;return node1;
}

链式二叉树的前序遍历

void PrevOrder(BTNode* root)
{if(root==NULL){printf("N ");return;}printf("%d ",root->data);PrevOrder(root->left);PrevOrder(root->right);
}

链式二叉树的中序遍历

void InOrder(BTNode* root)
{if(root==NULL){printf("N ");return;}PrevOrder(root->left);printf("%d ",root->data);PrevOrder(root->right);
}

链式二叉树的后序遍历

void PostOrder(BTNode* root)
{if(root==NULL){printf("N ");return;}PostOrder(root->left);PostOrder(root->right);

链式二叉树的节点个数

int BinaryTreeSize(BTNode* root)
{if(root==NULL)return 0;return BinaryTreeSize(root->left)+BinaryTreeSize(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)+BinaryTreeSize(root->right);
}

链式二叉树的高度

int BinaryTreeHeight(BTNode* root)
{if(root==NULL)return 0;int ret1=BinaryTreeSize(root->left);int ret2=BinaryTreeSize(root->right);return ret1>ret2?ret1+1:ret2+1;
}

链式二叉树的k层节点个数

int KLevelBinaryTreeSize(BTNode* root,int k)
{if(root==NULL)return 0;if(k==1)return 1;return KLevelBinaryTreeSize(root->left,k-1)+KLevelBinaryTreeSize(root->right,k-1);
}

链式二叉树中寻找某个值

BTNode* BinaryTreeFind(BTNode* root,int 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;
}

链式二叉树的层序遍历

链式二叉树的层序遍历需要借助队列的性质，所以需要使用队列的源码

void LevelOreder(BTNode* root)
{Queue 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);}printf("\n");
}

链式二叉树的销毁

void DestroyBinaryTree(BTNode* root)
{if(root==NULL)return;DestroyBinaryTree(root->left);DestroyBinaryTree(root->right);free(root);
}

源码：

#ifndef Queue_h
#define Queue_h#include <stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>#endif /* Queue_h */typedef struct BinarytreeNode* QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}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 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\n");return;}newnode->data=x;newnode->next=NULL;if(pq->phead==NULL)//当链表为空的时候{assert(!pq->ptail);//当链表为空的时候,pq->ptail也是空pq->phead=newnode;pq->ptail=newnode;}//链表不为空的时候进队列插入数据（尾插）else{pq->ptail->next=newnode;pq->ptail=newnode;}pq->size++;
}
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));//判断队列是否为空，断言为真程序继续//一个节点的时候//if(pq->phead->next==NULL)if(pq->phead==pq->ptail){free(pq->phead);pq->phead=NULL;pq->ptail=NULL;}//多个节点的时候else{//相当于头删QNode* next=pq->phead->next;free(pq->phead);pq->phead=next;}pq->size--;
}
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));//判断队列是否为空，断言为真程序继续return pq->phead->data;
}
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->ptail->data;
}
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead==NULL;
}
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}typedef int BTDataType;
typedef struct BinarytreeNode
{struct BinarytreeNode* left;struct BinarytreeNode* right;BTDataType data;
}BTNode;
BTNode* BuyNodde(BTDataType x)
{BTNode* newnode=(BTNode*)malloc(sizeof(BTNode));if(newnode==NULL){perror("malloc fail");return  NULL;}newnode->data=x;newnode->left=NULL;newnode->right=NULL;return newnode;
}
BTNode* CreatBinaryTree(void)
{BTNode* node1=BuyNodde(1);BTNode* node2=BuyNodde(2);BTNode* node3=BuyNodde(3);BTNode* node4=BuyNodde(4);BTNode* node5=BuyNodde(5);BTNode* node6=BuyNodde(6);node1->left=node2;node1->right=node4;node2->left=node3;node4->left=node5;node4->right=node6;return node1;
}
//前序遍历
void PrevOrder(BTNode* root)
{if(root==NULL){printf("N ");return;}printf("%d ",root->data);PrevOrder(root->left);PrevOrder(root->right);
}
//中序遍历
void InOrder(BTNode* root)
{if(root==NULL){printf("N ");return;}PrevOrder(root->left);printf("%d ",root->data);PrevOrder(root->right);
}
//后序遍历
void PostOrder(BTNode* root)
{if(root==NULL){printf("N ");return;}PostOrder(root->left);PostOrder(root->right);printf("%d ",root->data);
}//求二叉树的个数
int BinaryTreeSize(BTNode* root)
{if(root==NULL)return 0;return BinaryTreeSize(root->left)+BinaryTreeSize(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)+BinaryTreeSize(root->right);
}//求二叉树的高度int BinaryTreeHeight(BTNode* root)
{if(root==NULL)return 0;int ret1=BinaryTreeSize(root->left);int ret2=BinaryTreeSize(root->right);return ret1>ret2?ret1+1:ret2+1;
}//求树的k层节点
int KLevelBinaryTreeSize(BTNode* root,int k)
{if(root==NULL)return 0;if(k==1)return 1;return KLevelBinaryTreeSize(root->left,k-1)+KLevelBinaryTreeSize(root->right,k-1);
}//树中节点的寻找，找到返回这个节点
BTNode* BinaryTreeFind(BTNode* root,int 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;
}
//层序遍历
void LevelOreder(BTNode* root)
{Queue 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);}printf("\n");
}//二叉树的销毁
void DestroyBinaryTree(BTNode* root)
{if(root==NULL)return;DestroyBinaryTree(root->left);DestroyBinaryTree(root->right);free(root);
}
int main()
{//创建链式二叉树BTNode* root=NULL;root=CreatBinaryTree();printf("前序遍历：");PrevOrder(root);printf("\n");printf("中序遍历：");InOrder(root);printf("\n");printf("后序遍历：");PostOrder(root);printf("\n");printf("树的节点个数：%d\n",BinaryTreeSize(root));printf("树的叶子节点的个数：%d\n",BinaryTreeleafSize(root));printf("树的高度为：%d\n",BinaryTreeHeight(root));printf("树的第三层的节点个数：%d\n",KLevelBinaryTreeSize(root, 3));printf("树中的数值5：%d\n",BinaryTreeFind(root, 5)->data);printf("层序遍历：\n");LevelOreder(root);return 0;
}