二叉树的前序、中序、后序遍历-蒲公英云

二叉树的前序、中序、后序遍历

小鱼儿 2022-06-11 02:36 327阅读 0赞

二叉树的结构体

typedef struct binaryTree {
```
char item;
struct binaryTree *lChild;
struct binaryTree *rChild;
```
}binaryTree, *pBinaryTree;

二叉树的初始化创建，二叉树创建的过程中按照先序遍历的方式输入一颗满二叉树，缺失的节点元素使用#补足；构建的过程中先递归创建左子树，然后递归创建右子数；’#’作为递归的结束；

pBinaryTree createBinaryTree() {

char tmp = '0';
pBinaryTree treeNode = NULL;
scanf("%c", &tmp);
if (tmp == '#')
{
    treeNode = NULL;
}
else
{
    //为加入的节点分配新的内存空间
    treeNode = (binaryTree*)malloc(sizeof(binaryTree));
    treeNode->item = tmp;
    //递归调用产生二叉树
    treeNode->lChild = createBinaryTree();
    treeNode->rChild = createBinaryTree();
}
return treeNode;

}

先序遍历二叉树

void preVisitBiTree(pBinaryTree root) {

if (root)
{
    //先遍历根节点
    printf("%c", root->item);
    //遍历左子树
    preVisitBiTree(root->lChild);
    //遍历右子树
    preVisitBiTree(root->rChild);
}

}

中序遍历二叉树

void inVisitBiTree(pBinaryTree inRoot) {

if (inRoot)
{
    //先遍历左子树
    inVisitBiTree(inRoot -> lChild );
    //遍历根节点
    printf("%c", inRoot->item);
    //遍历右子树
    inVisitBiTree(inRoot->rChild);
}

}

后序遍历二叉树

void lastVisitBiTree(pBinaryTree lastRoot) {

if (lastRoot)
{
    //遍历左子树
    inVisitBiTree(lastRoot->lChild);
    //遍历右子树
    inVisitBiTree(lastRoot->rChild);
    //遍历根节点
    printf("%c", lastRoot->item);
}

}

三种遍历二叉树的递归结构是相似的，只是递归遍历的先后有区别

测试：

int main() {
    //构建一颗二叉树
    pBinaryTree binaryTree = createBinaryTree();
    //采用先序遍历的方式遍历输出二叉树
    preVisitBiTree(binaryTree);
    printf("\n");
    //采用中序遍历的方式输出二叉树
    inVisitBiTree(binaryTree);
    printf("\n");
    lastVisitBiTree(binaryTree);
    printf("测试二叉树");
    return 0;
}