一户辱、 樹的定義
樹的定義
二鸵钝、樹的抽象數(shù)據(jù)類型
樹的抽象數(shù)據(jù)類型
三、樹的存儲(chǔ)結(jié)構(gòu)
雙親表示法
#define MAX_TREE_SIZE 100
typedef int TElemType;
typedef struct PTNode {
TElemType data; //結(jié)點(diǎn)數(shù)據(jù)
int parent; //雙親位置
}PTNode;
typedef struct {
PTNode nodes[MAX_TREE_SIZE]; //結(jié)點(diǎn)數(shù)組
int r, n; //跟的位置和結(jié)點(diǎn)數(shù)
} PTree;
孩子表示法
#define MAX_TREE_SIZE 100
typedef int TElemType;
typedef struct CTNode { //孩子結(jié)點(diǎn)
int child;
struct CTNode *next;
} *ChildPtr;
typedef struct { //表頭結(jié)構(gòu)
TElemType data;
ChildPtr firstchild;
} CTBox;
typedef struct { //樹結(jié)構(gòu)
CTBox nodes[MAX_TREE_SIZE]; //結(jié)點(diǎn)數(shù)組
int r, n; //跟位置庐镐，結(jié)點(diǎn)數(shù)
} CTree;
孩子兄弟表示法
typedef int TElemType;
typedef struct CSNode {
TElemType data;
struct CSNode *firstchild, *rightslb;
} CSNode, *CSTree;
四蒋伦、二叉樹的定義
- 斜樹
- 滿二叉樹
-
完全二叉樹
五、二叉樹的性質(zhì)
- 二叉樹第i層上至多有2i-1個(gè)結(jié)點(diǎn)
- 深度為k的二叉樹焚鹊，最少有2k-1個(gè)結(jié)點(diǎn)
- 對(duì)任意二叉樹痕届，終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2末患，則研叫，n0 = n2 + 1
六、二叉樹的存儲(chǔ)結(jié)構(gòu)
二叉鏈表
typedef struct BiTNode {
TElemType data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
七璧针、遍歷二叉樹
前序遍歷
void BiTree::PreOrderTraverse(biTree T)
{
if (T == NULL)
return;
cout << T->data << endl;
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}v
中序遍歷
void BiTree::PostOrderTraverse(biTree T)
{
if (T == NULL)
return;
PreOrderTraverse(T->lchild);
cout << T->data << endl;
PreOrderTraverse(T->rchild);
}
后序遍歷
void BiTree::PostOrderTraverse(biTree T)
{
if (T == NULL)
return;
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
cout << T->data << endl;
}
已知前序中序求后序
特性A嚷炉，對(duì)于前序遍歷，第一個(gè)肯定是根節(jié)點(diǎn)探橱；
特性B申屹，對(duì)于后序遍歷，最后一個(gè)肯定是根節(jié)點(diǎn)隧膏；
特性C哗讥，利用前序或后序遍歷，確定根節(jié)點(diǎn)胞枕，在中序遍歷中杆煞，根節(jié)點(diǎn)的兩邊就可以分出左子樹和右子樹；
特性D腐泻，對(duì)左子樹和右子樹分別做前面3點(diǎn)的分析和拆分决乎，相當(dāng)于做遞歸，我們就可以重建出完整的二叉樹派桩；
例：构诚；
七、二叉樹的建立
void BiTree::CreateBiTree(biTree * T)
{
TElemType ch;
cin >> ch;
if (ch == '#') {
T = NULL;
}
else {
*T = (biTree)malloc(sizeof(BiTNode));
if (!*T) {
exit(OVERFLOW);
}
(*T)->data = ch;
CreateBiTree(&(*T)->lchild);
CreateBiTree(&(*T)->rchild);
}
}
八铆惑、線索二叉樹
中序遍歷線索化
void BiThrTree::InThreading(biThrTree p)
{
if (p) {
InThreading(p->lchild);
if (!p->lchild) {
p->LTag = Thread;
p->lchild = pre;
}
if (!pre->rchild) {
pre->RTag = Thread;
pre->rchild = p;
}
pre = p;
InThreading(p->rchild);
}
}
九范嘱、 樹凳寺、二叉樹、森林的轉(zhuǎn)化
1. 樹->二叉樹
森林->二叉樹
二叉樹->樹
二叉樹->森林
十彤侍、哈夫曼樹
