二叉树的链式存储结构及四种遍历算法

---

当二叉树不是完全二叉树时，使用顺序表来存储会造成很多的空间浪费，因此对于普通二叉树来说，使用链表存储更为合适。

普通二叉树示意图 二叉树链式存储结构示意图

采用链式存储二叉树时，其节点结构由 3 部分构成（如图 3 所示）：

• 指向左孩子节点的指针（Lchild）；
• 节点存储的数据（data）；

• 指向右孩子节点的指针（Rchild）；

  
  链式存储中树节点结构

二叉树的构建代码及四种遍历算法代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<queue>
#include<stack>
using namespace std;

typedef char Elemtype;

//表示树节点的结构体
typedef struct TNode{
    Elemtype data; //数据域
    struct TNode *lchild,*rchild; //左右孩子指针
}Tnode,*Tree;

//创建树
void CreateTree(Tree &T)
{
    queue<Tree> Q; //初始化一个空队列
    char buff[3]; //用来缓存输入的孩子节点数值
    printf("请输入根节点(以#表示空)：");
    scanf("%c",&buff[0]); //输入根节点
    getchar();
    if(buff[0]!='#'){ //根节点不为空
        T=(Tree)malloc(sizeof(Tnode)); //为根节点开辟内存空间
        T->data=buff[0];
        //T->rchild=NULL;//根节点没有右孩子;
        Q.push(T); //根节点入队
        while(!Q.empty()){
            Tnode *tmp=(Tnode*)malloc(sizeof(Tnode)); //为孩子节点开辟内存空间
            tmp=Q.front();
            Q.pop();
            printf("请依次输入节点%c的左右孩子：",tmp->data);
            scanf("%s",buff);
            if(buff[0]!='#'){
                Tnode *lc=(Tnode*)malloc(sizeof(Tnode));
                lc->data=buff[0];
                tmp->lchild=lc;
                Q.push(lc);
            }
            else{
                tmp->lchild=NULL;
            }
            if(buff[1]!='#'){
                Tnode *rc=(Tnode*)malloc(sizeof(Tnode));
                rc->data=buff[1];
                tmp->rchild=rc;
                Q.push(rc);
            }
            else{
                tmp->rchild=NULL;
            }
        }
    }
    else{ //树为空
        T=NULL;
    }
}

//二叉树的层次遍历
/*二叉树层次遍历的思想是：
通过使用队列的数据结构，从树的根结点开始，依次将其左孩子
和右孩子入队。而后每次队列中一个结点出队，都将其左孩子和
右孩子入队，直到树中所有结点都出队，出队结点的先后顺序就
是层次遍历的最终结果。
*/
void LevelTraverse(Tree T)
{
    queue<Tree> Q;
    if(T){
        Q.push(T);
        while(!Q.empty()){
            Tnode *tmp=(Tnode*)malloc(sizeof(Tnode));
            tmp=Q.front();
            Q.pop();
            printf("%c ",tmp->data);
            if(tmp->lchild){
                Q.push(tmp->lchild);
            }
            if(tmp->rchild){
                Q.push(tmp->rchild);
            }
        }
        printf("\n");
    }
    else{
        printf("树为空\n");
    }
}

//二叉树的先序遍历，非递归实现
/*二叉树先序遍历的实现思想是：
1.访问根节点；
2.访问当前节点的左子树；
3.若当前节点无左子树，则访问当前节点的右子树；
*/
void preorderTraverse(Tree T)
{
    if(T){
        stack<Tree> S;
        S.push(T);
        while(!S.empty()){
            Tnode *tmp=(Tnode*)malloc(sizeof(Tnode));
            tmp=S.top();
            S.pop();
            printf("%c ",tmp->data);
            while(tmp){
                if(tmp->rchild){
                    S.push(tmp->rchild);
                }
                if(tmp->lchild){
                    printf("%c ",tmp->lchild->data);
                }
                tmp=tmp->lchild;
            }
        }
        printf("\n");
    }
    else{
        printf("树为空\n");
    }
}

//二叉树的中序遍历，非递归实现
/*二叉树中序遍历的实现思想是：
1.访问当前节点的左子树；
2.访问根节点；
3.访问当前节点的右子树
*/
void inorderTraverse(Tree T)
{
    if(T){
        stack<Tree> S;
        Tnode *tmp=T;
        while(tmp || !S.empty()){
            if(tmp){
                S.push(tmp);
                tmp=tmp->lchild;
            }
            else{
                tmp=S.top();
                S.pop();
                printf("%c ",tmp->data);
                tmp=tmp->rchild;
            }
        }
        printf("\n");
    }
    else{
        printf("树为空\n");
    }
}

//二叉树的后序遍历，递归实现
/*二叉树后序遍历的实现思想是：
从根节点出发，依次遍历各节点的左右子树，直到
当前节点左右子树遍历完成后，才访问该节点元素。
*/
void postorderTraverse(Tree T)
{
    if(T){
        postorderTraverse(T->lchild);
        postorderTraverse(T->rchild);
        printf("%c ",T->data);
    }
}

int main(int argc,char **argv)
{
    Tree T;
    CreateTree(T);
    printf("树的层次遍历结果为：");
    LevelTraverse(T);
    printf("树的先序遍历结果为：");
    preorderTraverse(T);
    printf("树的中序遍历结果为：");
    inorderTraverse(T);
    printf("树的后序遍历结果为：");
    postorderTraverse(T);

    return 0;
}

运行结果：

运行结果

---

参考链接：http://c.biancheng.net/view/3386.html