二叉搜索树遍历

Question

我刚刚开始学习二叉树并继续尝试在 C 中实现我自己的二叉树。我有点迷惑为什么只有 InOrder Traversal 显示正确而其他两个显示错误。我真的想不通。我什至直接尝试插入节点，结果也是一样。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

struct Node
{
    int val;
    struct Node *left;
    struct Node *right;
};

//Allocate Memory for New Node
struct Node* getNewNode(int val)
{
    struct Node * ptr = (struct Node*)malloc(sizeof(struct Node));
    ptr->val = val;
    ptr->left = NULL;
    ptr->right = NULL;
    return ptr;
}
//Insert Node in Binary Search Tree
struct Node* insertNode(struct Node* root,int val)
{
    if(root == NULL)
    {
        root = getNewNode(val);
    }
    else if(val <= root->val)
    {
        root->left = insertNode(root->left,val);
    }
    else
    {
        root->right = insertNode(root->right,val);
    }
    return root;

}
void printInorder(struct Node* root)
{
    if(root == NULL) return;
    printInorder(root->left);
    printf("%d ",root->val);
    printInorder(root->right);
}
void printPostOrder(struct Node* root)
{
    if(root == NULL) return;
    printInorder(root->left);
    printInorder(root->right);
    printf("%d ",root->val);
}
void printPreOrder(struct Node*root)
{
    if(root == NULL) return;
    printf("%d ",root->val);
    printInorder(root->left);
    printInorder(root->right);
}
bool search(struct Node* root,int val)
{
    if(root == NULL)
    {
        return false;
    }
    else if(val == root->val)
    {
        return true;
    }
    else if(val < root->val)
    {
        return search(root->left,val);
    }
    else
    {
        return search(root->right,val);
    }
}
int main(void)
{
    struct Node * root = NULL; //Tree is Empty
    root = insertNode(root,15);
    root = insertNode(root,10);
    root = insertNode(root,8);
    root = insertNode(root,12);
    root = insertNode(root,20);
    root = insertNode(root,17);
    root = insertNode(root,25);
    printf("Printing In-Order: \n");
    printInorder(root);
    printf("\nPrinting Post-Order: \n");
    printPostOrder(root);
    printf("\nPrinting Pre-Order: \n");
    printPreOrder(root);

    // if(search(root,11))
    // {
    //  printf("\nValue Found\n");
    // }
    // else
    // {
    //  printf("\nValue Not Found\n");
    // }

    return 0;
}

如果我做错了或者我对遍历的理解有误，请帮助我理解。输出如下： output terminal

Answer 1

您在 printPostOrder 和 printPreOrder 中存在复制粘贴错误 - 他们都在应该调用自己的地方调用了 printInorder。

二叉搜索树遍历

Binary Search Tree Traversals

binary-tree

traversal

inorder

preorder

postorder