树与二叉树

  这里省去一千字，想知道树是什么或者二叉树是什么自己翻书。不知道用什么书？点[url=http://www.programfan.com/club/showbbs.asp?id=153002]这里[/url]。

二叉树的顺序存储

　将完全二叉树中所有结点按编号顺序依次存储在一个向量bt[1..n]中。
  可以简单得到结点编号与它的双父以及左右孩子编号的推算公式：
  parentID=[ID/2],leftChildID=ID*2,rightChildID=ID*2+1
  如果ID=1，则为根结点

二叉树的链式存储

  非常简单，与链表不同的是指针域指向两个孩子

  typedef struct _BNode BNode;
  typedef BNode *LPBNode;
  struct _BNode
  {
    LPVOID data;
    LPBNode lchild,rchild; // 左右孩子指针
  };

  而对于整棵树，则需要一个二叉树根，于是可以定义

  struct _BTree
  {
    LPBNode root;
    /*此外你还可以记录二叉树的其它信息*/
    DWORD nodes;
    DWORD depth;/*如结点数，深度等信息*/
  };

  树和二叉树最重要操作是遍历，主要算法是深度优先遍历和广度优先遍历，这两个算法比它本身要更有用得多。

  下面是从网上找到的实现代码，仅供参考。

-----------------------------------------------------------------------------
/* 二叉树的链接表示*/

#include<stdlib.h>
#include<stdio.h>

typedef int DataType;

struct BinTreeNode;                            /* 二叉树中结点 */
typedef  struct BinTreeNode     *PBinTreeNode;    /* 结点的指针类型 */

struct BinTreeNode { 
    DataType  info;                            /* 数据域 */
    PBinTreeNode llink;                     /* 指向左子女 */
    PBinTreeNode rlink;                     /* 指向右子女 */
};

typedef  struct BinTreeNode  *BinTree;

typedef  BinTree  *PBinTree;

PBinTreeNode root_btree(PBinTree t) {
    return *t;
}

PBinTreeNode leftChild_btree (PBinTreeNode p) {
    return p->llink;
}

PBinTreeNode rightChild_btree (PBinTreeNode p) {
    return p->rlink;
}

/*以下算法就是先将二叉树扩充为扩充的二叉树，
然后按先根次序周游的顺序输入结点的信息,
生成一个双链存储的二叉树的过程*/

/* 递归创建从根开始的二叉树 */
PBinTreeNode createRest_BTree() { 
    PBinTreeNode  pbnode;
    char ch;
    scanf("%c", &ch);
    if(ch == '@') pbnode = NULL;
    else { 
        pbnode = (PBinTreeNode )malloc(sizeof(struct BinTreeNode));
        if( pbnode == NULL )         {
            printf("Out of space!\n");
            return pbnode;
        }
        pbnode->info = ch;
        pbnode->llink = createRest_BTree();    /* 构造左子树 */
        pbnode->rlink = createRest_BTree();    /* 构造右子树 */
    }
    return pbnode;
}


/* 创建完整的二叉树 */
PBinTree  create_BTree( void ) { 
    PBinTree pbtree;
    pbtree = (PBinTree)malloc(sizeof(BinTree));
    if (pbtree != NULL)
        *pbtree = createRest_BTree( );  /* 递归创建从根开始的二叉树 */
    return pbtree; 
}


int main(){
    return 0;
}