二叉树的超详细讲解 | 深搜 | 广搜 | 深搜(非递归) 三实现 +完整可运行c语言代码 | 万字长文带你吃透二叉树

文章目录

• 二叉树
• • 1.二叉树的顺序存储结构
  • • 前置知识
  • 2.二叉树的链式存储结构
  • • 前置知识
    • • 1. 二叉树的深度遍历(递归)
      • 2. 二叉树的深度遍历 (非递归)
      • • 2.1 非递归先序遍历
        • 2.2 非递归中序遍历
        • 2.3 非递归后序遍历
      • 3. 二叉树的广度遍历
    • 头文件部分
    • 实现
    • • 1. 建二叉树 并初始化
      • 2. 释放二叉树
      • 3.创建节点
      • 4. 插入节点
      • 5.访问节点
      • 6. 前序遍历
      • 7.中序遍历
      • 8.后序遍历
      • 9.层序遍历 (广度遍历)
      • 10. 非递归 前序遍历
      • 11. 非递归 中序遍历
      • 12. 非递归 后序遍历
    • 测试案例
    • • main函数
      • 输出结果

二叉树

1.二叉树的顺序存储结构

前置知识

二叉树的顺序存储结构就是用一维数组存储二叉树中的节点,并且结点的存储位置,也就是数组的下标要能体现结点间的逻辑关系

​ 例如 :

可以看到有点浪费空间 如果我们考虑一种极端的情况—>右斜树

可以看到非常的浪费空间,所以顺序存储结构一般只用于完全二叉树

2.二叉树的链式存储结构

前置知识

​ 先看看二叉树的链式存储结构的样子吧 (这种存储结构是二叉链表)

1. 二叉树的深度遍历(递归)

所谓深度遍历 就是沿着一个方向一直走,直到不能再走,再返回 —-> 递归思想 (前序 中序 后序)

1.先序遍历 —-> 根左右
2.中序遍历 —-> 左根右
3.后序遍历 —-> 左右根

其实这三个只要理解递归之后就会非常的容易 —-> 后面会更一篇关于递归的到时候会仔细详解的 —-> 这里主要说二叉树的就不再多说了

其实本节的精髓在 非递归写法 嘿嘿！！

​ 既然说到递归下面贴一张先序递归的图 (这个图忘记在哪找到的了)

这个其实不想多说了 递归实现的树很简单

下面介绍个更好理解 先序 中序 后序的方法 (本质)

先抛开先序 中序 后序 不谈

深搜中每个结点会被访问三次 —-> 就是自己 自己从左边返回 自己从右边返回
从这三次中 选择一次作为访问触发时机

A B B C D D D C C B A E E F G H H H G K K K G F F E A

先序遍历就是 ABCDEFGHK —-> 保留每个节点第一次出现的位置
中序遍历就是 BDCAEHGKF —-> 保留每个节点第二次出现的位置
后序遍历就是 DCBHKGFEA —-> 保留每个节点第三次出现的位置

2. 二叉树的深度遍历 (非递归)

上面的递归遍历写法 肯定很多人都会 感觉没意思
下面主要讲讲非递归 深度遍历的

只要是递归函数 想变成 非递归 基本思路: 用栈

递归的特点就是保护现场然后进到下一个任务 当从下一个任务回来后可以恢复现场 然后进入到之前没做完的事情继续处理
再联系下栈的特点

2.1 非递归先序遍历

* 非递归实现先序遍历，基本思路：
* 先序的结果是 当前节点，再左节点，最后右节点，把栈当作任务的暂存空间
* 先压右节点，再压左节点，一旦弹栈，出现的是左节点 !!! */

* 基本步骤：
* 1. 初始化部分
* 将根节点压栈
* 2. 循环处理任务部分
* 2.1 弹栈，访问弹出来的节点，判断节点有右先压右，有左再压左，保证先右后左
* 2.2 循环出栈，直到栈内无元素
*

