二叉树前序遍历法举例!急急急！！！
前序遍历:1 2 4 8 9 10 11 5 3 6 7 (规律：根在前；子树在根后且左子树比右子树靠前)；
中序遍历:8 4 10 9 11 2 5 1 6 3 7 (规律：根在中；左子树在跟左边，右子树在根右边)；
后序遍历:8 10 11 9 4 5 2 6 7 3 1 (规律：根在后；子树在根前且左子树比右子树靠前)；
其它例子：
前序遍历:ABDECFG
中序遍历:DBEAFCG
后序遍历:DEBFGCA
前序遍历:1 2 4 3 5 7 6
中序遍历:2 4 1 5 7 3 6
后序遍历:4 2 7 5 6 3 1
做类似的题目，你可以先由两个遍历画出二叉树。通过形象的二叉树来写出另一个遍历，写的方法如上（递归）。画出二叉树的方法如下：
已知一棵二叉树的前序序列和中序序列，构造该二叉树的过程如下：
1. 根据前序序列的第一个元素建立根结点；
2. 在中序序列中找到该元素，确定根结点的左右子树的中序序列；
3. 在前序序列中确定左右子树的前序序列；
4. 由左子树的前序序列和中序序列建立左子树；
5. 由右子树的前序序列和中序序列建立右子树。
已知一棵二叉树的后序序列和中序序列，构造该二叉树的过程如下：
1. 根据后序序列的最后一个元素建立根结点；
2. 在中序序列中找到该元素，确定根结点的左右子树的中序序列；
3. 在后序序列中确定左右子树的后序序列；
4. 由左子树的后序序列和中序序列建立左子树；
5. 由右子树的后序序列和中序序列建立右子树。
//头文件
#ifndef _BINARYTREE_H_
#define _BINARYTREE_H_
#include"BinaryTreeNode.h"
#include
#include
using namespace std;
template
class BinaryTree
{
BinaryTreeNode* m_root;
protected:
BinaryTreeNode* Parent(BinaryTreeNode* root,BinaryTreeNode* p);
void Destroy(BinaryTreeNode* p);
public:
BinaryTree(){m_root=NULL;}
BinaryTree(T data){m_root=new BinaryTreeNode(data); }
virtual ~BinaryTree(void);
//判断是否为空树
bool IsEmpty()const{return m_root==NULL?true:false;}
//取得一个父节点的指针
BinaryTreeNode* GetParent(BinaryTreeNode* p){return Parent(m_root,p);}
//判断是否为左孩子
bool IsLeftChild(BinaryTreeNode* p){return p==GetParent(p)->GetLeftChild()?true:false;}
//判断是否为右孩子
bool IsRightChild(BinaryTreeNode* p){return p==GetParent(p)->GetRightChild()?true:false;}
//取得整棵树的树根
BinaryTreeNode* GetRoot(){return m_root;}
BinaryTreeNode* LeftChild(BinaryTreeNode* root)const
{return root==NULL?NULL:root->GetLeftChild();}
BinaryTreeNode* RightChild(BinaryTreeNode* root)const
{return root==NULL?NULL:root->GetRightChild();}
BinaryTreeNode* LeftSibling(BinaryTreeNode* leftChild);
BinaryTreeNode* RightSibling(BinaryTreeNode* rightChild);
//返回一个结点的数据
T Retrieve(BinaryTreeNode* p)const {return p->GetData()};
//设置一个结点的数据
void Assign(BinaryTreeNode* p,const T& d)const{p->SetData(d);}
void InsertRightChild(BinaryTreeNode* p,const T& d)const;
void InsertLeftChild(BinaryTreeNode* p,const T& d)const;
void DeleteRightChild(BinaryTreeNode* p){Destroy(p->GetRightChild());}
void DeleteLeftChild(BinaryTreeNode* p){Destroy(p->GetLeftChild());};
virtual void PreOrderTraverse(BinaryTreeNode* root)const; //先序遍历整棵树
virtual void InOrderTraverse(BinaryTreeNode* root)const; //中序遍历整棵树
virtual void PostOrderTraverse(BinaryTreeNode* root)const; //后序遍历整棵树
virtual void LevelOrderTraverse(BinaryTreeNode* root)const;//按层遍历整棵树
};
template
BinaryTree::~BinaryTree(void)
{
Destroy(m_root);
m_root=NULL;
}
template
void BinaryTree::Destroy(BinaryTreeNode* p)
{
if(p!=NULL)
{
Destroy(p->GetLeftChild());
Destroy(p->GetRightChild());
delete p;
}
}
template
void BinaryTree::InsertLeftChild(BinaryTreeNode* p,const T& d)const
{
BinaryTreeNode* q=new BinaryTreeNode(d);
q->SetLeftChild(p->GetLeftChild());
p->SetLeftChild(q);
}
template
void BinaryTree::InsertRightChild(BinaryTreeNode* p,const T& d)const
{
BinaryTreeNode* q=new BinaryTreeNode(d);
q->SetRightChild(p->GetRightChild());
p->SetRightChild(q);
}
//先序遍历的递归算法
//template
//void BinaryTree::PreOrderTraverse(BinaryTreeNode* root)const
//{
//if(root!=NULL)
//{
//coutGetData();
//PreOrderTraverse(root->GetLeftChild());
//PreOrderTraverse(root->GetRightChild());
//}
//}
//先序遍历的栈结构算法
template
void BinaryTree::PreOrderTraverse(BinaryTreeNode* root)const
{
stack*> s;
BinaryTreeNode* p=root;
while(!s.empty()||p!=NULL)
{
while(p)
{
s.push(p);
coutGetData();
p=p->GetLeftChild();
}
p=s.top();
s.pop();
p=p->GetRightChild();
}
}
//先序遍历的栈结构算法
template
void BinaryTree::InOrderTraverse(BinaryTreeNode* root)const
{
stack*> s;
BinaryTreeNode* p=root;
while(!s.empty()||p!=NULL)
{
while(p)
{
s.push(p);
p=p->GetLeftChild();
}
p=s.top();
s.pop();
coutGetData();
p=p->GetRightChild();
}
}
////后序遍历的递归算法
//template
//void BinaryTree::PostOrderTraverse(BinaryTreeNode* root)const
//{
//if(root!=NULL)
//{
//PreOrderTraverse(root->GetLeftChild());
//PreOrderTraverse(root->GetRightChild());
//}
//coutGetData();
//}
//按层遍历整棵树
template
void BinaryTree::LevelOrderTraverse(BinaryTreeNode* root)const
{
queue* > q;
if(root!=NULL)
{
q.push(root);
}
while(!q.empty())
{
root=q.front(),q.pop();
coutGetData();
if(root->GetLeftChild())
q.push(root->GetLeftChild());
if(root->GetRightChild())
q.push(root->GetRightChild());
}
}
//后序遍历的栈结构算法
template
void BinaryTree::PostOrderTraverse(BinaryTreeNode* root)const
{
stack*> s;
BinaryTreeNode* p=root;
while(!s.empty()||p!=NULL)
{
while(p)
{
s.push(p);
p=p->GetLeftChild();
}
p=s.top();
//coutGetData();
s.pop();
p=p->GetRightChild();
}
}
#endif
//-------------------------------------
//----主程序
#include
#include"BinaryTreeNode.h"
#include"BinaryTree.h"
using namespace std;
void main()
{
BinaryTree myBinTree('A');
myBinTree.InsertLeftChild(myBinTree.GetRoot(),'B');
myBinTree.InsertRightChild(myBinTree.GetRoot(),'C');
myBinTree.InsertLeftChild(myBinTree.GetRoot()->GetLeftChild(),'D');
myBinTree.InsertRightChild(myBinTree.GetRoot()->GetLeftChild(),'E');
myBinTree.InsertLeftChild(myBinTree.GetRoot()->GetRightChild(),'F');
myBinTree.InsertRightChild(myBinTree.GetRoot()->GetRightChild(),'G');
myBinTree.PreOrderTraverse(myBinTree.GetRoot());
cout<<endl;
myBinTree.InOrderTraverse(myBinTree.GetRoot());
cout<<endl;
myBinTree.PostOrderTraverse(myBinTree.GetRoot());
cout<<endl;
myBinTree.LevelOrderTraverse(myBinTree.GetRoot());
cout<<endl;
system("pause");
}
二叉树的三种金典遍历法
1.前序遍历法：
前序遍历（DLR）
前序遍历（DLR）
前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。
若二叉树为空则结束返回，否则：
（1）访问根结点
（2）前序遍历左子树
（3）前序遍历右子树
注意的是：遍历左右子树时仍然采用前序遍历方法。
如上图所示二叉树
前序遍历，也叫先根遍历，遍历的顺序是，根，左子树，右子树
遍历结果：ABDECF
中序遍历，也叫中根遍历，顺序是 左子树，根，右子树
遍历结果：DBEAFC
后序遍历，也叫后根遍历，遍历顺序，左子树，右子树，根
遍历结果：DEBFCA
2.中序遍历法：
中序遍历
中序遍历（LDR）
中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。在遍历左、右子树时，仍然先遍历左子树，再访问根结点，最后遍历右子树。即：
若二叉树为空则结束返回，否则：
（1）中序遍历左子树
（2）访问根结点
（3）中序遍历右子树。
注意的是：遍历左右子树时仍然采用中序遍历方法。
3.后序遍历法：
后序遍历
简介
后序遍历是二叉树遍历的一种。后序遍历指在访问根结点、遍历左子树与遍历右子树三者中，首先遍历左子树，然后遍历右子树，最后遍历访问根结点，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后遍历根结点。后序遍历有递归算法和非递归算法两种。
递归算法
算法描述：
（1）若二叉树为空，结束
（2）后序遍历左子树
（3）后序遍历右子树
（4）访问根结点
伪代码
PROCEDURE POSTRAV(BT)
IF BT<>0 THEN
{
POSTRAV(L(BT))
POSTRAV(R(BT))
OUTPUT V(BT)
}
RETURN
c语言描述
struct btnode
{
int d;
struct btnode *lchild;
struct btnode *rchild;
};
void postrav(struct btnode *bt)
{
if(bt!=NULL)
{
postrav(bt->lchild);
postrav(bt->rchild);
printf("%d ",bt->d);
}
}
非递归算法
算法1（c语言描述）：
void postrav1(struct btnode *bt)
{
struct btnode *p;
struct
{
struct btnode *pt;
int tag;
}st[MaxSize];
}
int top=-1;
top++;
st[top].pt=bt;
st[top].tag=1;
while(top>-1) /*栈不为空*/
{
if(st[top].tag==1) /*不能直接访问的情况*/
{
p=st[top].pt;
top--;
if(p!=NULL)
{
top++; /*根结点*/
st[top].pt=p;
st[top].tag=0;
top++; /*右孩子结点*/
st[top].pt=p->p->rchild;
st[top].tag=1;
top++; /*左孩子结点*/
st[top].pt=p->lchild;
st[top].tag=1;
}
}
if(st[top].tag==0) /*直接访问的情况*/
{
printf("%d ",st[top].pt->d);
top--;
}
}
}
算法2：
void postrav2(struct btnode *bt)
{
struct btnode *st[MaxSize],*p;
int flag,top=-1;
if(bt!=NULL)
{
do
{
while(bt!=NULL)
{
top++;
st[top]=bt;
bt=bt->lchild;
}
p=NULL;
flag=1;
while(top!=-1 && flag)
{
bt=st[top];
if(bt->rchild==p)
{
printf("%d ",bt->d);
top--;
p=bt;
}
else
{
bt=bt->rchild;
flag=0;
}
}
}while(top!=-1)
printf("
");
}
}
老曹回答 必属佳作 记得给分 谢谢合作！
请教一下数据结构 二叉树的先序遍历 中序遍历 后序遍历 是怎么弄的
所谓先序、中序和后序的区别在于访问根的时机，分别是BLR、LBR和LRB，其中B、L、R分别表示根结点、根结点的左子树和根结点的右子树。以后序遍历为例进行讲解。后序遍历算法：(1) 后序遍历根结点的左子树；(2) 后序遍历根结点的右子树。(3) 访问二叉树的根结点；你的方法是将树分解为根、左...
二叉树中,什么是前序,中序。后序!
3、特点为后续遍历的特点是执行操作时，肯定已经遍历过该节点的左右子节点，故适用于要进行破坏性操作的情况，比如删除所有节点 二叉树是数据结构中常被问到的相关知识点，也是需要了解的一个知识点，可以总结一下二叉树的前序、中序、后序遍历的相互求法，即如果知道两个的遍历，如何求第三种遍历方...
知道一颗二叉树的前序和中序遍历表示,怎么用c写他的后序表示
前序：根-左-右 中序：左-根-右 后序：左-右-根 举例：如果前序遍历为：ABDECFG,中序为：DBEAFGC 那么首先判断A为根结点，看中序，A左边的DBE为根结点左子树上的,FGC为右子树上的。又因为前序B，说明B为左子树的根结点。同样的道理，先绘出树，然后按照左-右-根写出后序 ...
二叉树中,根节点的前序遍历是?
该题答案选择D选项。后序遍历表明A一定是根节点，那么由中序遍历得CB、DE分别为左、右子树中序遍历，同时得到CB、ED分别为左、右子树后序遍历。同理，我们就可以得到如图所示得树。则它的前序遍历即为A选项。
怎样根据前序列和中序序列得出后序序列
例：已知某二叉树先序遍历序列是: A B C D E F H ,中序遍历序列是: B D C E A H F,写出后序遍历序列.由前序可知,该树根节点为A；由中序及根节点可知,B, D, C, E 在根节点的左子树上H, F在根节点的右子树上；再逐步分析各子树,可得该树为：A ╱ ╲ B F ╲ ╱ C H ╱...
二叉树前序中序后序
二叉树前序中序后序 前序遍历 前序遍历是三种遍历顺序中最简单的一种，因为根节点是最先访问的，而我们在访问一个树的时候最先遇到的就是根节点。递归法 递归的方法很容易实现，也很容易理解：我们先访问根节点，然后递归访问左子树，再递归访问右子树，即实现了根->左->右的访问顺序，因为使用的...
二叉树的先序、中序、后序是如何确定的?
二叉树的先序，中序，后序确定的方法如下：1、根据后序遍历的特点，我们知道后序遍历最后一个结点即为根结点，即根结点为G。2、观察中序遍历ADEFGHMZ。其中root节点G左侧的ADEF必然是r0ot的左子树，G右侧的HMZ必然是root的右子树。3、观察左子树ADEF，左子树的中的根节点必然是大树的root的left...
问一个关于二叉树遍历的问题
因为此二叉树（下图）1 2 3 4 5 6 图（1）的前序遍历是123456，而中序遍历是425163，后序遍历是452631 6为此二叉树的最后一个节点，前序是6；但中序不是6；后序总是1，不会变。而此二叉树（下图）1 2 3 4 5 6 7 图（2）的前序遍历是1234567，而中序遍历是425...
试用文字表达按照层次遍历二叉树的思想。
（3） 后序序列 后序遍历二叉树时，对结点的访问次序为后序序列 【例】后序遍历上图所示的二叉树时，得到的后序序列为：D B E F C A 注意：（1） 在搜索路线中，若访问结点均是第一次经过结点时进行的，则是前序遍历；若访问结点均是在第二次(或第三次)经过结点时进行的，则是中序...
数据结构关于遍历二叉树的一道题目急急急在线等啊
在中序遍历中，CBA是A的左子树，EDF是A的右子树。由于后序遍历的特点是先遍历左子树，再遍历右子树，最后访问根节点，所以后序遍历序列应该是CBAEDF。题目34要求根据后序遍历和中序遍历序列确定二叉树的前序遍历序列。后序遍历序列是dabec，中序遍历序列是debac。在后序遍历中，最后一个访问的节点是c...
麻货清之： 二叉树的三种金典遍历法1.前序遍历法: 前序遍历(DLR)前序遍历(DLR) 前序遍历首先访问根结点然后遍历左子树,最后遍历右子树.在遍历左、右子树时,仍然先访问根结点,然后遍历左子树,最后遍历右子树.若二叉树为空则结...
任城区18124315451： 二叉树遍历举例有哪些? - ？
麻货清之： 前序遍历:1 2 4 8 9 10 11 5 3 6 7 中序遍历:8 4 10 9 11 2 5 1 6 3 7 后序遍历:8 10 11 9 4 5 2 6 7 3 1 所谓遍历(Traversal)是指沿着某条搜索路线,依次对树中每个结点均做一次且仅做一次访问.访问结点所做的操作依赖于具体的应用问 题. 遍历是二叉树上最重要的运算之一,是二叉树上进行其它运算之基础.
任城区18124315451： 二叉树遍历结合例子具体讲解例子不能太简单 - ？
麻货清之： 遍历的方法有:层序遍历、先序遍历、中序遍历、后序遍历等,以下面的二叉树为例介绍遍历E/ \B F/ \ \A D H/ / \C G I\K/J 1.层序遍历即从上到下按层次访问该树,每一层单独输出一行,每一层要求访问的顺序为从左到右.例子中...
任城区18124315451： 二叉树遍历举例 - ？
麻货清之： 前序遍历:ABDECFG 中序遍历:DBEAFCG 后序遍历:DEBFGCA
任城区18124315451： 求二叉树的前序遍历的序列 - ？
麻货清之： 后序遍历最后一个元素为根!! 后序遍历最后元素为A,故A为根 在中序遍历序列中,A将:DGBAECHF 分为了 DGB(左子树) ECHF(右子树) 对照后序遍历,则左子树中序遍历为: DGB,后序遍历为:GDB 右子树中序遍历为:ECHF,后序遍历为:EHFC 采用同样的方法可以得到左子树的根为B,右子树的根为C 如此类推,画出整棵树, 先序遍历为: ABDGCEHF
任城区18124315451： 二叉树遍历问题(前序,中序,后序) - ？
麻货清之： 前序遍历(DLR) 前序遍历也叫做先根遍历,可记做根左右. 前序遍历首先访问根结点然后遍历左子树,最后遍历右子树.在遍历左、右子树时,仍然先访问根结点,然后遍历左子树,最后遍历右子树. 若二叉树为空则结束返回,否则: ...
任城区18124315451： 已知二叉树中序和后序遍历怎么求前序遍历遍历啊? - ？
麻货清之： 自己写个stack 我给你写的前后中写法吧. 前MyStack<TreeNode *> stack;while(true){while (lpCurNode){if (lpfun!=NULL){(this->*lpfun)(lpCurNode);stack.Push(lpCurNode);}lpCurNode=lpCurNode->m_lpLeft;}if (!stack.Pop(lpCurNode))...
任城区18124315451： 数据结构二叉树怎么遍历啊?? - ？
麻货清之： 拿先序遍历举例: 先序遍历 是根左右 先遍历根A,然后遍历A的左子树(是左面那一群),然后遍历A的右子树(为空). 在A的左子树中,先遍历根也就是B,在遍历B的左子树也就是C,在遍历B的右子树,是右边的一群. 在B的右子树中继续…………
任城区18124315451： 写出先序遍历的二叉树的遍历算法. - ？
麻货清之： 递归方式:#include<stdio.h> typedef struct node{ char data; struct node *lchild; struct node *rchild; }BitNode,*BitTree; void Createtree(BitTree *bt){ char ch; scanf(＂%c＂,&ch); if(ch=='.') *bt=NULL;//如果输入元素为'.',表示空; else {*bt=(BitNode ...
任城区18124315451： 二叉树的前、中、后三种遍历的解答方法? - ？
麻货清之： 二叉树的遍历: (1)前序遍历(DLR),首先访问根结点,然后遍历左子树,最后遍历右子树; (2)中序遍历(LDR),首先遍历左子树,然后访问根结点,最后遍历右子树; (3)后序遍历(LRD)首先遍历左子树,然后访问遍历右子树,最后访问根结点.
