数据结构——树与二叉树

树的基本概念

树的定义

见王道书P119

树的性质?

• 结点数 = 总度数（分支数） + 1，这个 1 是根结点。

• 度为 m 的树	m 叉树
  任意结点的度 <= m	任意结点的度 <= m
  至少有一个结点度 = m	允许所有结点的度都 < m
  一定是非空树，至少有 m + 1 个结点	可以是空树

• $$\begin{array}{l}度为m的树、m叉树，第i层至多有m^{i?1}个结点\end{array}$$

• $$\begin{array}{l}高度为h的m叉树、m度树至多有\frac{(m^h?1)}{(m?1)}个结点（等比数列求和）\end{array}$$

• $$\begin{array}{l}高度为h的度为m的树至少有h+m?1个结点（等比数列求和）\end{array}$$

• KaTeX parse error: Undefined control sequence: \ at position 43: …点的\ m\ 叉树的最小高度为\? ?\left\lceil {{{…

二叉树

二叉树的定义和主要特性

注意以上都是向下取整

二叉树的性质?

KaTeX parse error: Unknown column alignment: * at position 789: …{\begin{array}{*?{20}{c}} {{n_0}…

二叉树的存储结构和基本操作

顺序存储

满二叉树和完全二叉树可以采用顺序存储：

同“串”一样，我们从下标 1 开始存储，方便对应。

#define MaxSize 255
ElemType data[MaxSize];

struct TreeNode{
    ElemType value;
    bool isEmpty;
};
TreeNode data[MaxSize];

// ElemType 可以是一个结构体哈！长见识了吧！
struct ElemType{
    int value;
}

typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild, *rchild;
    Struct BiTNode *parent;		// 考研中经常考没有这个指针的情形，有这个叫做“三叉链表”
}BiTNode, *BiTree;

struct ElemType{
    int value;
}

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

// 初始化:
BiTree root = NULL;

// 赋值：
root = (BiTNode *)malloc(sizeof(BiTNode));
root -> data.value = 1;
root -> lchild = NULL;
root -> rchild = NULL;

void PreOrder(BiTree T){
    if (T != NULL) {
        visit(T);
        PreOrder(T -> lchild);
        PreOrder(T -> rchild);
    }
}

void InOrder(BiTree T){
    if (T != NULL) {
        PreOrder(T -> lchild);
        visit(T);
        PreOrder(T -> rchild);
    }
}

void PostOrder(BiTree T){
    if (T != NULL) {
        PreOrder(T -> lchild);
        PreOrder(T -> rchild);
        visit(T);
    }
}

int treeDepth(BiTree T) {
    if (T == NULL)
        return 0;
    else {
        int l = treeDepth(T -> lchild);
        int r = treeDepth(T -> rchild);
        // 树的深度 = Max(左子树深度，右子树深度) + 1
        return l > r ? l + 1 : r + 1;
    }
}