二叉树讲解

目录

前言

二叉树的遍历

层序遍历

队列的代码

 queuepush和queuepushbujia的区别

判断二叉树是否是完全二叉树

前序

中序

后序

功能展示

创建二叉树

初始化

销毁

简易功能介绍

二叉树节点个数

二叉树叶子节点个数

二叉树第k层节点个数

二叉树查找值为x的节点

判断是否为单值二叉数

判断二叉数高度

---

前言

本文讲解关于二叉树的创建和各种功能的实现，重点讲解前，中，后和层序遍历的写法

（层序遍历放到了本文前面先讲，如果是刚接触二叉数可以先看功能展示）

前中后序的遍历都用到了递归都写法

而层序遍历却不方便，只能创建队列来解决

二叉树的遍历

层序遍历

层序遍历这里重点讲解一下

因为不能使用递归，只好创建队列来帮助实现

队列的代码

头文件

typedef BTNode* QDataType;typedef struct QueueNode
{struct QueueNode* next;QDataType val;
}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 QueuePushbujia(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");return;}newnode->next = NULL;newnode->val = x;if (pq->ptail == NULL){pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;
}void QueuePushbujia(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");return;}newnode->next = NULL;newnode->val = x;if (pq->ptail == NULL){pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = newnode;}
}
// 队头删除
void QueuePop(Queue* pq)
{assert(pq);assert(pq->size != 0);/*QNode* next = pq->phead->next;free(pq->phead);pq->phead = next;if (pq->phead == NULL)pq->ptail = NULL;*/// 一个节点if (pq->phead->next == NULL){free(pq->phead);pq->phead = pq->ptail = NULL;}else // 多个节点{QNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}pq->size--;
}QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->phead);return pq->phead->val;
}QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->ptail);return pq->ptail->val;
}int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}

 queuepush和queuepushbujia的区别

两个都是将数据尾插进去，但bujia函数并不会对size加加

这样我们不仅可以正常打印N还不影响真实数据的打印

void BinaryTreeLevelOrder(BTNode* root)
{assert(root);Queue a;QueueInit(&a);BTNode* n = BuyNode1(root->_data);n = root;BTNode* null = BuyNode1('N');printf("%c ", n->_data);while (1){if (n->_left != NULL){QueuePush(&a, n->_left);}else{QueuePushbujia(&a,null);}if (n->_right != NULL){QueuePush(&a, n->_right);}else{QueuePushbujia(&a,null);}if (QueueEmpty(&a)){break;}n = QueueFront(&a);QueuePop(&a);if (n->_data == 'N'){a.size++;}printf("%c ", n->_data);}
}

每拿出一个头数据时就会对size--这样的话如果为N的话很有可能会出现size减完了但实际数据没有打印完的情况

所以这里加入了判断n->_data等于N时应该让size++ 

利用写出来的层序遍历就可以实现

判断二叉树是否是完全二叉树

i和x的作用

如果是完全二叉树遇到一个N后不可能再遇到N意外的数了

否则就是非完全二叉树

利用这一特征

当遇到第一个N时让i++

如果i不等于0说明遇到过N了如果此时遇到了非N的数那么就让n++

如果两个数同时不为0则为非完全二叉树

int BinaryTreeComplete(BTNode* root)
{assert(root);Queue a;QueueInit(&a);BTNode* n = BuyNode1(root->_data);n = root;BTNode* null = BuyNode1('N');//printf("%c ", n->_data);char pan = 'x';int i = 0;int x = 0;while (1){if (n->_left != NULL){QueuePush(&a, n->_left);}else{QueuePushbujia(&a, null);}if (n->_right != NULL){QueuePush(&a, n->_right);}else{QueuePushbujia(&a, null);}if (QueueEmpty(&a)){break;}n = QueueFront(&a);QueuePop(&a);if (n->_data == 'N'){a.size++;}//printf("%c ", n->_data);pan = n->_data;if (pan == 'N'){i++;}if (i !=0){if (pan != 'N'){x++;}}if (i!=0&&x!=0){return 1;}}return 0;
}

前序

void BinaryTreePrevOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}printf("%c ", root->_data);BinaryTreePrevOrder(root->_left);BinaryTreePrevOrder(root->_right);
}

中序

void BinaryTreeInOrder(BTNode* root)
{if (root == NULL){printf("N");return;}BinaryTreeInOrder(root->_left);printf("%c ", root->_data);BinaryTreeInOrder(root->_right);
}

后序

void BinaryTreePostOrder(BTNode* root)
{if (root == NULL){printf("N");return;}BinaryTreePostOrder(root->_left);BinaryTreePostOrder(root->_right);printf("%c ", root->_data);
}

功能展示

完成关于二叉树的如下功能

//初始化
BTNode* BuyNode1(BTDataType x);// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi);
// 二叉树销毁
void BinaryTreeDestory(BTNode** root);
// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root);
//判断是否为单值二叉数
bool isUnivalTree(struct BTNode* root);
//判断二叉数高度
int maxDepth(struct BTNode* root);

创建二叉树

手动创建一个二叉树可以让后面的功能更方便调试

首先确定结构体内容如下

typedef char BTDataType;typedef struct BinaryTreeNode
{BTDataType _data;struct BinaryTreeNode* _left;struct BinaryTreeNode* _right;
}BTNode;

在进行手动创建一个二叉树

创建之前需要初始化结构体

初始化

//初始化
BTNode* BuyNode1(BTDataType x)
{BTNode* n = (BTNode*)malloc(sizeof(BTNode));if (n == NULL){perror("malloc false");return NULL;}n->_data = x;n->_left = NULL;n->_right = NULL;return n;
}

有了初始化代码就可以正式创建二叉树了 

BTNode* headadd()
{BTNode* a1 = BuyNode1('a');BTNode* a2 = BuyNode1('b');BTNode* a3 = BuyNode1('c');BTNode* a4 = BuyNode1('d');BTNode* a5 = BuyNode1('e');a1->_left = a2;a1->_right = a3;a2->_left = a4;a4->_right = a5;return a1;
}

此时二叉树就建好了

有了初始化就需要有销毁，防止内存泄漏

销毁

使用递归思想比较方便

void BinaryTreeDestory(BTNode** root)
{assert(root);assert(*root);BinaryTreeDestory(&((*root)->_left));BinaryTreeDestory(&((*root)->_right));free(*root);*root == NULL;
}

简易功能介绍

大多数采用递归的方法即可轻松解决

二叉树节点个数

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||k<1){return 0;}if (root!=NULL&&k == 1){return 1;}return BinaryTreeLevelKSize(root->_left, k - 1) +BinaryTreeLevelKSize(root->_right, k - 1);
}

二叉树查找值为x的节点
 

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL){return NULL;}if (root->_data == x){return root;}BTNode* lf = BinaryTreeFind(root->_left, x);if (lf != NULL){return lf;}BTNode* lr = BinaryTreeFind(root->_right, x);if (lr != NULL){return lr;}return NULL;
}

判断是否为单值二叉数

bool isUnivalTree(BTNode* root) 
{if (root == NULL){return true;}if (root->_left){if (root->_data!= root->_left->_data){return false;}}if (!isUnivalTree(root->_left)){return false;}if (root->_right){if (root->_data != root->_right->_data){return false;}}if (!isUnivalTree(root->_right)){return false;}return true;
}

判断二叉数高度

int maxDepth(BTNode* root)
{if (root == NULL){return 0;}int leftsize = maxDepth(root->_left);int rightsize = maxDepth(root->_right);return leftsize > rightsize ? leftsize + 1 : rightsize + 1;
}