摘要
- 定義和資料結構
- 初始化和賦值
- 遍歷方式
一、定義和資料結構
1. 定義
??二叉樹（Binary Tree）是一種樹形結構，它的特點是每個結點至多有兩棵子樹（即二叉樹中不存在度大于2的結點），并且，二叉樹的子樹有左右之分，其次序不能隨意顛倒，
2. 資料結構
typedef struct BiTNode
{
ElemType data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
??該結點是二叉樹中最基本的元素，包括資料域和指標域，
二、初始化和賦值
1. 初始化
BiTree myBiTree; // 定義一個指向二叉樹根結點的指標
InitTree(&myBiTree); // 初始化二叉樹
??我們使用一個指向二叉樹根結點的指標表示一顆二叉樹，
??需要注意的是，二叉樹的初始化InitTree改變的是根結點指標本身的內容，而不是指標指向的內容，所以在傳遞引數時，使用指標傳遞，傳遞根結點指標的指標，即根結點指標的地址，
Status InitTree(BiTree *T)
{
// *T 即為指向二叉樹根結點的指標.
if (*T == NULL) // 若已經指向空, 操作失敗, 報錯.
{
return ERROR;
}
*T = NULL; // 使得指標指向 NULL.
return OK;
} // InitTree
2. 賦值
??按照先序次序為二叉樹結點賦值，
// ! *T是二叉樹指標的指標, **T才是二叉樹本體.
void CreateTree(BiTree *T, FILE *fp)
{
char ch = 0;
ch = fgetc(fp); // 從輸入檔案中讀取一個字符.
if (ch == '^') // 使用'^'表示空結點.
{
*T = NULL;
}
else
{
// 為根結點指標分配要指向要記憶體空間.
*T = (BiTNode *)malloc(sizeof(BiTNode));
if (!*T)
{
exit(OVERFLOW);
}
(*T)->data = https://www.cnblogs.com/tianshihao/p/ch;
CreateTree(&((*T)->lchild), fp); // 遞回創建左右子樹.
CreateTree(&((*T)->rchild), fp); // 依舊傳遞指標的指標.
}
} // CreateTree
??在定義CreateTree時也可以不使用兩層套娃, 但之所以仍像InitTree一樣是因為:
????1. 保持一致性，凡是涉及到修改二叉樹的操作，都傳遞指標的指標，
????2. 若以后修改二叉樹的操作涉及對二叉樹指標本身的修改，這么做可以減少麻煩，實際上CreateTree中的*T = NULL理解起來比&T = NULL方便.
三、遍歷方式
??遍歷不修改二叉樹，直接傳遞指標，
1. 前序
Status PreOrderTraverse(BiTree T, Status (*Visit)(ElemType e))
{
if (T)
{
if (Visit(T->data))
{
if (PreOrderTraverse(T->lchild, Visit))
{
if (PreOrderTraverse(T->rchild, Visit))
{
return OK;
}
}
}
return ERROR;
}
else
{
return OK;
}
} // PreOrderTraverse
2. 中序
Status InOrderTraverse(BiTree T, Status (*Visit)(ElemType e))
{
if (T)
{
if (InOrderTraverse(T->lchild, Visit))
{
if (Visit(T->data))
{
if (InOrderTraverse(T->rchild, Visit))
{
return OK;
}
}
}
return ERROR;
}
else
{
return OK;
}
} // InOrderTraverse
3. 后序
Status PostOrderTraverse(BiTree T, Status (*Visit)(ElemType e))
{
if (T)
{
if (PostOrderTraverse(T->lchild, Visit))
{
if (PostOrderTraverse(T->rchild, Visit))
{
if (Visit(T->data))
{
return OK;
}
}
}
return ERROR;
}
else
{
return OK;
}
} // PostOrderTraverse
參考文獻
- 資料結構:C語言版/嚴蔚敏,吳偉民編著. ——北京：清華大學出版社，2007
代碼倉庫
- https://github.com/tianshihao/data-structure/tree/master/chapter_6
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/67603.html
標籤：其他