树的存储结构
1．双亲数组存储结构
用一个一维数组存储树中的各个节点，数组元素是一个记录，包含data和parent两个字段，分别表示节点的数据值和其双亲在数组中的下标。其类型定义如下：
typedef struct { ElemType data; int parent; } ParType[MaxSize];
在这个一维数组中，树中节点可按任意顺序存放。
例如，图5-1中给出的树，它的双亲数组存储表示如图5-3所示。其中，规定下标为0的位置存储的节点是根节点。
位置 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 空闲 | Maxsize-1 |
data | A | B | C | D | E | F | G | H | … | |
parent | -1 | 0 | 0 | 0 | 2 | 2 | 3 | 4 | … |
图5-3 树的双亲数组存储结构
在双亲数组中，找某个节点的双亲或祖先是很方便的，但要找某个节点的孩子或兄弟则较麻烦，需要遍历整个数组。
2．孩子链表存储结构
把每个节点的孩子节点排列起来，构成一个单链表，称为孩子链表。n个节点的树有n个这样的孩子链表，其中，树叶的孩子链表为空表。为便于查找，n个链表的表头指针放在一个顺序表中。这个顺序表中的每个元素有两个字段：一个存放节点的值；另一个存放第一个孩子的地址。孩子链表中的每个节点也有两个字段：指示孩子节点的值存放的位置；另一个存放下一个孩子的地址。在顺序表中，各元素可以按任意顺序存放。在每个孩子链表中，各节点也可以按任意顺序链接。
单链表中每个节点的类型定义如下：
typedef struct node1 { int adjvex; /*该节点值在顺序表中的位置*/ struct node1 *next; } ChildType;
顺序表的类型定义如下：
typedef struct { ElemType data; ChildType *children; } Child[MaxSize];
图5-4是图5-1所示树的孩子链表存储结构。其中，规定表头中下标为0的位置存储的节点是根节点。
图5-4 树的孩子链表存储结构
显然，在孩子链表中，找某个节点的孩子很容易，但找节点的双亲则较困难。
3．孩子兄弟链表存储结构
孩子兄弟链表存储结构是一种二叉链表，链表中每个节点包含两个指针，分别指向对应节点的第一个孩子和下一个兄弟。每个节点的类型定义如下：
typedef struct node2 { ElemType data; struct node2 *child,*brother; } CBNodeType;
图5-5是图5-1所示树的孩子兄弟链表存储结构，其中，T1指针指向树的根节点。
出自：http://www.qacn.net/viewchapter.aspx?topicid=147&chapterid=2771
二叉树的存储结构
1、顺序存储结构
A(B(D,E(G,H)),C(,F(I)))存储为：
| A | B | C | D | E | F | G | H | I |
2、链式存储结构
利用左右孩子指针。
二叉树的基本运算及四种遍历方式
#include <iostream> #include <cstdlib> using namespace std; #define MaxSize 100 typedef struct Node{ char data; struct Node *lChild, *rChild; }BTNode; //先序遍历 void PreOrder(BTNode *bt){ if(bt != NULL){ cout << bt->data << " "; PreOrder(bt->lChild); PreOrder(bt->rChild); } } //中序遍历 void InOrder(BTNode *bt){ if(bt != NULL){ InOrder(bt->lChild); cout << bt->data << " "; InOrder(bt->rChild); } } //后序遍历 void LastOrder(BTNode *bt){ if(bt != NULL){ LastOrder(bt->lChild); LastOrder(bt->rChild); cout << bt->data << " "; } } //层次遍历 //先是根节点进入队列，紧接着是其左右孩子，在用左右孩子循环。 void LeverOrder(BTNode *bt){ BTNode *p; BTNode *qu[MaxSize]; int front,rear; front = rear = -1; rear++; qu[rear] = bt; while(front != rear){ front = (front+1)%MaxSize; p = qu[front]; cout << p->data << " "; if(p->lChild != NULL){ rear = (rear+1)%MaxSize; qu[rear] = p->lChild; } if(p->rChild != NULL){ rear = (rear+1)%MaxSize; qu[rear] = p->rChild; } } } //以括号表示法输出二叉树 void DispBTree(BTNode *bt) { if(bt!=NULL) { cout << bt->data; if(bt->lChild!=NULL || bt->rChild!=NULL) { cout<<"("; DispBTree(bt->lChild); /*递归处理左子树*/ if(bt->rChild!=NULL) cout << ","; DispBTree(bt->rChild); /*递归处理右子树*/ cout<<")"; } } } //叶子节点数 int LeafCount(BTNode *bt){ int l,r; if(bt == NULL){ return 0; } else{ if(bt->lChild == NULL && bt->rChild == NULL){ return 1; } else{ l = LeafCount(bt->lChild); r = LeafCount(bt->rChild); return l+r; } } } //二叉树节点个数 int NodeCount(BTNode *bt){ int l,r; if(bt == NULL){ return 0; } else{ l = NodeCount(bt->lChild); r = NodeCount(bt->rChild); return (l+r+1); } } //二叉树高度运算 int BTHeight(BTNode *bt){ int l,r; if(bt == NULL){ return 0; } else{ char d = bt->data; //cout << d << endl; l = BTHeight(bt->lChild); //cout << "l: " << l << endl; r = BTHeight(bt->rChild); //cout << "r: " << r << endl; //cout << (l>r ? (l+1):(r+1)) << endl; return l > r ? (l+1):(r+1); } } //根据二叉树的括号表示法str建立二叉链 void CreateBTree(BTNode* &bt,char* str){ BTNode* st[MaxSize]; BTNode* p = NULL; bt = NULL; int k,top=-1,j=0; char ch = str[j]; while(ch != '