C/C++教程

C++ 二叉树的层次建树及其遍历

本文主要是介绍C++ 二叉树的层次建树及其遍历,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

总结归纳

  1. 先序遍历:根左右;中序遍历:左根右;后序遍历:左右根。
  2. 若选取层次建树,则需要一个链式队列辅助实现 (规定,不必问为什么) 。
  3. 该辅助队列的具体操作流程(重点理解): 队列结点的数据域 p 存放的是树结点的地址 ( BiTNode *p 类型 ) ,头指针 phead 指向该队列头部,尾指针 ptail 指向该队列尾部,队列指针 pCur 始终指向当前操作位置,当前操作位置指的是:有新结点加入二叉树时,新结点作为队列指针 pCur 所指向的树结点(队列结点的数据域)的子孩子。此时,若 pCur 所指向树结点的左孩子为空,将新结点置为该树结点的左孩子,并通过尾插法加入队列,更新队尾指针;若此时右孩子为空,将新结点置为该树结点的右孩子,更新队尾指针,因为此时 pCur 指针所指向的树结点左右孩子皆满,使得 pCur 指针右移,下次新结点入队时,pCur 指针指向的树结点的左孩子就又为空。
  4. 层次建树的难点在于,较为复杂且难以理解,最后再总结一下:定义树结点,定义链式队列结点,队列结点的数据域为树结点的地址(BiTNode *p 类型)。树结点入树时,首先将队列结点通过尾插法入队,并通过 pCur 指针指向的队列结点的数据域拿到对应树结点的地址,再对左右孩子进行判空,然后入树。
  5. 在该代码中,pCur 是每次建树时重新定义的,所以在建树最后,要释放并置为 NULL ,如果不这么做,可以将 pCur 置为全局变量。也可以将头尾指针定义在队列内部,可以使得建树函数 BuildBinaryTree() 少传些参数,总之方法很多,均能实现。

代码实践

#include <iostream>

#define MaxSize 10 // 栈中元素的最大个数

using namespace std;

typedef char ElemType;

// 树
struct BiTNode {
    ElemType data;            // 数据域
    BiTNode *lchild, *rchild; // 左孩子,右孩子
};

// 辅助队列结点,不带头结点,通过头指针 phead 访问
struct LinkNode {
    BiTNode *p; // 树中对应结点的地址
    LinkNode *pNext;
};

typedef BiTNode *BiTree;     // 代指二叉树
typedef LinkNode *LinkQueue; // 代指链式队列

// 树的初始化
bool InitTree(BiTree &T) {
    T = NULL;
    return true;
}

//层次建树
void BuildBinaryTree(BiTree &T, LinkNode *&phead, LinkNode *&ptail, ElemType val) {
    // 此处申请空间,不能使用new,会进入死循环,我也不知道为啥
    BiTNode *pTreeNew = (BiTNode *)calloc(1, sizeof(BiTNode)); // 为树结点申请空间
    LinkNode *pQueueNew = (LinkNode *)calloc(1, sizeof(LinkNode)); // 为队列结点申请空间
    LinkNode *pCur = phead; // 始终指向当前操作位置

    pTreeNew->data = val;    // 树结点的赋值
    pQueueNew->p = pTreeNew; // 队列新结点的数据域为树的新结点

    if (T == NULL) { // 空树时,新结点置为树根
        T = pTreeNew;
        phead = pQueueNew;
        ptail = pQueueNew;
    } else {
        ptail->pNext = pQueueNew; //尾插法
        ptail = pQueueNew;        // 更新尾指针

        if (pCur->p->lchild == NULL) { // 左孩子为空
            pCur->p->lchild = pTreeNew;
        } else if (pCur->p->rchild == NULL) { // 右孩子为空
            pCur->p->rchild = pTreeNew;
            phead = pCur->pNext; //该结点左右孩子已满,队头指针后移
            free(pCur); // 该代码中,PCur 是每次建树时重新定义的,所以在建树最后,要释放并置为 NULL 
            pCur = NULL;
        }
    }
}

//前序遍历(深度优先遍历):根左右
void PreOrder(BiTNode *p) {
    if (p != NULL) {
        putchar(p->data);
        PreOrder(p->lchild);
        PreOrder(p->rchild);
    }
}

// 中序遍历:左根右
void InOrder(BiTNode *p) {
    if (p != NULL) {
        InOrder(p->lchild);
        putchar(p->data);
        InOrder(p->rchild);
    }
}

// 后序遍历:左右根
void PostOrder(BiTNode *p) {
    if (p != NULL) {
        PostOrder(p->lchild);
        PostOrder(p->rchild);
        putchar(p->data);
    }
}

int main() {
    ElemType val;
    BiTree T;
    InitTree(T);

    LinkNode *phead = NULL;
    LinkNode *ptail = NULL; // 头指针,尾指针
    while (scanf("%c", &val) != EOF) {
        if (val == '\n') {
            break;
        } else {
            BuildBinaryTree(T, phead, ptail, val);
        }
    }

    cout << "-----前序遍历-----" << endl;
    PreOrder(T);
    cout << endl;

    cout << "-----中序遍历-----" << endl;
    InOrder(T);
    cout << endl;

    cout << "-----后序遍历-----" << endl;
    PostOrder(T);
    cout << endl;

    return 0;
}
这篇关于C++ 二叉树的层次建树及其遍历的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!