算法之二叉树各种遍历


		树形结构是一类重要的非线性数据结构，其中以树和二叉树最为常用。
 
二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2的 i -1次方个结点；深度为k的二叉树至多有2^(k) -1个结点；对任何一棵二叉树T，如果其终端结点数(即叶子结点数)为n0，度为2的结点数为n2，则n0 = n2 + 1。
 
二叉树的链式存储结构是一类重要的数据结构，其形式定义如下：
 
 
[cpp] 
//二叉树结点   
typedef struct BiTNode{  
    //数据   
    char data;  
    //左右孩子指针   
    struct BiTNode *lchild,*rchild;  
}BiTNode,*BiTree;  
 
//二叉树结点
typedef struct BiTNode{
//数据
char data;
//左右孩子指针
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
 
 
 
二叉树的创建： 
通过读入一个字符串，建立二叉树的算法如下：
 
 
 
[cpp]
//按先序序列创建二叉树   
int CreateBiTree(BiTree &T){  
    char data;  
    //按先序次序输入二叉树中结点的值（一个字符），‘#’表示空树   
    scanf("%c",&data);  
    if(data == '#'){  
        T = NULL;  
    }  
    else{  
        T = (BiTree)malloc(sizeof(BiTNode));  
        //生成根结点   
        T->data = data;  
        //构造左子树   
        CreateBiTree(T->lchild);  
        //构造右子树   
        CreateBiTree(T->rchild);  
    }  
    return 0;  
}  
 
//按先序序列创建二叉树
int CreateBiTree(BiTree &T){
char data;
//按先序次序输入二叉树中结点的值（一个字符），‘#’表示空树
scanf("%c",&data);
if(data == '#'){
T = NULL;
}
else{
T = (BiTree)malloc(sizeof(BiTNode));
//生成根结点
T->data = data;
//构造左子树
CreateBiTree(T->lchild);
//构造右子树
CreateBiTree(T->rchild);
}
return 0;
}
二叉树的遍历： 
 
遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。
 
 
递归算法：
 
 
[cpp
//输出   
void Visit(BiTree T){  
    if(T->data != '#'){  
        printf("%c ",T->data);  
    }  
}  
//先序遍历   
void PreOrder(BiTree T){  
    if(T != NULL){  
        //访问根节点   
        Visit(T);  
        //访问左子结点   
        PreOrder(T->lchild);  
        //访问右子结点   
        PreOrder(T->rchild);  
    }  
}  
//中序遍历   
void InOrder(BiTree T){  
    if(T != NULL){  
        //访问左子结点   
        InOrder(T->lchild);  
        //访问根节点   
        Visit(T);  
        //访问右子结点   
        InOrder(T->rchild);  
    }  
}  
//后序遍历   
void PostOrder(BiTree T){  
    if(T != NULL){  
        //访问左子结点   
        PostOrder(T->lchild);  
        //访问右子结点   
        PostOrder(T->rchild);  
        //访问根节点   
        Visit(T);  
    }  
}  
 
//输出
void Visit(BiTree T){
if(T->data != '#'){
printf("%c ",T->data);
}
}
//先序遍历
void PreOrder(BiTree T){
if(T != NULL){
//访问根节点
Visit(T);
//访问左子结点
PreOrder(T->lchild);
//访问右子结点
PreOrder(T->rchild);
}
}
//中序遍历
void InOrder(BiTree T){
if(T != NULL){
//访问左子结点
InOrder(T->lchild);
//访问根节点
Visit(T);
//访问右子结点
InOrder(T->rchild);
}
}
//后序遍历
void PostOrder(BiTree T){
if(T != NULL){
//访问左子结点
PostOrder(T->lchild);
//访问右子结点
PostOrder(T->rchild);
//访问根节点
Visit(T);
}
}
 
非递归算法：
 
<1>先序遍历：
 
【思路】：访问T->data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。
 
 
 
[cpp] 
/* 先序遍历(非递归) 
   思路：访问T->data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。 
*/  
void PreOrder2(BiTree T){  
    stack<BiTree> stack;  
    //p是遍历指针   
    BiTree p = T;  
    //栈不空或者p不空时循环   
    while(p || !stack.empty()){  
        if(p != NULL){  
            //存入栈中   
            stack.push(p);  
            //访问根节点   
            printf("%c ",p->data);  
            //遍历左子树   
            p = p->lchild;  
        }  
        else{  
<

补充：软件开发 , C++ ,