二叉树

二叉树基本操作代码

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

相关文章

来自专栏GIS讲堂

Openlayers中热力图的实现

Heatmap 是用来呈现一定区域内的统计度量,最常见的网站访问热力图就是以特殊高亮的形式显示访客热衷的页面区域和访客所在的地理区域的图示。Heatmap.j...

56130
来自专栏小鹏的专栏

ubuntu下C++如何调用python程序,gdb调试C++代码

Linux下gdb调试C++代码:http://jingyan.baidu.com/article/acf728fd464984f8e410a369.html ...

35690
来自专栏闻道于事

js登录滑动验证,不滑动无法登陆

js的判断这里是根据滑块的位置进行判断,应该是用一个flag判断 <%@ page language="java" contentType="text/html...

1.3K80
来自专栏PPV课数据科学社区

【学习】七天搞定SAS(三):基本模块调用

搞定基本的函数之后,开始鼓捣SAS里面的模型。也就是说,要开始写PROC了。说实话,越学SAS,越觉得SAS像Stata...无论是从输出的样式,还是语法。好不...

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

java.base.jmod

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

18620
来自专栏杨建荣的学习笔记

通过java来格式化sql语句(r4笔记第61天)

经常在抓取一些sql语句的时候,得到的sql文本有格式的问题,如果尝试得到执行计划,每次都会费一番周折。 比如下面的sql语句,基本包含了常见的格式问题。第3行...

40640
来自专栏吴伟祥

星期、月份英文缩写 原

12110
来自专栏码匠的流水账

聊聊rocketmq的RequestTask

org/apache/rocketmq/remoting/netty/RequestTask.java

23320
来自专栏听雨堂

想修改CSS

      下载了一个“通用”的CSS文件,本来想偷懒的,结果发现有问题,就是它用的颜色是变量定义的,无法识别。我又找不到在哪里可以定义。 BODY{     ...

261100
来自专栏叁金大数据

EmguCV学习——简单算法 差分与高斯

公司项目需要检测运动物体,我对opencv也没啥研究,google了好久看了好多方法,最简单的就是差分与高斯背景建模了。

18630

扫码关注云+社区

领取腾讯云代金券