下面的具体实现可以去看代码部分了

牢记那句话即可 一旦弹栈 先压右节点再压左节点

理解上面的思路后 这个图就很好看懂了

2.2 非递归中序遍历

* 非递归实现中序遍历，基本思路：

* 1.以根节点开始 整条左边进栈 从栈中弹出节点 开始访问
* 2.如果这个节点有右孩子，把右孩子当作新节点
* 3.再次整条左边进栈 再弹栈

下面的具体实现可以去看代码部分了

理解上面的思路后 这个图就很好看懂了

2.3 非递归后序遍历

* 非递归实现后序遍历,基本思路:

* 双栈法 (这个方法更好理解 实现也简单)
* 栈1 根(弹根)->左->右入栈 弹给栈2
* 栈2 根->右->左存放 倒序就是 左->右->根

* 基本步骤
* 1.初始化部分
* 将根节点压栈
* 2.循环处理任务部分
* 2.1 弹栈给栈2 访问弹出来的节点 判断节点有左先压左 有右先压右 保证先左后右
* 2.2 最后弹出栈2中的元素即可
*

下面的具体实现可以去看代码部分了

理解上面的思路后 这个图就很好看懂了

3. 二叉树的广度遍历

所谓广度遍历也叫层序遍历：从上到下逐层,每层从左往右逐个访问节点，利用队列来实现
我们可以这样理解—> 访问一个节点时（消费者），发现两个新任务（生产者）引入队列来解决

* 广度遍历 (层序遍历)
* 1 引入一个任务队列先把根节点入队
* 2 从任务队列中，取出一个节点，处理它（访问）
* 3 如果2步的节点，有左那么就入队，有右那么就入队
* 4 重复第2步

入队
出队：获取到一个新任务 处理新任务（printf），有左节点，入左节点，有右节点，入右节点

头文件部分

#define MaxQueueSize 8 //用于层序遍历的队列大小

typedef int Element;

//二叉树的节点
typedef struct _tree_node
{
Element data;
struct _tree_node *left;
struct _tree_node *right;
} TreeNode;

// 二叉树的树头
typedef struct
{
TreeNode *root;
int count; //树中节点数量
} BinaryTree;

//1. 建二叉树 并初始化
BinaryTree *createBinaryTree(TreeNode *root);
//2. 释放二叉树
void releaseBinaryTree(BinaryTree *tree);
//3. 创建节点
TreeNode *createTreeNode(Element e);

//4. 插入节点
void insertBinaryTree(BinaryTree *tree, TreeNode *parent, TreeNode *left, TreeNode *right);
//5. 访问节点
void visitTreeNode(const TreeNode *node);

//6. 前序遍历
void preOrderBTree(const BinaryTree *tree);
//7.中序遍历
void inOrderBTree(const BinaryTree* tree);
//8.后序遍历
void postOrderBTree(const BinaryTree* tree);
//9.层序遍历 (广度遍历)
void levelOrderBTree(const BinaryTree *tree);

//10. 非递归 前序遍历
void preOrderBtreeNoRecursion(const BinaryTree *tree);
//11. 非递归 中序遍历
void inOrderBtreeNoRecursion(const BinaryTree *tree);
//12. 非递归 后序遍历
void postOrderBtreeNoRecursion(const BinaryTree* tree);

//加const 是因为只读 不可改

/* 这里多说一点 10 11 12 要用到栈 因为是纯c语言代码 所以就不用STL中库中的 stack
我用了我之前写过的栈 下面是一些接口 想看具体实现的可以去主页数据结构专栏 翻找
*/

/* 递增空栈 */

//1.初始化栈空间
void initArrayStack(ArrayStack *stack);

//2.入栈
void pushArrayStack(ArrayStack *stack, Element e);

//3.出栈
void popArrayStack(ArrayStack *stack);

