数据结构手撕--【二叉树】

 

目录

定义结构体：

初始化：

手动创建一个二叉树：

前序遍历：

中序遍历：

后序遍历

 二叉树节点个数：

叶子节点个数：

二叉树第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;
}

二叉树的层序遍历：

借助队列

1. 先将根入队列
2. 当前节点出队列后,将次此节点的左右孩子入队列
3. 一直这样循环往复直到队列为空,说明最后一层已经没有节点了,遍历结束

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