数据结构（二叉树-2）

一、 实现链式结构二叉树

　　1.1 Tree.h

　　1.2 Tree.c 前中后序遍历

　　　　前序遍历

　　　　中序遍历

　　　　后续遍历

　　1.2 Tree.c 结点个数

　　1.3Tree.c 叶子节点个数

　　1.4 Tree.c 二叉树的高度

　　1.5 Tree.c 层序遍历

　　1.6 判断是否为完全二叉树

　　1.7 销毁二叉树

　　test.c

一、 实现链式结构二叉树

1.1 Tree.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//定义二叉树的链式结构
//二叉树结点的结构
typedef int BTDataType;
typedef struct BinaryTreeNode
{int data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;//前序遍历
void PreOrder(BTNode* root);
//中序遍历
void InOrder(BTNode* root);
//后序遍历 
void PostOrder(BTNode* root);// ⼆叉树结点个数
int BinaryTreeSize(BTNode* root);// ⼆叉树叶⼦结点个数
int BinaryTreeLeafSize(BTNode* root);// ⼆叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k);//⼆叉树的深度/⾼度
int BinaryTreeDepth(BTNode* root);// ⼆叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);// ⼆叉树销毁
void BinaryTreeDestory(BTNode** root);//层序遍历
void LevelOrder(BTNode* root);//判断二叉树是否为完全二叉树
bool BinaryTreeComplete(BTNode* root);

 前序遍历

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

输出结果为： 1 2 4 3

其他两种遍历方式的递归过程也是一样的做法，下面就只展示代码部分了。

中序遍历

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

输出结果为： 4 2 1 3 

后续遍历

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

输出结果为： 4 2 3 1

1.2 Tree.c 结点个数

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

1.3Tree.c 叶子节点个数

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);
}

•  当一棵二叉树中的节点的左右孩都为空时，证明他就是最后的结点，也叫做 “叶子节点” ，上述代码就运用了这一特点进行函数递归 ，if (root->left == NULL && root->right == NULL) 成立则返回 1 ，不成立就继续对其左右孩创建函数栈帧进行递归。

1.4 Tree.c 二叉树的高度

int BinaryTreeDepth(BTNode* root)
{if (root == NULL){return 0;}int lefttree = BinaryTreeDepth(root->left);int righttree = BinaryTreeDepth(root->right);return lefttree > righttree ? lefttree + 1 : righttree + 1;
}

•  此处的递归方式与查找节点个数的递归方式相同，但是这里是求树的高度，所以当我们返回根节点的左右孩子的节点个数时（也就是求出左孩和右孩分别的高度），要进行比较，选出较高的树的高度，此高度就是整棵树的高度。

1.5 Tree.c 层序遍历

在上述构建好的二叉树中，如果要对其进行层序遍历的话，期待输出的结果为 1 2 3 4 ，

此时我们可以借助队列这一数据结构实现，所以在编写代码时先要包括 “Queue.h” 的头文件，具体队列的实现可以参考 数据结构（队列）-CSDN博客。

void LevelOrder(BTNode* root)
{Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueEmpty(&q)){//取队头，打印BTNode* front = QueueFront(&q);printf("%d ", front->data);QueuePop(&q);//队头节点的左右孩子入队列if (front->left)QueuePush(&q, front->left);if (front->right)QueuePush(&q, front->right);}//队列为空QueueDestroy(&q);
}

1.6 判断是否为完全二叉树 

bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);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)){if (front != NULL){QueueDestory(&q);return false;}}QueueDestory(&q);return true;
}

•  如果是完全二叉树，跳出一个循环之后队列中剩下的全是NULL节点；
•  如果不是完全二叉树，跳出一个循环之后队列还有非空节点。

1.7 销毁二叉树

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

• 销毁左子树 + 销毁右子树 + 销毁根节点

test.c

#include"Tree.h"BTNode* buyNode(BTDataType x)
{//创建结点BTNode* newnode = (BTNode*)malloc(sizeof(BTDataType));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->left = newnode->right = NULL;return newnode;
}void treetest()
{BTNode* node1 = buyNode(1);BTNode* node2 = buyNode(2);BTNode* node3 = buyNode(3);BTNode* node4 = buyNode(4);node1->left = node2;node1->right = node3;node2->light = node4;
}int main()
{treetest();return 0;
}

未完待续~~