数据结构——树

浙大数据结构慕课的一些笔记

二分查找判定树

二分判定树的一些性质

树的一些基本术语

术语一

术语二

二叉树的重要性质

二叉树的性质

构造二叉树

数据结构

1
2
3
4
5
6
7
8
typedef int ElementType;
typedef struct TNode * Position;
typedef Position BinTree;
struct TNode {
ElementType Data;
BinTree Left;
BinTree Right;
};

先、中、后序遍历

递归法

这里只列出递归中序遍历,后序和先序大致相同,就不列出了。

1
2
3
4
5
6
7
8
void InOrderTraversal(BinTree BT)
{
if (BT) {
InOrderTraversal(Bt -> Left);
cout << BT -> Data << endl;
InOrderTraversal(BT -> Right);
}
}

非递归法

非递归法的中序遍历和先序遍历比较简单,大致相同,唯一的不同的地方在于访问的时间点不同。

中序遍历在第二次经过的时候访问,而先序遍历在第一次经过的时候就访问了。

  • 中序遍历

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    void InOrderTraversal(BinTree BT)
    {
    BinTree T = BT;
    stack <BinTree> s;
    while (T || !s.empty()) {
    while (T) { /*一直向左并将沿途结点压入堆栈 */
    s.push(T);
    T = T -> Left;
    }
    if (!s.empty()) {
    T = s.top(); /*结点弹出堆栈 */
    s.pop();
    cout << T -> Data << endl; /*访问(打印)结点 */
    T = T -> Right; /*转向右子树 */
    }
    }
    }
  • 先序遍历

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    void PreOrderTraversal(BinTree BT)
    {
    BinTree T = BT;
    stack <BinTree> s;
    while (T || !s.empty()) {
    while (T) { /*一直向左并将沿途结点压入堆栈 */
    cout << T -> Data << endl; /*访问(打印)结点 */
    s.push(T);
    T = T -> Left;
    }
    if (!s.empty()) {
    T = s.top(); /*结点弹出堆栈 */
    s.pop();
    T = T -> Right; /*转向右子树 */
    }
    }
    }

层序遍历

借助队列这个数据结构即可实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void LevelOrderTraversal(BinTree BT)
{
queue <BinTree> q;
if (!BT) return;
q.push(BT);
while (!q.empty()) {
BinTree T;
T = q.front();
q.pop();
cout << T -> Data << endl;
if (T -> Left) q.push(T -> Left);
if (T -> Right) q.push(T -> Right);
}
}

哈弗曼树

ZsqGRJ.md.png
ZsqJz9.md.png
Zsq8G4.md.png

文章作者: Yeoman Li
文章链接: https://yeomanli.github.io/2019/07/06/数据结构——树/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yeoman's Blog