赞
踩
二叉树主要有两种遍历方式:
前中后序指的就是根的遍历顺序,
前序遍历就是先访问根,再遍历左子树,最后遍历右子树。
中序遍历就是先遍历左子树,再访问根,最后遍历右子树。
后序遍历就是先遍历左子树,再遍历右子树,最后访问根。
以这棵二叉树为例,这里也列出访问到NULL的位置。
前序遍历:1 2 3 NULL NULL NULL 4 5 NULL NULL 6 NULL NULL
中序遍历:NULL 3 NULL 2 NULL 1 NULL 5 NULL 4 NULL 6 NULL
后序遍历:NULL NULL 3 NULL 2 NULL NULL 5 NULL NULL 6 4 1
以下文字解释前序和中序是怎样遍历的(我觉得文字更适合理解,如果你有耐心看完的话。动图无论看多少遍也只是知道个顺序,对递归的思想理解不够深刻):
(荧光笔记号表示记录)
前序遍历:先访问根1,再访问左子树,子树依然要按照根左右的方式遍历,那么先访问根2,再访问左子树,左子树的根是3,访问完根3,再访问它的左子树,左子树是NULL,就回退,再访问右子树,右子树也是NULL,继续回退,那么3这棵树访问完毕,3是2的左子树,接下来回退,访问2的右子树,2的右子树是NULL,此时2这棵树也访问完毕,回退,访问根的右子树,先访问根4,再访问左子树5,5的左子树是NULL,右子树也是NULL,回退,访问根4的右子树6,6的左子树是NULL右子树是NULL,回退,这样4这棵子树访问完毕,整棵树就访问完毕。
中序遍历:要遍历整棵树,先遍历左子树,1的左子树是2,2的左子树是3,3的左子树NULL,回退,记录3,然后记录3的右子树NULL,这样以3为根的子树遍历完毕,它是2的左子树,回退,接下来记录2,再记录2的右子树NULL,2这棵树就遍历完毕,回退,接下来记录1,然后遍历1的右子树,右子树依然要保证左根右的顺序,先遍历4的左子树5,5的左子树NULL,回退,根5,右子树NULL,这样5这棵树遍历完毕,它是4的左子树,回退,记录根4,然后遍历右子树6,6的左子树NULL,回退,根6,右子树NULL,这样6这棵树遍历完毕,4这棵树也就遍历完毕,整棵树就遍历完毕。
后序也是一样的道理。
可以发现,中序和后序不是走到一个结点就一定会把这个结点记录下来,因为它必须先遍历这个结点的左子树,
注意体会其中的递归思想,把遍历一棵树,化为遍历它的各个子树。
前序就像绕外围逆时针跑一圈,中序就是向下投影,后序就像是剪葡萄。这种虽然很好理解,但是抛弃了递归思想,适合人脑,不适合电脑。想写好代码还是要多多理解递归思想。
层序遍历:
从左往右从上往下一层一层地遍历,顺序就和二叉树的顺序存储一样。如上图,层序遍历结果为124356
练习:
1.已知某二叉树的中序遍历序列为JGDHKBAELIMCF,后序遍历序列为JGKHDBLMIEFCA,则其前序遍历序列为( )
A. ABDGHJKCEFILM
B. ABDGJHKCEILMF
C. ABDHKGJCEILMF
D. ABDGJHKCEIMLF
答案:B
结合中序和后序,我们可以构造出这棵二叉树:
后序遍历序列从右往左看,A一定是根。C在A的左边还是右边呢,结合中序遍历序列,C在A的右边,所以C是A的右孩子。F在C的右边,F是C的右孩子。E在A的右边,C的左边,所以是C的左孩子。I在E的右边,C的左边,所以是E的右孩子。M在I的右边C的左边,所以是I的右孩子。L在E的右边,I的左边,所以是I的左孩子。B在A的左边,所以是A的左孩子,D在B的左边,所以是B的左孩子,H在B的左边,D的右边,所以是D的右孩子。K在H的右边B的左边,所以是H的右孩子。G在D的左边,所以是D的左孩子。J在G的左边,所以是G的左孩子。
最终构建的二叉树如图。
前序遍历就像绕着外围逆时针走一圈,序列为ABDGJHKCEILMF,选B
2.已知某二叉树的前序遍历序列为ABDEC,中序遍历序列为BDEAC,则该二叉树( )
A. 是满二叉树
B. 是完全二叉树,不是满二叉树
C. 不是完全二叉树
D. 是所有的结点都没有右子树的二叉树
前序遍历从左往右看,A一定是根。B在A的左边,B是A的左孩子。D在B的右边,A的左边,D是B的右孩子。E在D的右边,A的左边,E是D的右孩子。C在A的右边,C是A的右孩子。
最终构建的二叉树如图
很明显,选C。
二叉树的递归构建放到后面讲。先从最简单的遍历开始。
这里手动构建一棵二叉树。
typedef int BTDataType; typedef struct BinaryTreeNode { struct BinaryTreeNode* left; struct BinaryTreeNode* right; BTDataType data; }BTNode; BTNode* BuyBTNode(BTDataType x) { BTNode* node = (BTNode*)malloc(sizeof(BTNode)); if (node == NULL) { printf("malloc fail\n"); exit(-1); } node->data = x; node->left = node->right = NULL; return node; } BTNode* CreatBinaryTree() { BTNode* node1 = BuyBTNode(1); BTNode* node2 = BuyBTNode(2); BTNode* node3 = BuyBTNode(3); BTNode* node4 = BuyBTNode(4); BTNode* node5 = BuyBTNode(5); BTNode* node6 = BuyBTNode(6); node1->left = node2; node1->right = node4; node2->left = node3; node4->left = node5; node4->right = node6; return node1; }
以下就是递归遍历,写递归要注意三要素:
前序遍历
void PrevOrder(BTNode* root) { // 确定参数和返回类型
if (root == NULL) return; //遇到NULL就回退,也就是遇到NULL就终止这一层递归
printf("%d ", root->data); //前序是根左右,逻辑就是先打印根结点的值,再去遍历左子树,最后遍历右子树
PrevOrder(root->left);
PrevOrder(root->right);
}
中序和后序同理
中序遍历
void InOrder(BTNode* root) {
if (root == NULL) return;
InOrder(root->left);
printf("%d ", root->data);
InOrder(root->right);
}
后序遍历
void PostOrder(BTNode* root) {
if (root == NULL) return;
PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->data);
}
不难写出如下代码:
void BTreeSize(BTNode* root, int* count)
{
if (root == NULL) return;
(*count)++;
BTreeSize(root->left, count);
BTreeSize(root->right, count);
}
遍历+递归计数,先定义一个局部变量count = 0,传地址进去。也可以直接把count定义为全局变量;
注意:不要把局部变量定义在递归函数内部,否则每一层递归都会重新创建一个新的局部变量,每次回退都会自动销毁这个局部变量。
就算是static定义的静态局部变量也不行,因为无法重新初始化,多次调用计数只会叠加。
优化(分治):
先把大问题转换为小的子问题:一棵树的结点数就是它的左子树的结点数+右子树的结点数+根结点数1,
这种做法叫做分治,字面意思就是“分而治之”,把大问题转化为两个或多个相似的子问题,再把子问题分成更小的子问题,直到最后的子问题简单到可以直接求解。
重新思考递归三要素:
BTNode* root
,返回类型为int
int BTreeSize(BTNode* root) {
return root == NULL ? 0 : BTreeSize(root->left) + BTreeSize(root->right) + 1;
}
也可以采用遍历+计数的方法。只要在计数前加if
判断左右子树是否满足都为空的条件即可。
我们重点讲分治:一棵树的叶子结点树就是它的左子树的叶子结点数+右子树的叶子结点数
递归三要素:
int BTreeLeafSize(BTNode* root)
{
if (root == NULL) return 0;
if (root->left == NULL && root->right == NULL) return 1;
return BTreeLeafSize(root->left) + BTreeLeafSize(root->right);
}
也可以采用遍历+计数的方法。但是如果树很大,k很小,难道也要全部遍历一遍吗?
可能你会想到层序遍历,那当然也可以,我们放到后面讲。
分治:一棵二叉树第k层的结点个数就是左子树第k-1层的结点数+右子树第k-1层的结点数。
递归三要素:
BTNode* root, int k
,返回类型为int
int BTreeKLevelSize(BTNode* root, int k)
{
assert(k >= 1);
if (root == NULL) return 0;
if (k == 1) return 1;
return BTreeKLevelSize(root->left, k - 1) + BTreeKLevelSize(root->right, k - 1);
}
分治:一棵二叉树的深度就是左子树的深度和右子树的深度中大的那个+1,+1是因为根结点自己算一个深度。
递归三要素:
BTNode* root
,返回类型为int
int BTreeDepth(BTNode* root)
{
if (root == NULL) return 0;
int leftDepth = BTreeDepth(root->left);
int rightDepth = BTreeDepth(root->right);
return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
分治:一棵二叉树中值为x的结点就是左子树中值为x的结点或者右子树中值为x的结点或者根结点。
递归三要素:
BTNode* root, BTDataType x
,返回类型BTNode*
&&
和||
,除非返回类型是bool
。而这里是要具体地返回一个地址。BTNode* BTreeFind(BTNode* root, BTDataType x)
{
if (root == NULL) return NULL;
if (root->data == x) return root;
BTNode* ret1 = BTreeFind(root->left, x);
if (ret1) return ret1;
BTNode* ret2 = BTreeFind(root->right, x);
if (ret2) return ret2;
return NULL;
}
最后三行可以简化成一行return BTreeFind(root->right, x)
,为了保证可读性,建议还是像上面那样写。
采用后序遍历的方式,保证根最后释放。
void BTreeDestory(BTNode* root)
{
if (root == NULL) return;
BTreeDestory(root->left);
BTreeDestory(root->right);
free(root);
}
本文一开始手动创建二叉树,然后先讲了三种遍历。
现在我们来试着采用前序遍历的方法递归创建。
给定前序遍历序列,比如ABC##DE#G##F###,其中“#”表示空格,空格表示空树。
以此建立二叉树。
递归三要素:
char* a, int* i
返回类型为BTNode*
(*i)++
BTNode* CreateTree(char* a, int* i)
{
if (a[*i] == '#')
{
(*i)++;
return NULL;
}
BTNode* root = (BTNode*)malloc(sizeof(BTNode));
root->val = a[(*i)++];
root->left = CreateTree(a, i);
root->right = CreateTree(a, i);
return root;
}
这道题可以用这种方法创建二叉树
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。