数据结构-二叉树

二叉树的概念

二叉树的遍历分类

有前序遍历，中序遍历，后序遍历和层序遍历

规则：

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 (node==NULL){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->right=node6;return node1;
}

前序遍历的实现

函数的回归条件为root为空，或者函数正常结束
按照顺序依次为：根，左子树，右子树

void PreOrder(BTNode* root)
{if (root==NULL){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 (root==NULL){return 0;}else{return TreeSize(root->left) + TreeSize(root->right)+1;}
}

执行结果如下：

计算树的深度

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

运行结果如下:

查找二叉树的元素

BTNode* TreeFind(BTNode* root, BTDataType x)
{if (root==NULL){return NULL;}if (root->data==x){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 (front==NULL){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.h"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 (node==NULL){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->right=node6;node1->left = node2;node1->right = node3;node2->left = node4;//node4->left = node5;node3->right = node5;return node1;
}void PreOrder(BTNode* root)
{if (root==NULL){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 (root==NULL){return 0;}else{return TreeSize(root->left) + TreeSize(root->right)+1;}
}int TreeHeight(BTNode* root)
{if (root==NULL){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 (root==NULL){return 0;}if (k==1){return 1;}return TreeLevel(root->left, k - 1) + TreeLevel(root->right, k - 1);
}//查找元素
BTNode* TreeFind(BTNode* root, BTDataType x)
{if (root==NULL){return NULL;}if (root->data==x){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 (front==NULL){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.h"void 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 (newnode==NULL){perror("malloc fail");return;}newnode->next = NULL;newnode->data = x;//需要判断队列中是否有元素if (pq->head==NULL){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->next==NULL){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->size==0;
}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.h>typedef 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);