写在前面
二叉树的几乎所有实现都是依靠递归实现,递归的核心思路是把任何一个二叉树看成根和左右子树,而二叉树递归的核心玩法就是把二叉树的左右子树再看成根,再找左右子树,再看成根...
因此,解决二叉树问题实际上要把二叉树转换成一个一个子树的过程,找到一个一个的子树再组装起来就形成了二叉树
二叉树的创建
二叉树建立的正统方法是利用递归,这里展示递归的一种写法
BTNode* BuyNode(BTDataType a)
{
BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
newnode->data = a;
newnode->left = NULL;
newnode->left = NULL;
return newnode;
}
BTNode* BinaryTreeCreate(BTDataType* a, int* pi)
{
if (a[*pi] == '#')
{
(*pi)++;
return NULL;
}
BTNode* root = BuyNode(a[*pi]);
(*pi)++;
root->left = BinaryTreeCreate(a, pi);
root->right = BinaryTreeCreate(a, pi);
return root;
}
如果你对递归的认识并不熟悉,下面我画了一幅递归展开图,更好解释这其中的原理
(右子树的部分过程由于空间原因不够完全展开,但如果看懂左子树的构建过程,右子树不难自己画出)
这里注意的是,函数栈帧的创建并不是每一个都不一样的位置,当一个栈帧被销毁后,另外一个栈帧创建就会在原来的位置,因此在计算空间复杂度的时候需要考虑这个问题:
==空间是可以重复利用的,时间是一去不复返的==
从这幅图中,相信可以理解这段代码的含义了
首先创建一个根节点,根节点去寻找左子树进入递归,而进入递归后继续寻找左子树...直到遇到NULL截止,而遇到空后就寻找右子树,右子树也找到空后返回,这样就构建出了二叉树中最小的一棵树,而这棵树会返回,作为根的左子树,然后继续进入递归寻找根的右子树...
由于是借助链表进行实现的,因此我们可以理解为首先创建好根,而根的左右子树用函数创建好后再连接起来...当遇到#就返回,形成了一个一个的小树,小树最后组成大树,就形成了二叉树
二叉树的遍历
二叉树的遍历主要有前序遍历,中序遍历,后序遍历,层序遍历
前序遍历
前序遍历是指遍历时先访问根,再访问左子树,再访问右子树
代码实现如下
void BinaryTreePrevOrder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
printf("%c ", root->data);
BinaryTreePrevOrder(root->left);
BinaryTreePrevOrder(root->right);
}
下面依旧画出它的递归展开图
中序遍历
中序遍历是先访问左子树,再访问根,最后访问右子树
void BinaryTreeInOrder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
BinaryTreeInOrder(root->left);
printf("%c ", root->data);
BinaryTreeInOrder(root->right);
}
递归图和上面基本类似,就不做画出了
后序遍历
后序遍历是先访问左子树,再访问右子树,最后访问根
void BinaryTreePostOrder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
BinaryTreePostOrder(root->left);
BinaryTreePostOrder(root->right);
printf("%c ", root->data);
}
递归图和上面基本类似,就不做画出了