二叉樹的存儲結構
順序存儲
#define MaxSize 100
struct TreeNode{ElemType value; //結點中的數據元素bool isEmpty; //結點元素是否為空
};//定義一個長度為MaxSize的數組t，按照從上至下、從左至右的順序依次完成存儲完全二叉樹中的各個節點
TreeNode t[MaxSize];
for (int i = 0;i<MaxSize;i++){t[i].isEmpty = true; //初始化所有結點為空
}
幾個重要常考的基本操作：
i 的左孩子 – 2i
i 的右孩子 – 2i+1
i 的父節點 – [i/2]
i 所在的層次 – [log2(n+1)]或[log2n]+1
【注意】如果是一顆普通的二叉樹，依然按照層序將各節點順序存儲，那么結點間是沒有上述的對應關系的
?所以在二叉樹的順序存儲中，一定需要將二叉樹的節點編號與完全二叉樹對應起來
【存在問題】在最壞情況下，高度為h的且只有h個節點的單只樹（所有結點只有右孩子），也至少需要2^h-1個存儲單元
鏈式存儲
//二叉樹的結點（鏈式存儲）
typedef struct BiTNode{ElemType data; //數據域struct BiTNode * lchild,*rchild; //左右孩子
}BiTNode,*BiTree;
?n個結點的二叉鏈表共有n+1個空鏈域（可以用于構造線索二叉樹）
struct ElemType{int value;
};typedef struct BiTNode{ElemType data; //數據域struct BiTNode *lchild,*rchild; //左右孩子指針
}BiTNode,*BiTree;//定義一顆空樹
BiTree root = NULL://插入根結點
root = (BiTree)malloc(sizeof(BiTNode));
root->data = {1};
root->lchild = NULL;
root->rchild = NULL;//插入新結點
BiTNode *p = (BiTNode*)malloc(sizeof(BiTNode));
p->data = {2};
p->lchild = NULL;
p->rchild = NULL;
root ->lchild = p; //作為根結點的左孩子
找到指定結點p的左右孩子 – p->lchild; p->rchild;
找到指定結點p的父節點 – 只能從根節點開始遍歷
【解決】如果經常需要尋找父節點，可以使用三叉鏈表（添加一個父結點指針）
//二叉樹的結點（鏈式存儲）
typedef struct BiTNode{ElemType data; //數據域struct BiTNode *lchild,*rchild; //左右孩子指針struct BiTNode *parent; //父結點指針（根據實際需要決定要不要添加）
}BiTNode,*BiTree;