//4.获取栈顶元素
Element getTopArrayStack(const ArrayStack *stack);

//5.判断栈是否为空
int isEmptyArrayStack(const ArrayStack *stack);

//6.判断栈是否为满
int isFullArrayStack(const ArrayStack *stack);

实现

1. 建二叉树 并初始化

BinaryTree* creatBinaryTree(TreeNode* root)
{
//在堆上申请
BinaryTree* tree = malloc(sizeof(BinaryTree));
if (tree == NULL) {
fprintf(stderr, "tree malloc failed!\\n");
return NULL;
}

//初始化
if (root)
{
tree->root = root;
tree->count = 1;
}
else
{
tree->root = NULL;
tree->count = 0;
}

//返回该树
return tree;
}

2. 释放二叉树

//释放一棵树最简单思想 —> 后序遍历 左边释放完 右边释放完 再释放自己
static void FreeBTNode(TreeNode* node ,BinaryTree *tree)
{
if (node)
{
//1.释放左子树
FreeBTNode(node->left, tree);
//2.释放右子树
FreeBTNode(node->right, tree);
//3.释放根
free(node);

//减少树中节点数量
tree->count—;
}
}

void releaseBinaryTree(BinaryTree* tree)
{
if (tree->root)
{
//调用对内接口
FreeBTNode(tree->root, tree);

//打印树中节点数量
printf("BinaryTree Have %d Node!\\n", tree->count);
}
}

3.创建节点

//3. 创建节点
TreeNode* createTreeNode(Element e)
{
//堆上申请
TreeNode* node = malloc(sizeof(TreeNode));
node->data = e;
node->left = node->right = NULL;

//返回该节点
return node;
}

4. 插入节点

void insertBinaryTree(BinaryTree* tree, TreeNode* parent, TreeNode* left, TreeNode* right)
{
if (tree && parent)
{
parent->left = left;
parent->right = right;

//下面这两个if 如果传了一个NULL呢
if (left) {
tree->count++;
}
if (right) {
tree->count++;
}
}
}

5.访问节点

void vistTreeNode(const TreeNode* node)
{
if(node)
{
printf(" \\t%c", node->data);
}
}

6. 前序遍历

static void preOrderNode(const TreeNode *node)
{
if (node)
{
//根
vistTreeNode(node);
//左
preOrderNode(node->left);
//右
preOrderNode(node->right);
}
}

void PreOrderBTree(const BinaryTree* tree)
{
//调用对内接口
preOrderNode(tree->root);
printf("\\n");
}

7.中序遍历

static void inOrderNode(const TreeNode* node)
{
if (node)
{
//左
inOrderNode(node->left);
//根
vistTreeNode(node);
//右
inOrderNode(node->right);
}
}

void inOrderBTree(const BinaryTree* tree)
{
//调用对内接口
inOrderNode(tree->root);
printf("\\n");
}

8.后序遍历

static void postOrderNode(const TreeNode* node)
{
if (node)
{
//左
postOrderNode(node->left);
//右
postOrderNode(node->right);
//根
vistTreeNode(node);
}
}

void postOrderBTree(const BinaryTree* tree)
{
//调用对内接口
postOrderNode(tree->root);
printf("\\n");
}

9.层序遍历 (广度遍历)

/* 广度遍历 (层序遍历)
* 1 引入一个任务队列先把根节点入队
* 2 从任务队列中，取出一个节点，处理它（访问）
* 3 如果2步的节点，有左那么就入队，有右那么就入队
* 4 重复第2步
*/

