数据结构手撕--【二叉树】
目录
定义结构体：
初始化：
手动创建一个二叉树：
前序遍历：
中序遍历：
后序遍历
二叉树节点个数：
叶子节点个数：
二叉树第k层节点个数：
二叉树的高度：
查找值为x的节点：
二叉树的层序遍历：
判断二叉树是否为完全二叉树：
销毁二叉树：
二叉树增删查改没有具体意义。我们主要实现搜索二叉树
特殊的二叉树---完全二叉树（堆） 适合数组结构表示 （堆结构下节更新）
对于普通二叉树我们采用 链式结构
定义结构体：
一个结构体就是一个树节点
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//链式二叉树//定义结构体 --- 一个结构体就是一个树节点
typedef char BTDataType;
typedef struct BinaryTreeNode
{BinaryTreeNode* left; //指向节点的指针 类型为节点类型BinaryTreeNode* right;BTDataType data;
}BTNode;初始化：
链式结构 开辟空间创建新节点
BTNode BuyNode(BTDataType x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));newnode->left = NULL;newnode->right = NULL;newnode->data = x;return newnode;
}手动创建一个二叉树：
BTNode* CreatBinaryTree()
{BTNode* nodeA = BuyNode('A');BTNode* nodeB = BuyNode('B');BTNode* nodeC = BuyNode('C');BTNode* nodeD = BuyNode('D');BTNode* nodeE = BuyNode('E');BTNode* nodeF = BuyNode('F');nodeA->left = nodeB;nodeA->right = nodeC;nodeB->left = nodeD;nodeC->left = nodeE;nodeC->right = nodeF;return nodeA;
}前序遍历：
--- 根左右 打印放在最前面 再左、右递归
void PerOrder(BTNode* root)
{if (root == NULL){return NULL;}printf("%c", root->data);PerOrder(root->left);PerOrder(root->right);
}画图理解递归过程：
中序遍历：
--- 左根右 打印放在中间 先左递归 打印 再右递归
void MidOrder(BTNode* root)
{if (root == NULL){return NULL;}MidOrder(root->left);printf("%c", root->data);MidOrder(root->right);
} 
后序遍历
-- 左右根
void PostOrder(BTNode* root)
{if (root == NULL){return NULL;}PostOrder(root->left);PostOrder(root->right);printf("%c", root->data);
}二叉树节点个数：
为空返回0，不为空去递归左右子树，+1是递归完左右返回之后+1的，即就会算此时的root节点的数量。（下图有具体的递归过程）左+右+根（1）
int BinaryTreeSize(BTNode* root)
{return root == NULLL ? 0 : BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
叶子节点个数：
走到叶子返回1（不再向下递归），返回 左+右 不算根的个数
int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL){return 0;}if (root->left && root->right == NULL) //在递归的过程中 走到叶子就会返回1 最后左+右即可{return 1;}return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
二叉树第k层节点个数：
往下走一层k都会减一，假如要求第五层，走到第五层k=1，把1返回即可
int BinaryTreeLeaveSize(BTNode* root, int k)
{if (root == NULL){return 0;}if (k == 1){return 1;}return BinaryTreeLeaveSize(root->left, k - 1) + BinaryTreeLeaveSize(root->right, k - 1);
} 
二叉树的高度：
当这棵树为空树时,二叉树的高度应该是0,所以当数为空我们返回0,然而当树不等于空时,我们可以以大事化小,小事化了的思想,将当前树的高度转换成左右子树两个中的最大高度再加上一,然后左右子树中最大高度的树的高度又可以转换成我们刚刚的思想,就这样不断递归下去直接我们遇见空节点.
nt BinaryTreeDepth(BTNode* root)
{//为空 返回0//递归左树 遇到左右都为空的节点 返回1 再递归右树 左右都为空 返回1，//左右比较 返回大的+1if (root == NULL){return NULL;}NTNode* left = BinaryTreeDepth(root->left);NTNode* right = BinaryTreeDepth(root->right);return left > right ? left + 1 : right + 1;
}查找值为x的节点：
只要找到了就不会返回空，只要返回的不是空就是找到了。左子树找到了就不会再去右子树找
BTNode* BinaryTreeFind(BTNode* root, BTNodeType x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}BTNode* left = BinaryTreeFind(root->left);if (left != NULL){return left;}BTNode* right = BinaryTreeFind(root->right);if (left != NULL){return right;}return NULL;
}二叉树的层序遍历：
借助队列
- 先将根入队列
- 当前节点出队列后,将次此节点的左右孩子入队列
- 一直这样循环往复直到队列为空,说明最后一层已经没有节点了,遍历结束
void BinaryTreeLevelOrder(BTNode* root)
{if (root == NULL){return NULL;}Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);printf("%c", front->data);if (front->left != NULL){QueuePush(&q, front->left);}if (front->right != NULL){QueuePush(&q, front->right);}}printf("\n");QueueDestroy(&q);
}判断二叉树是否为完全二叉树：
完全二叉树和非完全二叉树的区别：前者一旦有空后面就都是空，而后者一旦有空后面还会出现非空。
第二个while循环是遇到空时候，看后面是否全为空，如果是就是完全二叉树
QueueEmpty(&q)判断队列是否为空，看的是front是否为空
bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);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){QueueDestory(&q);return false;}}QueueDestory(&q);return true;
}销毁二叉树：
void BinaryTreeDestory(BTNode* root)
{if (root == NULL){return;}BinaryTreeDestory(root->left);BinaryTreeDestory(root->right);free(root);
}