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

树的定义

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

树的专门术语

根结点:最初的节点(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;    }}