二叉树的遍历
扫描二维码
随时随地手机看文章
1、定义
---- 二叉树的遍历(traversing binary tree)是指从根结点出发,按照某种次序依次访问二叉树中所有结点,使得每个结点被访问一次且仅被访问一次。
2、遍历算法
---- 限定先左结点后右结点后,主要的遍历算法分为四种:
--1)前序遍历(根结点--左子树--右子树)
规则是若二叉树为空,则空操作返回,否则先访问根结点,然后前序遍历左子树,再前序遍历右子树。
如下图所示的二叉树,前序遍历结果是:ABDECF
--2)中序遍历(左子树--根结点--右子树)
规则是若树为空,则空操作返回,否则从根结点开始(注意并不是先访问根结点),中序遍历根结点的左子树,然后是访问
根结点,最后中序遍历右子树。
上图所示二叉树的中序遍历结果是:DBEAFC
--3)后序遍历(左子树--右子树--根结点)
规则是若树为空,则空操作返回,否则从左到右先遍历左子树,再遍历左子树,最后访问根结点。
上图所示二叉树的后序遍历结果是:DEBFCA
--4)层序遍历
规则是若树为空,则空操作返回,否则从树的第一层,也就是根结点开始访问,从上而下逐层遍历,在同一层中,按从左到右
的顺序对结点逐个访问。上图所示二叉树的层序遍历结果是:ABCDEF
具体算法如下:
#includeusing namespace std; typedef int TElemType; typedef struct BTNode //结点结构 { TElemType data;//结点数据 struct BTNode *lchild,*rchild; //左右孩子指针 }BNode,*BTree; //前序遍历 void preorder(BNode * root) { if(root!=NULL) { printf("%d",root->data); preorder(root->lchild); preorder(root->rchild); } } //中序遍历 void inorder(BNode * root) { if(root!=NULL) { inorder(root->lchild); printf("%d",root->data); inorder(root->rchild); } } //后序遍历 void postorder(BNode * root) { if(root!=NULL) { postorder(root->lchild); postorder(root->rchild); printf("%d",root->data); } } //二叉树的叶子节点数 int leaf(BNode * root) { if(root==NULL) //空树 return 0; int L,R; if(root->lchild==NULL && root->rchild==NULL) //叶子结点 return 1; L = leaf(root->lchild); //统计左子树的叶子数 R = leaf(root->rchild); //统计右子树的叶子数 return L+R; }