二叉树的建树，按层遍历，结点总数，页结点以及深度, 以及三序非递归遍历二叉树；

建立一颗二叉树：

#include "handsomecui.h"typedef struct Node{    char data;    Node *left, *right;}Node, *Tree;Tree build(){    char c;    SI(c);    if(c == '#'){        return NULL;    }    else{        Node *root = new Node;        root->data = c;        root->left = build();        root->right = build();        return root;    }}void VisitTree(Node *root){    if(root == NULL){        return;    }        VisitTree(root->left);    VisitTree(root->right);    PI(root->data);}int main(){    Tree tree = build();    VisitTree(tree);    return 0;}

按层遍历：

#include "handsomecui.h"#include
     
      typedef struct Node{    char data;    Node *left, *right;}Node, *Tree;Tree build(){    char c;    SI(c);    if(c == '#'){        return NULL;    }    else{        Node *root = new Node;        root->data = c;        root->left = build();        root->right = build();        return root;    }}void Floor_Visit(Node *root){    queue
      
       Q;    Q.push(root);    while(!Q.empty()){        root = Q.front();        Q.pop();        PI(root->data);        if(root->left != NULL)            Q.push(root->left);        if(root->right != NULL)            Q.push(root->right);     }}int main(){    Tree tree = build();    PI("按层访问的结果为：\n");    Floor_Visit(tree);    return 0;}
      
     

结点总数，页结点以及深度：

#include "handsomecui.h"typedef struct Node{    char data;    Node *left, *right;}Node, *Tree;Tree build(){    char c;    SI(c);    if(c == '#'){        return NULL;    }    else{        Node *root = new Node;        root->data = c;        root->left = build();        root->right = build();        return root;    }}int Total_Node(Node *root){    if(root == NULL)        return 0;    else        return Total_Node(root->left) + Total_Node(root->right) + 1;}int Child_Node(Node *root){    if(root->left == NULL && root->right == NULL){        return 1;    }    else{        int temp = 0;        if(root->left != NULL)            temp += Child_Node(root->left);        if(root->right != NULL)            temp += Child_Node(root->right);        return temp;    }}int Tree_Depth(Node *root){    if(root == NULL)        return 0;    else        return max(Tree_Depth(root->left), Tree_Depth(root->right)) + 1;}int main(){    Tree tree = build();    PI("这棵二叉树的总结点为");    PI(Total_Node(tree));     PI("\n这棵二叉树的页结点为");    PI(Child_Node(tree));     PI("\n这棵二叉树的深度为");    PI(Tree_Depth(tree));     return 0;}

 三序非递归遍历二叉树：

#include "handsomecui.h"#include
     
      typedef struct Node{    char data;    Node *left, *right;}Node, *Tree;Tree build(){    char c;    SI(c);    if(c == '#'){        return NULL;    }    else{        Node *root = new Node;        root->data = c;        root->left = build();        root->right = build();        return root;    }}void PreOder(Node *root){    stack
      
       S;    while(!S.empty() || root != NULL){        while(root != NULL){            S.push(root);            PI(root->data);            root = root->left;        }        if(!S.empty()){            root = S.top();            S.pop();            root = root->right;        }    }}void InOrder(Tree root){    stack
       
        S;    while(!S.empty() || root != NULL){        while(root != NULL){            S.push(root);            root = root->left;        }        if(!S.empty()){            root = S.top();            PI(root->data);            S.pop();            root = root->right;        }    } }void PostOrder(Tree root){    stack
        
         S;    S.push(root);    Node *pre = NULL;    while(!S.empty()){        root = S.top();        if((root->left == NULL && root->right == NULL) || (pre != NULL && (pre == root->left || pre == root->right))){            PI(root->data);            S.pop();            pre = root;        }        else{            if(root->right != NULL){                S.push(root->right);            }            if(root->left != NULL){                S.push(root = root->left);            }        }    }}int main(){    Tree tree = build();    PI("先序遍历为：");    PreOder(tree);    PI("\n中序遍历为：");    InOrder(tree);    PI("\n后序遍历为：");    PostOrder(tree);    return 0;}
        
       
      
     

 中序线索二叉树：没有头，还不能遍历。。。

代码：

#include "handsomecui.h"typedef enum{    Link, Thread}PointTag;typedef struct Node{    char data;    Node *left, *right;    PointTag LTag, RTag;}Node, *Tree;Tree build(){    char c;    SI(c);    if(c == '#'){        return NULL;    }    else{        Node *root = new Node;        root->data = c;        root->left = build();        root->right = build();        return root;    }}Node *pre;void InThread(Tree root){    if(root == NULL)        return;    InThread(root->left);    if(root->left == NULL){        root->LTag = Thread;        root->left = pre;    }    if(root->right == NULL){        root->RTag = Thread;        pre->right = root;    }    pre = root;     InThread(root->right);}int main(){    Tree tree = build();    InThread(tree);    return 0;    }