二叉树

二叉树基本操作代码

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

相关文章

来自专栏琯琯博客

PHP二叉树(三):红黑树

2214
来自专栏撸码那些事

【图解数据结构】 二叉树遍历

1444
来自专栏猿人谷

根据前序和中序推出后序

最近面试总遇到这种根据给出的两类序遍历,然后求按另一种形式序的遍历。看来有必要好好总结下这个知识点,省的每次笔试时都得花不少时间推导。 首先,我们看看前序、中序...

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

二叉树性质

•【性质1】在二叉树的第i层上最多有2i-1个结点(i>=1)。 【性质2】深度为k的二叉树至多有2k –1个结点(k>=1)。 •【特别】一棵深度为k且有2k...

2416
来自专栏Kubernetes

Kubernetes Scheduler原理解析

本文是对Kubernetes Scheduler的算法解读和原理解析,重点介绍了预选(Predicates)和优选(Priorities)步骤的原理,并介绍了默...

3965
来自专栏开发与安全

数据结构:二叉树的定义和性质以及特殊二叉树

一、二叉树(Binary Tree)是n(n>=0)个结点的有限集合,该集合或者为空集(称为空二叉树),或者由一个根结点和两棵互不相交的、分别称为根结点的左子树...

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

AVL树

平衡二叉树,是一个方便查找的树,树的左子树深度与右子树的深度的差总(BF)是在+1,0,-1之中。 随着树的建立,插入,树都会自动的进行调整,使得其满足上面的条...

1895
来自专栏java学习

面试题65(树,图)

面试例题1:前序遍历二叉树值为abcdefg,下面哪个不可能是中序遍历?A.abcdefg B.gfedcba C.bcdefga D.bceadfg 正确解析...

2704
来自专栏琯琯博客

PHP二叉树(一):平衡二叉树(AVL)

平衡二叉树 <?php /** * description: 平衡二叉树 */ //结点 class Node { public $key; ...

2769
来自专栏机器学习从入门到成神

数据结构之树、森林和二叉树的转换

树转换为二叉树 (1)加线。在所有兄弟结点之间加一条连线。 (2)去线。树中的每个结点,只保留它与第一个孩子结点的连线,删除它与其它孩子结点之间的连线。...

812

扫码关注云+社区