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

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

建立一颗二叉树：

#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<queue>
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<Tree>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("按层访问的结果为：
");
    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("
这棵二叉树的页结点为");
    PI(Child_Node(tree)); 
    PI("
这棵二叉树的深度为");
    PI(Tree_Depth(tree)); 
    return 0;
}

 三序非递归遍历二叉树：

#include "handsomecui.h"
#include<stack>
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<Tree>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<Tree>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<Tree>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("
中序遍历为：");
    InOrder(tree);
    PI("
后序遍历为：");
    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;    
}