数据结构之二叉树_二叉树tdata

二叉树专题

#树的定义：
树是n个结点的有限集。n等于0是称为空树，在任意一棵非空树中，有且仅有 一个特定的称为根的结；当n>1时，其余节点可分为m（m>0）个互不相交的有限集，其中每个集合本身又是一棵树，并且称为根的子树。

#二叉树基本概念

满二叉树：一棵深度为k 且有2k -1个结点的二叉树。
（特点：每层都“充满”了结点）
完全二叉树：深度为k 的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k 的满二叉树中编号从1至n的结点一一对应。

#二叉树的存储结构
顺序存储结构：按二叉树的结点“自上而下，从左到右”编号，用一组连续的存储单元存储。如果是完全二叉树，能够恢复唯一对应的二叉树形状
链式存储结构：
typedef struct node{ //树的结点
int data;
struct node* left;
struct node* right;
} Node;

#二叉树的遍历
二叉树由根、左子树、右子树构成，定义为D、L、R,所以根据访问的根结点是先于子树出现还是后于子树出现，分为先、中、后三种遍历方式.

#import <Foundation/Foundation.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode{
    char ch;
    struct TreeNode *lchild, *rchild;
}Tree, *PTree;//定义树节点的结构体

void createBiTree(PTree *p)//建立二叉树
{
    char ch;
    scanf("%c", &ch);
    getchar();//此时%c读取的是单个字符，所以用那个getchar来接收一下
    if(ch == '#')
        *p = NULL;
    else
    {
        *p = (PTree)malloc(sizeof(Tree));
        (*p) -> ch = ch;
        printf("请输入%c的左子树\n", ch);
        createBiTree(&(*p) -> lchild);
        printf("请输入%c的右子树\n", ch);
        createBiTree(&(*p) -> rchild);
    }
}

void preOrderTraverse(PTree p)//前序遍历
{
    if(p == NULL)
        return ;
    printf("%c ", p -> ch);
    preOrderTraverse(p -> lchild);
    preOrderTraverse(p -> rchild);
}

void InOrderTraverse(PTree p)//中序遍历
{
    if(p == NULL)
        return;
    InOrderTraverse(p -> lchild);
    printf("%c ", p -> ch);
    InOrderTraverse(p -> rchild);
}

void BackOrderTraverse(PTree p)//后续遍历
{
    if(p == NULL)
        return ;
    BackOrderTraverse(p -> lchild);
    BackOrderTraverse(p -> rchild);
    printf("%c ", p -> ch);
}

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        PTree pt;
        createBiTree(&pt);
        preOrderTraverse(pt);
        printf("\n");
        InOrderTraverse(pt);
        printf("\n");
        BackOrderTraverse(pt);
        printf("\n");
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67