void levelOrderBTree(const BinaryTree* tree)
{
// 申请一个任务队列，用顺序存储（用完就消失），循环队列，队列的每个元素应该是节点的地址
// (关于循环队列 我主页数据结构专栏 专门讲过 感兴趣可以去看看)

TreeNode* queue[MaxQueueSize];
int front, rear; //头尾 "指针"

// 初始化循环队列
//1 引入一个任务队列先把根节点入队
front = rear = 0;
queue[rear] = tree->root;
rear = (rear + 1) % MaxQueueSize;

//开始循环系统处理
while (front != rear)
{
//2 从任务队列中，取出一个节点，处理它（访问）
TreeNode* node = queue[front];
front = (front + 1) % MaxQueueSize;
vistTreeNode(node);

//3 如果2步的节点，有左那么就入队，有右那么就入队
if (node->left) {
queue[rear] = node->left;
rear = (rear + 1) % MaxQueueSize;
}
if (node->right) {
queue[rear] = node->right;
rear = (rear + 1) % MaxQueueSize;
}

//4 重复第2步
}
}

10. 非递归 前序遍历

/* 基本步骤：
* 1. 初始化部分
* 将根节点压栈
* 2. 循环处理任务部分
* 2.1 弹栈，访问弹出来的节点，判断节点有右先压右，有左再压左，保证先右后左
* 2.2 循环出栈，直到栈内无元素
*/

void preOrderBtreeNoRecursion(const BinaryTree* tree) {
//1. 初始化部分
ArrayStack stack;
initArrayStack(&stack);
//将根节点压栈
pushArrayStack(&stack, tree->root);

TreeNode* node;
//2. 循环处理任务部分
while (!isEmptyArrayStack(&stack))
{
// 2.1 弹栈，访问弹出来的节点
node = getTopArrayStack(&stack);
popArrayStack(&stack);
vistTreeNode(node);

//判断节点有右先压右，有左再压左，保证先右后左
if (node->right)
{
pushArrayStack(&stack, node->right);
}
if (node->left)
{
pushArrayStack(&stack, node->left);
}

//2.2 循环出栈，直到栈内无元素
}
}

11. 非递归 中序遍历

/* 非递归实现中序遍历，基本思路：

* 1.以根节点开始 整条左边进栈 从栈中弹出节点 开始访问
* 2.如果这个节点有右孩子，把右孩子当作新节点
* 3.再次整条左边进栈 再弹栈
*/

void inOrderBtreeNoRecursion(const BinaryTree* tree)
{
//初始化栈
ArrayStack stack;
initArrayStack(&stack);

TreeNode* node=tree->root;

while (!isEmptyArrayStack(&stack) || node)
{
if (node)
{
//1.以根节点开始 整条左边进栈
pushArrayStack(&stack,node);
node = node->left;
}
else
{
//从栈中弹出节点 开始访问
node = getTopArrayStack(&stack);
popArrayStack(&stack);
vistTreeNode(node);

//2.如果这个节点有右孩子，把右孩子当作新节点
node = node->right;
}
//3.再次整条左边进栈 再弹栈
}
}

12. 非递归 后序遍历

/* 非递归实现后序遍历,基本思路:

* 双栈法 (这个方法更好理解 实现也简单)
* 栈1 根(弹根)->左->右入栈 弹给栈2
* 栈2 根->右->左存放 倒序就是 左->右->根

* 基本步骤
* 1.初始化部分
* 将根节点压栈
* 2.循环处理任务部分
* 2.1 弹栈给栈2 访问弹出来的节点 判断节点有左先压左 有右先压右 保证先左后右
* 2.2 最后弹出栈2中的元素即可
*/

void postOrderBtreeNoRecursion(const BinaryTree* tree)
{
//1.初始化部分
ArrayStack stack1;
ArrayStack stack2;

initArrayStack(&stack1);
initArrayStack(&stack2);

//将根节点压栈
TreeNode* node = tree->root;
pushArrayStack(&stack1, node);

//2.循环处理任务部分
while (!isEmptyArrayStack(&stack1))
{
// 2.1 弹栈给栈2
TreeNode* pop_node = getTopArrayStack(&stack1);
popArrayStack(&stack1);
pushArrayStack(&stack2,pop_node);

//访问弹出来的节点 判断节点有左先压左 有右先压右 保证先左后右
if (pop_node->left)
{
pushArrayStack(&stack1, pop_node->left);
}

if (pop_node->right)
{
pushArrayStack(&stack1, pop_node->right);
}
}

// 2.2 最后弹出栈2中的元素即可
while (!isEmptyArrayStack(&stack2))
{
node = getTopArrayStack(&stack2);
popArrayStack(&stack2);

vistTreeNode(node);
}
}

