【资料结构】树的定义与追踪

树的定义

一种存资料的型态，由最初的节点延伸下多个分支，每个分支都个有个自的子分支，分支下可分割成彼此不相交的子集合，也称为子树。

树的专门术语

• 根结点:最初的节点(A)
• 阶层:树中的子分层树(E的层次为3，树的高度是4)
• 节点:分支下所连接的空间(B,C,D......)
• 父节点:节点的上一个节点(B是D的父节点)
• 兄弟:在同一个分支层，且有同一个父节点(D,E为兄弟)
• 祖先,兄弟:子分支与子分支源的关系(I的祖先为A,C,H，C的祖先为F,G,H,I)
• 终端节点(树叶):最末端没有分支的节点(E,F)
• 内部节点:非终端节点(A,B,C,H)
• 分支度:分支的数量(B的分支度数量为2,数的分支度为3)
  

树的表示法

• 串列:在非完满树中，会有浪费空间的缺点
• 左小孩右兄弟:将每个小孩节点放到左边，兄弟节点放到右边，

二元树

由一个跟节点和两个分支构成的树，两个分支一位置被称为左子树与右子树，树不可为空集合，二元树可以，且有顺序之分。

特殊形态的二元树

• 歪斜二元树:皆为子节点的二元树
• 完全二元树:每个分支的子节点树皆为二或零
• 完满二元树:每个分之的子节点节树为二，深度为k的时候，节点为(2^K)-1

二元树的性质

• 二元树的最大节点数为 (2^K)-1，深度为K时

二元树的表示法

先略

二元树的追踪

    左儿子 资料 右儿子
      L    V    R

依照追踪组合有六种:LVR、LRV、VLR、VRL、RVL、RLV
因追踪有受先左再右，因此剩3种:LVR 、 LRV 、 VLR

• 中序
• 

void inorder(tree_pointer ptr)
/*中序追踪 */
{
    if (ptr) {
L     inorder(ptr->left_child);       
V     printf(“%d”, ptr->data);      
R     inorder(ptr->right_child);  
    }
}

• 前序
  

void preorder(tree_pointer ptr)
/* 前序追踪 */
{
     if (ptr) {
V       printf(“%d”, ptr->data); 
L       preorder(ptr->left_child);       
R       preorder(ptr->right_child);  
     }
}

• 後序
  

void postorder(tree_pointer ptr)
/* 後序追踪 */
{
    if (ptr) {
L      postorder(ptr->left_child);       
R      postorder(ptr->right_child);  
V      printf(“%d”, ptr->data);
    }
}

• 叠代(中序)
  利用叠代的方式作中序追踪

void iter_inorder(tree_pointer node)
{
  int top= -1; /* 初始化堆叠 */
  tree_pointer stack[MAX_STACK_SIZE];
  for (;;) {
     for (; node; node = node->left_child)
         push(node);  /* 将节点加入堆叠 */
     node= pop();  /* 自堆叠删除节点 */
     if (!node) break;  /* 空堆叠 */
     printf(“%d”, node->data);
     node = node->right_child;
  }
}

• 阶序
  

void level_order(tree_pointer ptr)
/* 阶层次序追踪 */
{
    int front = rear = 0;
    tree_pointer queue[MAX_QUEUE_SIZE];
    if (!ptr) return;   /* 空树 */
    addq(ptr);
    for (;;) {
        ptr = deleteq();
        if (ptr) {
        printf (“%d”, ptr ->data);
        if (ptr ->left_child)
            addq(ptr ->left_child);
        if (ptr ->right_child)
            addq(ptr ->right_child);
        }
        else break;
    }
}