第八章树

二叉树的存储结构：顺序存储，链式存储，线索二叉树

顺序存储：挨个编号，父节点是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<data;

       preorder(r->left);

       preorder(r->right);

    }

}

void inorder(Tree *r){

    if(r!=NULL){

       inorder(r->left);

       cout<data;

       inorder(r->right);

    }

}

void postorder(Tree *r){

    if(r!=NULL){

       postorder(r->left);

       postorder(r->right);

       cout<data;

    }

}

以连接方式遍历二叉树非递归方式：

void porder(Tree *r){

    const int max(20);

    Tree *stack[max],*p;

    int top = -1;

    if(r!=NULL){

    top++;

    stack[top]=r;

    while(top>0){

       p = stack[top];

       top--;

       cout<data<

       if(p->right!=NULL){

           top++;

           stack[top]=p->right;

       }

       if(p->left!=NULL){

           top++;

           stack[top]=p->left;

       }

    }

    }

}

后续遍历的非递归实现，用栈实现，后序遍历的时候只有当左右孩子都遍历过之后才可以访问父节点，所以设置一个标志flag，判断当前节点r的右孩子是否是刚才访问过的p节点，如果是，代表左右孩子都已经访问过了，否则访问右子树flag=0。

void psorder(Tree *r){

    const int max(20);

    Tree *stack[max];

    Tree *p;

    int top = -1;

    int flag = 1;

    do{

       while(r){

           top++;

           stack[top] = r;

           r = r->left;

       }

       p = NULL;

       flag = 1;

       while(top!=-1&&flag){

           r = stack[top];

           if(r->right==p){

              cout<data<

              top--;

              p = t;

           }

           else{

              r = r->right;

              flag = 0;

           }

       }

    }while(top!=-1);

}

 

层序遍历二叉树，应用队列来实现

void levelorder(Tree *r){

    const int max(20);

    Tree *queue[max];

    int front = 0;

    int rear = 0;

    if(r!=NULL)

       cout<data<

    queue[rear] = r;

    rear = (rear+1)%max;

    while((rear+1)%max!=front){

       Tree *p = queue[front];

       front = (front+1)%max;

       if(p->left!=NULL){

           cout<data<

           queue[rear] = p->left;

           rear = (rear+1)%max;

       }

       if(p->right!=NULL){

           cout<data<

           queue[rear] = p->right;

           rear = (rear+1)%max;

       }

    }

}

从顺序存储的二叉树建链式存储的二叉树

 

void creat(Tree *&r ,char tree[],int n){

    int i = 0;

    int j = 1;

    int k = 2;

    r = new Tree;

    while(k

       r->data = tree[i];

       if(tree[j]!=NULL){

           Tree *l = new Tree;

           l->data = tree[j];

           r->left = l;

       }

       if(tree[k]!=NULL){

           Tree *l = new Tree;

           l->data = tree[k];

           r->right = l;

       }

       i = j;

       j = k;

       k++;

    }

}

void create(Tree *&r , char tree[] , int n , int i){

    if(i>n)

       r = NULL;

    else{

       r = new Tree;

       r->data = tree[i];

       create(r->left,tree,n,2*i);

       create(r->right,tree,n,2*i+1);

    }

}

显示各个节点，过程类似与先序遍历节点

void displayTree(Tree *r){

    if(r!=NULL){

       cout<data<

       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;

    }

}