算法导论第10章 10.4 有根树的表示

本文链接：https://blog.csdn.net/mishifangxiangdefeng/article/details/7707756

一、概念

1.二叉树

（1）用域p、left、right来存放指向二叉树T中的父亲、左儿子、右儿子。没有则为NULL。

（2）结点结构

struct node
{
    node *p;
    node *left;
    node *right;
    int key;
};

（3）树的结构

struct Bin_Tree
{
    node *head;
};

2.分支数无限的有根树

（1）左孩子右兄弟表示法

（2）结点结构

struct node
{
    node *p;
    node *left_child;
    node *right_sibling;
    int key;
};

（3）树的结构

struct Tree
{
    node *head;
};

二、练习

10.4-2

算法导论 10.4-2 O(n)时间递归遍历二叉树

TREE-PRINT(T)
1    print key[T]
2    if left[T] != NIL
3        TREE-PRINT(left[T])
4    if right[T] != NIL
5        TREE-PRINT(right[T])

10.4-3

算法导论 10.4-3 O(n) 二叉树非递归遍历

TREE-PRINT(T, S)
 1    print key[T]
 2    PUSH(S, T)
 3    while true
 4        if left[T] != NIL
 5            then T <- left[T]
 6        else
 7            do
 8                T = POP(S)
 9                if T = NIL
10                    then return
11            while left[T] = NIL
12            T <- right[T]

10.4-4

与二叉树的遍历过程相同

10.4-5

见算法导论-10.4-5

采用类似中序遍历的处理方法，对一个结点，可以分为以下几种情况

1.从父结点进入子结点进行处理

（1）如果有左孩子，就处理左孩子

（2）返回到自己

（3）访问自己

（4）如果有右孩子，就处理右孩子

（5）返回到自己的父结点

2.从左孩子返回，说明左孩子已经处理过，自己还没访问，自己的右孩子也没有处理过，就进行1-（2）