概念

二叉树，是每个节点最多只有两个分之的树结构，通常分之被称作“左子树”或者“右子树”；二叉树的分之具有左右次序，且不能随意颠倒。

• 满二叉树：一棵深度为k，且有2^k-1 个结点的二叉树；
• 完全二叉树：在一棵二叉树中，除最后一层外，若其余层都是满的，并且或者最后一层是满的，或者是在右边缺少连续若干结点；
• 左斜树：所有节点都只有左子树
• 右斜树：所有节点都只有右子树

二叉树的性质

1. 在二叉树的第i层上最多有2^(i-1)个结点；
2. 深度为k的二叉树最多有2k-1个节点(k>=1)；
3. 对于任何一颗二叉树T，如果其终端节点树为n0，度为2的节点书数为n2，则n0 = n2 + 1；
4. 具有n个节点的完全二叉树深度为(log2(n)) + 1；
5. 对具有n个节点的完全二叉树，如果按照从上到下和从左到右的顺序对二叉树的所有节点从1开始编号，则对于任意的序号为i的结点有：

• 如果i > 1，那么序号为i的节点的双亲结点为i/2;
• 如果i = 1，那么序号为i的结点为根结点，无双亲节点；
• 如果2i <=n，那么序号为i的结点的左孩子结点序号为2i；
• 如果2i > n；那么序号为i的结点无左孩子；
• 如果2i + i <= n；那么序号为i的结点右孩子序号为2i + 1；
• 如果2i + i > n；那么序号为i的结点无左孩子。

二叉树的存储结构

顺序存储结构

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXSIZE 100 /* 存储空间初始分配量 */
#define MAX_TREE_SIZE 100 /* 二叉树的最大结点数 */

typedef int Status;
typedef int CElemType;
typedef CElemType SqBiTree[MAX_TREE_SIZE];
CElemType Nil = 0;

typedef struct {
    int level;
    int order;
} Position;

#pragma mrak - 二叉树的基本操作

Status InitBiTree(SqBiTree T) {
    for (int i = 0; i < MAX_TREE_SIZE; i++) {
        T[i] = Nil;
    }
    return OK;
}

Status CreateBiTree(SqBiTree T) {
    int i = 0;
    while (i < 10) {
        T[i] = i + 1;
        if (i != 0 && T[(i + 1) / 2 - 1] == Nil && T[i] != Nil) {
            return ERROR;
        }
        i++;
    }
    
    while (i < MAX_TREE_SIZE) {
        T[i++] = Nil;
    }
    
    return OK;
}

#define ClearBiTree InitBiTree

Status BiTreeEmpty(SqBiTree T) {
    return T[0] == Nil;
}

int BiTreeDepth(SqBiTree T) {
    int i;
    int j = -1;
    
    for (i = MAX_TREE_SIZE - 1; i >= 0; i--) {
        if (T[i] != Nil) {
            break;
        }
    }
    
    do {
        j++;
    } while (pow(2, j) < i);
    
    return j;
}

CElemType Value(SqBiTree T, Position e) {
    return T[(int)pow(2, e.level - 1) + e.order - 2];
}

Status Root(SqBiTree T,CElemType *e) {
    if (BiTreeEmpty(T)) {
        return ERROR;
    }
    *e = T[0];
    return OK;
}

Status Assign(SqBiTree T, Position e, CElemType value) {
    int i = (int)pow(2, e.level -1 ) + e.order - 2;
    
    //叶子结点的双亲为空
    if (value != Nil && T[(i + 1) / 2 -1] == Nil) {
        return ERROR;
    }
    
    //给双亲赋空值但是有叶子结点
    if (value == Nil && (T[i * 2 + 1] != Nil || T[i * 2 + 2] != Nil)) {
        return ERROR;
    }
    
    T[i] = value;
    return OK;
}

CElemType Parent(SqBiTree T, CElemType e) {
    if (T[0] == Nil) {
        return ERROR;
    }
    
    for (int i = 1; i < MAX_TREE_SIZE; i++) {
        if (T[i] == e) {
            return T[(i + 1) / 2 -1];
        }
    }
    
    return Nil;
}

CElemType LeftChild(SqBiTree T, CElemType e) {
    if (T[0] == Nil) {
        return ERROR;
    }
    
    for (int i = 0; i < MAX_TREE_SIZE - 1; i++) {
        if (T[i] == e) {
            return T[i * 2 + 1];
        }
    }
    
    return Nil;
}

CElemType RightChild(SqBiTree T, CElemType e) {
    if (T[0] == Nil) {
        return ERROR;
    }
    
    for (int i = 0; i < MAX_TREE_SIZE - 1; i++) {
        if (T[i] == e) {
            return T[i * 2 + 2];
        }
    }
    
    return Nil;
}

CElemType LeftSibling(SqBiTree T,CElemType e) {
    if (T[0] == Nil) {
        return ERROR;
    }
    
    for (int i = 1; i < MAX_TREE_SIZE - 1; i++) {
        if (T[i] == e && i % 2 == 0) {
            return T[i - 1];
        }
    }
    
    return Nil;
}