测试案例

main函数

//建树 这个其实就是上面反复出现的那一张树的图
BinaryTree* initTree1()
{
TreeNode* nodeA = createTreeNode('A');
TreeNode* nodeB = createTreeNode('B');
TreeNode* nodeC = createTreeNode('C');
TreeNode* nodeD = createTreeNode('D');
TreeNode* nodeE = createTreeNode('E');
TreeNode* nodeF = createTreeNode('F');
TreeNode* nodeG = createTreeNode('G');
TreeNode* nodeH = createTreeNode('H');
TreeNode* nodeK = createTreeNode('K');

BinaryTree* tree = creatBinaryTree(nodeA);
insertBinaryTree(tree, nodeA, nodeB, nodeE);
insertBinaryTree(tree, nodeB, NULL, nodeC);
insertBinaryTree(tree, nodeE, NULL, nodeF);
insertBinaryTree(tree, nodeC, nodeD, NULL);
insertBinaryTree(tree, nodeF, nodeG, NULL);
insertBinaryTree(tree, nodeG, nodeH, nodeK);
/* A
/ \\
B E
\\ \\
C F
/ /
D G
/ \\
H K
*/

//返回该树
return tree;
}

//递归树遍历
void test01()
{
//初始化树
BinaryTree* tree = initTree1();
printf("tree count:%d\\n", tree->count);

//前序遍历
printf("PreOrder travel:");
PreOrderBTree(tree);

//中序遍历
printf("inOrder travel:");
inOrderBTree(tree);

//后序遍历
printf("postOrder travel:");
postOrderBTree(tree);

//层序遍历
printf("LevelOrder travel:");
levelOrderBTree(tree);

printf("\\n");
//释放树
releaseBinaryTree(tree);
}

//非递归树遍历
void test02()
{
//初始化树
BinaryTree* tree = initTree1();
printf("tree count:%d\\n", tree->count);

//前序 非递归
printf("NoRecursion preOrder trsvel:");
preOrderBtreeNoRecursion(tree);
printf("\\n");

//中序 非递归
printf("NoRecursion inOrder trsvel:");
inOrderBtreeNoRecursion(tree);
printf("\\n");

//后序 非递归
printf("NoRecursion postOrder trsvel:");
postOrderBtreeNoRecursion(tree);

printf("\\n");
//释放树
releaseBinaryTree(tree);
}

int main()
{
//test01();
test02();
return 0;
}

输出结果

//test01() 递归遍历 和 层序遍历
tree count:9
PreOrder travel: A B C D E F G H K
inOrder travel: B D C A E H G K F
postOrder travel: D C B H K G F E A
LevelOrder travel: A B E C F D G H K
BinaryTree Have 0 Node!

//test02() 非递归遍历
tree count:9
NoRecursion preOrder trsvel: A B C D E F G H K
NoRecursion inOrder trsvel: B D C A E H G K F
NoRecursion postOrder trsvel: D C B H K G F E A
BinaryTree Have 0 Node!

​ 嘻嘻嘻嘻 普通二叉树部分到此结束😆😆

​ 线索二叉树 二叉搜索树 二叉平衡树 并查集 哈夫曼树 红黑树 B树 静候更新 👻👻👻😸😸😸

​ (有错误欢迎指出) (疑问也是)❤️❤️😍😍💖💖

​ 持续更新中…

​ 唠唠嗑 下周去考四级了 四级我还没过 我真的服啦🤣🤣