目录
一.二叉树链式结构的实现
1.二叉树的创建
2.二叉树的销毁
3.二叉树的遍历
1.深度优先
2.广度优先
4.求二叉树节点数
5.求二叉树叶子节点个数
6.求第k层节点数
7.查找值为x的节点
8.判断是否为完全二叉树
二.整体代码
1.BinaryTree.h
2.BinaryTree.c
3.Queue.h
4.Queue.c
5.test.c
在上一篇中我们实现了二叉树的顺序结构——堆的实现,这次实现链式结构,若对堆不了解,可以观看https://blog.csdn.net/w200514/article/details/143086428?sharetype=blog&shareId=143086428&sharerefer=APP&sharesource=w200514&sharefrom=link
一.二叉树链式结构的实现
1.二叉树的创建
对于二叉树的创建,我们只需要创建节点,并将其连接到左右节点上即可
//构建二叉树
BTNode* CreatNode(BTDataType x)
{BTNode* tmp = (BTNode*)malloc(sizeof(BTNode));if (tmp == NULL)return 0;BTNode* node = tmp;if (node == NULL)printf("申请内存失败");node->_data = x;node->_left = NULL;node->_right = NULL;return node;
} BTNode* A = CreatNode('A');BTNode* B = CreatNode('B');BTNode* C = CreatNode('C');BTNode* D = CreatNode('D');BTNode* E = CreatNode('E');A->_left = B;A->_right = C;B->_left = D;B->_right = E;
如图我们创建出了一个二叉树,在这里我们将空节点显示出来,以便于接下来遍历时的理解
2.二叉树的销毁
二叉树的销毁从底部开始向上逐层销毁,我们用递归的方法来实现
//销毁
void BinaryTreeDestroy(BTNode* root)
{if (root == NULL)return;BinaryTreeDestroy(root->_left);BinaryTreeDestroy(root->_right);free(root);
}
3.二叉树的遍历
二叉树遍历分为两种,广度优先(层序遍历),深度优先(前/中/后序遍历)
1.深度优先
前/中/后序遍历的不同,主要是因为根节点遍历的顺序不同
前序遍历:按照根-左子树-右子树的顺序遍历.
对于我们上图创建的二叉树来说,前序遍历应为A B D NULL NULL E NULL NULL C NULL NULL
为何会出现这种情况,我们将使用递归的方式来实现
//前序排列
void PrevOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}printf("%c ", root->_data);PrevOrder(root->_left);PrevOrder(root->_right);
}
中序遍历:左子树-根-右子树
NULL D NULL B NULL E NULL A NULL C NULL
void InOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}InOrder(root->_left);printf("%c ", root->_data);InOrder(root->_right);
}后序遍历:左子树-右子树-根
NULL NULL D NULL NULL E B NULL NULL C A
void LastOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}LastOrder(root->_left);LastOrder(root->_right);printf("%c ", root->_data);
}2.广度优先
层序遍历:自上而下,自左而右的遍历
A B C D E
对于层序遍历,我们可以利用队列来实现.
将根节点存入队列,每次取出一个节点,就将其的左右节点放入队列(如果有左右节点)
//层序遍历
void LevelOrder(BTNode* root)
{Queue q;QueueInit(&q);if (root == NULL)return;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);}QueueDestory(&q);printf("\n");
}4.求二叉树节点数
二叉树节点数我们只需要将左子树节点数加上右子树节点数,再加1(根节点)即可
int BinaryTreeSize(BTNode* root)
{if (root == NULL)return 0;elsereturn BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;
}5.求二叉树叶子节点个数
当只有根节点时,返回1,否则返回左子树加右子树节点数
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);
}6.求第k层节点数
int BinaryTreeLeveIKSize(BTNode* root, int k)
{if (root == NULL)return 0;if (k == 1)return 1;return BinaryTreeLeveIKSize(root->_left, k - 1) + BinaryTreeLeveIKSize(root->_right, k - 1);
}7.查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL)return NULL;if (root->_data == x)return root;BTNode* node = BinaryTreeFind(root->_left, x);if (node != NULL)return node;node = BinaryTreeFind(root->_right, x);if (node != NULL)return node;return NULL;
}8.判断是否为完全二叉树
int BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);if (root == NULL)return 1;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){QueueDestory(&q);return 0;}}QueueDestory(&q);return 1;
}二.整体代码
1.BinaryTree.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef char BTDataType;typedef struct BinaryTreeNode
{BTDataType _data;struct BinaryTreeNode* _left;struct BinaryTreeNode* _right;
}BTNode;void PrevOrder(BTNode* root);
void InOrder(BTNode* root);
void LastOrder(BTNode* root);
int BinaryTreeSize(BTNode* root);
int BinaryTreeLeafSize(BTNode* root);
int BinaryTreeLeveIKSize(BTNode* root, int k);
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
BTNode* CreatNode(BTDataType x);
void BinaryTreeDestroy(BTNode* root);
void LevelOrder(BTNode* root);
int BinaryTreeComplete(BTNode* root);2.BinaryTree.c
#include "BinaryTree.h"
#include "Queue.h"//前序排列
void PrevOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}printf("%c ", root->_data);PrevOrder(root->_left);PrevOrder(root->_right);
}//中序排列
void InOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}InOrder(root->_left);printf("%c ", root->_data);InOrder(root->_right);
}//后序排列
void LastOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}LastOrder(root->_left);LastOrder(root->_right);printf("%c ", root->_data);
}//层序遍历
void LevelOrder(BTNode* root)
{Queue q;QueueInit(&q);if (root == NULL)return;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);}QueueDestory(&q);printf("\n");
}//求二叉树节点数
int BinaryTreeSize(BTNode* root)
{if (root == NULL)return 0;elsereturn 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) + BinaryTreeLeafSize(root->_right);
}//二叉树第k层节点数
int BinaryTreeLeveIKSize(BTNode* root, int k)
{if (root == NULL)return 0;if (k == 1)return 1;return BinaryTreeLeveIKSize(root->_left, k - 1) + BinaryTreeLeveIKSize(root->_right, k - 1);
}//二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL)return NULL;if (root->_data == x)return root;BTNode* node = BinaryTreeFind(root->_left, x);if (node != NULL)return node;node = BinaryTreeFind(root->_right, x);if (node != NULL)return node;return NULL;
}
//构建二叉树
BTNode* CreatNode(BTDataType x)
{BTNode* tmp = (BTNode*)malloc(sizeof(BTNode));if (tmp == NULL)return 0;BTNode* node = tmp;if (node == NULL)printf("申请内存失败");node->_data = x;node->_left = NULL;node->_right = NULL;return node;
}//销毁
void BinaryTreeDestroy(BTNode* root)
{if (root == NULL)return;BinaryTreeDestroy(root->_left);BinaryTreeDestroy(root->_right);free(root);
}//判断是否为完全二叉树,是返回1不是返回0
int BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);if (root == NULL)return 1;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){QueueDestory(&q);return 0;}}QueueDestory(&q);return 1;
}3.Queue.h
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>extern struct BinaryTreeNode;
typedef struct BinaryTreeNode* QDataType;typedef struct QueueNode
{struct QueueNode* _next;QDataType _data;
}QueueNode;typedef struct Queue
{QueueNode* _head;QueueNode* _tail;
}Queue;void QueueInit(Queue* pq);
void QueueDestory(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
int QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);4.Queue.c
#include "Queue.h"//初始化
void QueueInit(Queue* pq)
{assert(pq);pq->_head = pq->_tail = NULL;
}//销毁
void QueueDestory(Queue* pq)
{assert(pq);QueueNode* cur = pq->_head;while (cur != NULL){QueueNode* next = cur->_next;free(cur);cur = next;}pq->_head = pq->_tail = NULL;
}//队尾入
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));if (newNode == NULL){printf("申请内存失败");exit(-1);}newNode->_data = x;newNode->_next = NULL;if (pq->_head == NULL)pq->_head = pq->_tail = newNode;elsepq->_tail->_next = newNode;pq->_tail = newNode;
}//队头出
void QueuePop(Queue* pq)
{assert(pq);assert(pq->_head);QueueNode* next = pq->_head->_next;free(pq->_head);pq->_head = next;if (pq->_head == NULL)pq->_tail = NULL;}//取队头数据
QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->_head);return pq->_head->_data;
}//取队尾数据
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->_tail);return pq->_tail->_data;
}//返回1为空,返回0为非空
int QueueEmpty(Queue* pq)
{assert(pq);return pq->_head == NULL ? 1 : 0;
}//获取数据个数
int QueueSize(Queue* pq)
{assert(pq);assert(pq->_head);QueueNode* cur = pq->_head;int size = 0;while (cur != NULL){++size;cur = cur->_next;}return size;
}5.test.c
#include "BinaryTree.h"void TestBinaryTree()
{BTNode* A = CreatNode('A');BTNode* B = CreatNode('B');BTNode* C = CreatNode('C');BTNode* D = CreatNode('D');BTNode* E = CreatNode('E');A->_left = B;A->_right = C;B->_left = D;B->_right = E;printf("前序排列: ");PrevOrder(A);printf("\n");printf("中序排列: ");InOrder(A);printf("\n");printf("后序排列: ");LastOrder(A);printf("\n");printf("层序排列: ");LevelOrder(A);printf("\n");printf("二叉树节点为: ");printf("%d", BinaryTreeSize(A));printf("\n");printf("二叉树叶子节点个数为: ");printf("%d",BinaryTreeLeafSize(A));printf("\n");printf("二叉树第3层节点数为: ");printf("%d",BinaryTreeLeveIKSize(A, 3));printf("\n");BTNode* result = BinaryTreeFind(A, 'C');if (result != NULL) {printf("结点的地址为: %p\n", (void*)result);printf("结点的值为: %c\n", result->_data); }else printf("节点不存在\n");printf("%d", BinaryTreeComplete(A));BinaryTreeDestroy(A);
}int main()
{TestBinaryTree();return 0;
}
