一、二叉树的遍历原理
1.1原理:
二叉树的遍历(traveing binary tree)是指从根结点出发,按照某种次序依次访问二叉树中所有的结点,使每个结点都被访问一次,且仅被访问一次。
这里有两个关键词:访问和次序。
1.2.1访问
访问其实是要根据实际的需要来确定具体做什么,比如对每个结点进行相关计算,输出打印等,它算作是一个抽象操作。在这里我们可以简单地假定就是输出结点的数据信息。
1.2.2次序
二叉树的遍历次序不同于线性结构,最多也就是从头至尾、循环、双向等简单的遍历方式。树的结点之间不存在唯一的前驱和后继关系,在访问一个结点后,下一个被访问的结点面临着不同的选择就像你人生的道路上,高考填志愿要面临哪个城市、哪所大学、具体专业等选择,由选择方式的不同,遍历的次序就完全不同了。
二、二叉树的前序、中序、后序遍历
2.1二叉树遍历的几种方式
二叉树的遍历方式可以很多,如果我们限制了从左到右的习惯方式,那么主要就分为四种:
前序遍历、中序遍历、后序遍历、层次遍历。
这四种遍历方式的基本顺序和在数组中存储的形式如下图所示:
2.2前序遍历
规则是若 叉树为空,则空操作返回,否则先访问根结点,然后前序遍历左子树,再前序遍历右子树。如图遍历的顺序为: ABDGHCEIF
步骤:1、先造一颗树
造树:
#include<stdio.h> #include<stdlib.h> typedef int BTDataType; typedef struct BinaryTreeNode { struct BinaryTreeNode* left; struct BinaryTreeNode* right; BTDataType data; }BTNode; malloc一块空间 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; }
2、写前序遍历和main函数
void PrevOrder(BTNode* root)//前序遍历 { if (root == NULL)//如果根是空就return { printf("NULL "); return; } printf("%d ", root->data); PrevOrder(root->left);//左子树 PrevOrder(root->right);//右子树 } int main() { BTNode* tree = CreatBinaryTree(); PrevOrder(tree); return 0; }
程序运行结果 :(对照1、2、3、4、5、6)上图
2.3中序遍历
规则是若树为空,则空操作返回,否则从根结点开始(注意并不是先访问根结 点) ,中序遍历根结点的左子树,然后是访问根结点,最后中序遍历右子树 如图所示, 遍历的顺序为GDHBAELCF.
void InOrder(BTNode* root)//中序遍历 { if (root == NULL)//如果根是空就return { printf("NULL "); return; } InOrder(root->left);//先左子树 printf("%d ", root->data); InOrder(root->right);//再右子树 } int main() { BTNode* tree = CreatBinaryTree(); InOrder(tree); return 0; }
程序运行结果
2.4后序遍历
规则是若树为空,则空操作返回,否则从左到右先叶子后结点的方式遍历访问左右子树,最后是访问根结点 如图所示 遍历的顺序为 GHDBIEFCA。
void BackOrder(BTNode* root) { if (root == NULL)//如果根是空就return { printf("NULL "); return; } BackOrder(root->left); BackOrder(root->right); printf("%d ", root->data); } int main() { BTNode* tree = CreatBinaryTree(); BackOrder(tree); return 0; }
程序运行结果:
二叉树的遍历的几种路径 (小结):网上找的图
2.5层序遍历
层序遍历:除了先序遍历、中序遍历、后序遍历外,还可以对二叉树进行层序遍历。设二叉树的根节点所在 层数为1,层序遍历就是从所在二叉树的根节点出发,首先访问第一层的树根节点,然后从左到右访问第2层 上的节点,接着是第三层的节点,以此类推,自上而下,自左至右逐层访问树的结点的过程就是层序遍历。
层序遍历与之前的三种遍历情况有所不同,层序遍历的实现依赖于队列,会比较麻烦一些。
//层序遍历 void LevelOrder(BTNode* root) { Queue q; QueueInit(&q); if (root) { QueuePush(&q, root);//先插入根节点 } while (QueueEmpty(&q)) { BTNode* front = QueueFront(&q); QueuePop(&q);//把队列里根节点的指针拿出来,但是指针指向的节点的值没有被销毁; printf("%d ", front->data); if (front->left) { QueuePush(&q, front->left); } if (front->right) { QueuePush(&q, front->right); } printf("\n"); } QueueDestry(&q); }
三、二叉树的拓展
3.1计算树的结点的个数
low版(代码比较挫)但是容易理解
int count = 0; void BTreeSize(BTNode* root) { if (root == NULL) return; ++count; BTreeSize(root->left); BTreeSize(root->right); //后序 }
注意:
这里为什么不用static静态变量。
因为静态变量在静态区,是整个程序结束后才销毁,而且局部静态变量不能置零
所以如果再计算下一个树的结点就会和上一个树累加。
static只初始化一次,所以要么就是全局静态变量。
具体的调用方法://更好的计数方法,既不使用全局,也不使用静态变量-
//思想遍历加计数(传地址调用)指针
void BTreeSize(BTNode* root, int* pCount) { if (root == NULL) return; ++(*pCount);//把一个变量的地址传过去 BTreeSize(root->left, pCount); BTreeSize(root->right, pCount); //后序 }
3.2计算树的叶子结点的个数
思路:叶子结点的左右结点都为空,递归+分治思想
因此:代码如下
int BTreeLaafSize(BTNode* root) { if (root == NULL) return 0; if (root->left == NULL && root->right == NULL) return 1; return BTreeLaafSize(root->left) + BTreeLaafSize(root->right); }