CElemType RightSibling(SqBiTree T,CElemType e) {
    if (T[0] == Nil) {
        return ERROR;
    }
    
    for (int i = 1; i < MAX_TREE_SIZE - 1; i++) {
        if (T[i] == e && i % 2 == 1) {
            return T[i + 1];
        }
    }
    
    return Nil;
}

Status visit(CElemType c){
    printf("%d ",c);
    return OK;
}

void LevelOrderTraverse(SqBiTree T) {
    int i = MAX_TREE_SIZE - 1;
    while (T[i] != Nil) {
        i--;
    }
    
    for (int j = 0; j <= i; j++) {
        if (T[j] != Nil) {
            visit(T[j]);
        }
    }
    printf("\n");
}

void PreTraverse(SqBiTree T, int e) {
    visit(T[e]);
    if (T[2 * e + 1] != Nil) {
        PreTraverse(T, 2 * e + 1);
    }
    
    if (T[2 * e + 2] != Nil) {
        PreTraverse(T, 2 * e + 2);
    }
}

Status PreOrderTraverse(SqBiTree T) {
    if (!BiTreeEmpty(T)) {
        PreTraverse(T, 0);
    }
    printf("\n");
    return OK;
}

void InTraverse(SqBiTree T, int e) {
    if (T[2 * e + 1] != Nil) {
        InTraverse(T, 2 * e + 1);
    }
    
    visit(T[e]);
    
    if (T[2 * e + 2] != Nil) {
        InTraverse(T, 2 * e + 2);
    }
}

Status InOrderTraverse(SqBiTree T) {
    if (!BiTreeEmpty(T)) {
        InTraverse(T, 0);
    }
    printf("\n");
    return OK;
}

void PostTraverse(SqBiTree T,int e) {
    if (T[2 * e + 1] != Nil) {
        PostTraverse(T, 2 * e + 1);
    }
    
    if (T[2 * e + 2] != Nil) {
        PostTraverse(T, 2 * e + 2);
    }
    
    visit(T[e]);
}

Status PostOrderTraverse(SqBiTree T) {
    if(!BiTreeEmpty(T)) {
        PostTraverse(T, 0);
    }
    printf("\n");
    return OK;
}

链式存储结构

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAX_TREE_SIZE 100 /* 二叉树的最大结点数 */

typedef int Status;
typedef char CElemType;
typedef CElemType SqBiTree[MAX_TREE_SIZE];
CElemType Nil = ' ';

#pragma mark--二叉树构造

int indexs = 1;
typedef char String[24];
String str;
Status StrAssign(String T,char *chars) {
    int i;
    if(strlen(chars) > 100) {
        return ERROR;
    }
    T[0] = strlen(chars);
    for(i = 1; i <= T[0]; i++)
        T[i] =* (chars + i - 1);
    return OK;
}

#pragma mark - BiTree

typedef struct BiTNode {
    CElemType data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

Status visit(CElemType e) {
    printf("%c ", e);
    return OK;
}

Status InitBiTree(BiTree *T) {
    *T = NULL;
    return OK;
}

void DestroyBiTree(BiTree *T) {
    if (*T) {
        if ((*T)->lchild) {
            DestroyBiTree(&(*T)->lchild);
        }
        if ((*T)->rchild) {
            DestroyBiTree(&(*T)->rchild);
        }
        free(T);
        *T = NULL;
    }
}

#define ClearBiTree DestroyBiTree

void CreateBiTree(BiTree *T) {
    CElemType e = str[indexs++];
    if (e == '#') {
        *T = NULL;
    } else {
        *T = (BiTree)malloc(sizeof(BiTNode));
        if (T == NULL) {
            return;
        }
        
        (*T)->data = e;
        CreateBiTree(&(*T)->lchild);
        CreateBiTree(&(*T)->rchild);
    }
}

Status BiTreeEmpty(BiTree T) {
    return T == NULL;
}

int BiTreeDepth(BiTree T) {
    if (T == NULL) {
        return 0;
    }
    
    int i, j;
    if (T->lchild) {
        i = BiTreeDepth(T->lchild);
    } else {
        i = 0;
    }
    
    if (T->rchild) {
        j = BiTreeDepth(T->rchild);
    } else {
        j = 0;
    }
    
    return i > j ? i + 1 : j + 1;
}

CElemType Root(BiTree T) {
    if (BiTreeEmpty(T)) {
        return Nil;
    }
    return T->data;
}

CElemType Value(BiTree p) {
    return p->data;
}

void Assign(BiTree p, CElemType value) {
    p->data=value;
}

void PreOrderTraverse(BiTree T) {
    if (T == NULL) {
        return;
    }
    printf("%c", T->data);
    PreOrderTraverse(T->lchild);
    PreOrderTraverse(T->rchild);
}

void InOrderTraverse(BiTree T) {
    if (T == NULL) {
        return;
    }
    InOrderTraverse(T->lchild);
    printf("%c", T->data);
    InOrderTraverse(T->rchild);
}

void PostOrderTraverse(BiTree T) {
    if (T == NULL) {
        return;
    }
    PostOrderTraverse(T->lchild);
    PostOrderTraverse(T->rchild);
    printf("%c", T->data);
}