二叉树

二叉树基本操作代码

#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 条评论
登录 后参与评论

相关文章

来自专栏Hadoop数据仓库

Oracle sqlldr 如何导入一个日期列

1. LOAD DATA INFILE * INTO TABLE test FIELDS TERMINATED BY X'9' TRAILING NULLCO...

1876
来自专栏Ryan Miao

ehcache报错

jfinal2.0+tomcat7+ehcache2.6.11+Linux Linux version 2.6.18-164.el5 (mockbuild@x8...

3749
来自专栏一个会写诗的程序员的博客

java.base.jmod

/Library/Java/JavaVirtualMachines/jdk-9.jdk/Contents/Home/jmods$ jmod list java....

1182
来自专栏我和未来有约会

简练的视图模型 ViewModel

patterns & practices Developer Center 发布了 Unity Application Block 1.2 for Silver...

2349
来自专栏黑泽君的专栏

【未解决问题】

762
来自专栏前端儿

Web 前端颜色值--字体--使用,整理整理

颜色值 CSS 颜色使用组合了红绿蓝颜色值 (RGB) 的十六进制 (hex) 表示法进行定义。对光源进行设置的最低值可以是 0(十六进制 00)。最高值是 2...

2762
来自专栏Java学习123

HTTP Status 500 - {msg=SolrCore 'collection1' is not available due to init failure: Could not load c

45011
来自专栏码匠的流水账

聊聊HystrixThreadPool

hystrix-core-1.5.12-sources.jar!/com/netflix/hystrix/HystrixThreadPool.java

931
来自专栏linux驱动个人学习

高通Audio中ASOC的machine驱动

ASoC被分为Machine、Platform和Codec三大部分,其中的Machine驱动负责Platform和Codec之间的耦合以及部分和设备或板子特定的...

1K4
来自专栏码匠的流水账

聊聊HystrixConcurrencyStrategy

hystrix-core-1.5.12-sources.jar!/com/netflix/hystrix/strategy/concurrency/Hystri...

611

扫码关注云+社区