第八章树
时间：2010-08-06 来源：静止的流水
二叉树的存储结构：顺序存储，链式存储，线索二叉树
顺序存储：挨个编号，父节点是i，左子树节点为2i，右子树节点为2i+1，存储在一维数组里面。
链式存储：存储结构为
typedef struct Tree{
int data;
struct Tree *left,*right;
}Tree;
线索二叉树：
typedef struct Node{
int data;
int ltag,rtag;
struct Node *left,*right;
}Node;
Ltag=0,left指向左孩子，ltag=1，left指向某种序列的前驱；rtag=0，right指向右孩子，rtag=1，right指向某种序列遍历的后继。
以链式存储结构存储的二叉树递归遍历程序如下：
void preorder(Tree *r){
if(p!=NULL){
cout<<r->data;
preorder(r->left);
preorder(r->right);
}
}
void inorder(Tree *r){
if(r!=NULL){
inorder(r->left);
cout<<r->data;
inorder(r->right);
}
}
void postorder(Tree *r){
if(r!=NULL){
postorder(r->left);
postorder(r->right);
cout<<r->data;
}
}
显示各个节点，过程类似与先序遍历节点
void displayTree(Tree *r){
if(r!=NULL){
cout<<r->data<<endl;
if(r->left!=NULL||r->right!=NULL){
cout<<"(";
displayTree(r->left);
if(r->right!=NULL)
cout<<",";
displayTree(r->right);
cout<<")";
}
}
}
求二叉树的深度，递归求解，r的深度等于左右子树最大深度+1
int depth(Tree *r){
if(r==NULL)
return 0;
else{
int d1 = depth(r->left);
int d2 = depth(r->right);
return d1>d2?d1:d2+1;
}
}
相关阅读 更多 +
