二叉树

二叉树基本操作代码

#include "stdafx.h"
#include "stdlib.h"
#include "string.h"

#define MAX 100
typedef char Elemtype;

typedef struct BTNODE
{
    Elemtype data;
    BTNODE *left;
    BTNODE *right;
} BTNode;

void CreateBTNode(BTNode *&root, char *str)
{
    BTNode *p = NULL;
    BTNode *st[MAX] = {NULL};
    int top = -1;
    int i = 0;
    int k = 0;
    char ch = str[i];

    while ('\0' != ch)
    {
        switch (ch)
        {
        case '(':
            {
                top++;
                st[top] = p;
                k = 1;
                break;
            }
        case ')':
            {
                top--;
                break;
            }
        case ',':
            {
                k = 2;
                break;
            }
        default:
            {
                p = (BTNode*)malloc(sizeof(BTNode));
                if (NULL == p)
                {
                    return;
                }
                p->data = ch;
                p->left = p->right = NULL;

                if (!root)
                {
                    root = p;
                } 
                else
                {
                    switch (k)
                    {
                    case 1:
                        st[top]->left = p;
                        break;
                    case 2:
                        st[top]->right = p;
                        break;
                    }
                }
                break;
            }
        }
        ch = str[++i];
    }
}

void DispBTNode(BTNode *&root)
{
    if (root)
    {
        printf("%c", root->data);
        if (root->left || root->right)
        {
            printf("(");
            DispBTNode(root->left);
            if (root->right)
            {
                printf(",");
                DispBTNode(root->right);
            }
            printf(")");
        }
    }
}

int GetBTNodeDepth(BTNode *&root)
{
    int iLeftDepth  = 0;
    int iRightDepth = 0;

    if (!root)
    {
        return 0;
    }

    iLeftDepth  = GetBTNodeDepth(root->left);
    iRightDepth = GetBTNodeDepth(root->right);
    return (iLeftDepth > iRightDepth ? (iLeftDepth+1):(iRightDepth+1));
}

void PreOrder(BTNode *&root)
{
    if (root)
    {
        printf("%c\t", root->data);
        PreOrder(root->left);
        PreOrder(root->right);
    }
}

void PreOrder1(BTNode *&root)
{
    int top = -1;
    BTNode *p = NULL;
    BTNode *st[MAX] = {NULL};

    if (root)
    {
        top++;
        st[top] = root;

        while (top > -1)
        {
            p = st[top];
            top--;
            printf("%c\t", p->data);
            if (p->right)
            {
                top++;
                st[top] = p->right;
            }
            if (p->left)
            {
                top++;
                st[top] = p->left;
            }
        }
    }
}

void InOrder(BTNode *&root)
{
    if (root)
    {        
        PreOrder(root->left);
        printf("%c\t", root->data);
        PreOrder(root->right);
    }
}

void PostOrder(BTNode *&root)
{
    if (root)
    {        
        PreOrder(root->left);        
        PreOrder(root->right);
        printf("%c\t", root->data);
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
    BTNode *root = NULL;
    char *str = "A(B(D(,G)),C(E,F))";
    CreateBTNode(root, str);
    DispBTNode(root);
    printf("\r\n");
    printf("The BTree's Depth = %d\r\n", GetBTNodeDepth(root));

    printf("PreOrder:\r\n");
    PreOrder(root);
    printf("\r\n");

    printf("InOrder:\r\n");
    InOrder(root);
    printf("\r\n");

    printf("PostOrder:\r\n");
    PostOrder(root);
    printf("\r\n");
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ml

HDUOJ-------2719The Seven Percent Solution

The Seven Percent Solution Time Limit: 2000/1000 MS (Java/Others)    Memory Limi...

2855
来自专栏前端知识分享

第15天:穷举算法(水仙花数、阶乘求和)

773
来自专栏帘卷西风的专栏

编写简易斜45度地图编辑器

      最近在研究cocos2dx的地图,最开始使用的是Tiled,这个编辑器做比较小的地图还是比较强大的,不过做大地图的时候,有一些功能不太方便并且有缺陷...

923
来自专栏小樱的经验随笔

HDU 2438 Turn the corner(三分查找)

托一个学弟的福,学了一下他的最简便三分写法,然后找了一道三分的题验证了下,AC了一题,写法确实方便,还是我太弱了,漫漫AC路!各路大神,以后你们有啥好的简便写法...

2725
来自专栏xingoo, 一个梦想做发明家的程序员

数字时钟

/*----------------------------------------- DIGCLOCK.c -- Digital Clock ...

1775
来自专栏深度学习与数据挖掘实战

Graph application with Python, Neo4j, Gephi & Linkurious.js

I love Python, and to celebrate Packt Python week, I’ve spent some time developi...

402
来自专栏乐沙弥的世界

oracle imp导入时出现skipping table

    最近有同事在使用传统的imp工具导入数据时,总是提示收到skipping table的提示,也就是表被跳过,而不是被重建。即使是将目标数据库上的表对象删...

821
来自专栏CSDN技术头条

大数据与Hadoop最有影响力150人(英)

There are more than 284 million activeusers on twitter. This makes following t...

2747
来自专栏数据结构与算法

POJ3622 Gourmet Grazers(FHQ Treap)

Description Like so many others, the cows have developed very haughty tastes an...

3085
来自专栏陈满iOS

剑指offer读书笔记:每天一个编程题·iOS开发算法提升计划(1)

1013

扫码关注云+社区