二叉树

今天写的一波二叉树的操作。。感觉自己还得多多练习啊！ 依旧直接上代码了，8点了，得回去休息了T_T。

程序

/*
 * @Author: Zheng Qihang
 * @Date: 2018-07-10 09:38:39
 * @Last Modified by: Zheng Qihang
 * @Last Modified time: 2018-11-08 16:36:09
 */
#include <limits.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

/*
        data
       /    \
      V      V
    Left    Right
*/
typedef int ElementType;
typedef struct TreeNode {
    ElementType Data;
    struct TreeNode *Left;
    struct TreeNode *Right;
} * BinTree;

/************************* Queue define! **************************/
#define ElementQueueType BinTree
typedef struct QueueNode {
    ElementQueueType data;
    struct QueueNode *next;
} * QNode;

typedef struct QueueHeader {
    QNode front;
    QNode rear;
} * Queue;

/**
 * description  Create the Queue!
 * @param[in]   void
 * @retval      no
 **/
Queue CreateQueue(void) {
    Queue Q = (Queue)malloc(sizeof(struct QueueHeader));
    Q->front = NULL;
    Q->rear = NULL;
    return Q;
}

/**
 * description  Add Queue Node !
 * @param[in]   Queue header and a item
 * @retval      void
 **/
void AddQ(Queue Q, ElementQueueType item) {
    if (!Q) {
        return;
    }
    if (!item) {
        return;
    }
    QNode temp = (QNode)malloc(sizeof(struct QueueNode));
    temp->data = item;
    temp->next = NULL;
    // when the Queue is null
    if (!Q->front && !Q->rear) {
        Q->front = temp;
        Q->rear = temp;
    } else {
        Q->rear->next = temp;
        Q->rear = temp;
    }
}

/**
 * description  check the queue is empty
 * @param[in]   queue
 * @retval      int
 **/
int IsEmptyQ(Queue Q) { return !Q->front; }

/**
 * description  Delete the Queue Node
 * @param[in]   Queue header
 * @retval      data
 **/
ElementQueueType DeleteQ(Queue Q) {
    if (!Q) {
        return NULL;
    }
    if (IsEmptyQ(Q)) {
        return NULL;
    }
    QNode temp = Q->front;
    ElementQueueType tempdata;
    if (Q->front == Q->rear) {
        Q->front = NULL;
        Q->rear = NULL;
    } else {
        Q->front = Q->front->next;
    }
    tempdata = temp->data;
    free(temp);
    return tempdata;
}

void PrintQueue(Queue Q) {

    if (IsEmptyQ(Q)) {
        return;
    }
    printf("打印队列数据元素：\n");
    QNode temp = Q->front;

    for (; temp; temp = temp->next) {
        printf("0x%3lX   ", (unsigned long int)temp->data & 0xFFF);
    }
    printf("\n");
}

/************************* Queue define! **************************/

/************************* Stack define! **************************/

#define ElementStackType BinTree
typedef struct StackNode // node defination
{
    ElementStackType data;
    struct StackNode *next;
} * Stack; // Node is a pointer to _Node

int IsEmpty(Stack S) { return !S->next; }

Stack CreateStack(void) {
    Stack S = (Stack)malloc(sizeof(struct StackNode));
    S->next = NULL;
    return S;
}

ElementStackType Pop(Stack S) {
    ElementStackType temp;
    Stack tmepNode = S->next;
    if (tmepNode != NULL) {
        temp = tmepNode->data;
        S->next = tmepNode->next;
        free(tmepNode);
        return temp;
    } else {
        return NULL;
    }
}

void MakeEmpty(Stack S) {
    while (S->next != NULL) {
        Pop(S);
    }
}
void DisposeStack(Stack S) {
    MakeEmpty(S);
    free(S);
}

void Push(Stack S, ElementStackType X) {
    Stack tempNode = S->next;
    Stack newNode = (Stack)malloc(sizeof(struct StackNode));
    newNode->data = X;
    // printf("S->next %p\n",S->next);
    if (tempNode != NULL) {
        newNode->next = tempNode;
        // printf("%p = %p\n",newNode->next,tempNode);
    } else {
        newNode->next = NULL;
    }
    S->next = newNode;
    // printf("S->next %p\n",S->next);
}

ElementStackType Top(Stack S) {
    if (S->next != NULL) {
        return S->next->data;
    } else {
        return NULL;
    }
}

void PrintStack(Stack S) {
    Stack tep = S->next;
    while (tep != NULL) {
        printf("addr=0x%3lX  dataadd=0x%3lX  nextaddr=0x%3lX\n",
               (unsigned long int)tep & 0xFFF,
               (unsigned long int)tep->data & 0xFFF,
               (unsigned long int)tep->next & 0xFFF);
        tep = tep->next;
    }
}

/************************* Stack define! **************************/

/**
* description  first root then left
                child tree then right child tree
* @param[in]   BinTree
* @retval      void
**/
void PreOrderTraversal(BinTree BT) {
    if (BT) {
        printf("%d   ", BT->Data);
        PreOrderTraversal(BT->Left); // Recursion traversal
        PreOrderTraversal(BT->Right);
    }
}
/**
 * description  traversal the leaves
 * @param[in]   BinTree
 * @retval      void
 **/
void PreOrderPrintLeaves(BinTree BT) {
    if (BT) {

        if (!BT->Left && !BT->Left) {
            printf("%d   ", BT->Data);
        }
        PreOrderPrintLeaves(BT->Left); // Recursion traversal
        PreOrderPrintLeaves(BT->Right);
    }
}

/**
 * description  find the Binary tree alone length
 *              Tag==0 find the right
 *              Tag!=0 find the left
 * @param[in]   bintree
 * @retval      height
 **/
int FindTreeLength(BinTree BT, int tag) {
    if (BT) {

        if (tag) {
            return 1 + FindTreeLength(BT->Left, tag);
        } else {
            return 1 + FindTreeLength(BT->Right, tag);
        }
    } else {
        return 0;
    }
}
/*

// /**
//  * description  find the Binary tree height
//  *              Tag==0 find the right
//  *              Tag!=0 find the left
//  * @param[in]   bintree
//  * @retval      height
//  **/
// int FindTreeHeight(BinTree BT) {
//     int rightlen = FindTreeLength(BT, 0);
//     int leftlen = FindTreeLength(BT, 1);
//     return rightlen > leftlen ? rightlen : leftlen;
// }
/* the better implement */
int FindTreeHeight(BinTree BT) {
    int rightlen, leftlen, maxlen;
    if (BT) {
        rightlen = FindTreeHeight(BT->Right);
        leftlen = FindTreeHeight(BT->Left);
        maxlen = leftlen > rightlen ? leftlen : rightlen;
        return maxlen + 1;
    } else {
        return 0;
    }
}

/**
* description  first left child tree then
            root then  then right child tree
* @param[in]   BinTree
* @retval      void
**/
void InOrderTraversal(BinTree BT) {
    if (BT) {
        PreOrderTraversal(BT->Left); // Recursion traversal
        printf("%d   ", BT->Data);
        PreOrderTraversal(BT->Right);
    }
}
/**
* description  first left child tree then
             right child tree then root
* @param[in]   BinTree
* @retval      void
**/
void PostOrderTraversal(BinTree BT) {
    if (BT) {
        PreOrderTraversal(BT->Left); // Recursion traversal
        PreOrderTraversal(BT->Right);
        printf("%d   ", BT->Data);
    }
}

/*
* description first root then left
                child tree then right child tree
* @param[in]   BinTree
* @retval      void
**/
void PreStackTraversal(BinTree BT) {
    BinTree T = BT;
    Stack S = (Stack)malloc(sizeof(struct StackNode));
    // T!=null or stack is not empty
    while (T || !IsEmpty(S)) {
        while (T) { // push the left child tree in stack
            Push(S, T);
            printf("%d   ", T->Data);
            T = T->Left;
        }
        if (!IsEmpty(S)) {
            T = Pop(S);
            T = T->Right; // to the
        }
    }
    DisposeStack(S);
}
/*
* description  first left child tree then
            root then  then right child tree
* @param[in]   BinTree
* @retval      void
**/
void InStackTraversal(BinTree BT) {
    BinTree T = BT;
    Stack S = (Stack)malloc(sizeof(struct StackNode));
    // T!=null or stack is not empty
    while (T || !IsEmpty(S)) {
        while (T) { // push the left child tree in stack
            Push(S, T);
            T = T->Left;
        }
        if (!IsEmpty(S)) {
            T = Pop(S);
            printf("%d   ", T->Data);
            T = T->Right;
        }
    }
    DisposeStack(S);
}
/*
* description  first left child tree then
             right child tree then  root
* @param[in]   BinTree
* @retval      void
**/
void PostStackTraversal(BinTree BT) {
    BinTree T = BT;
    Stack S = (Stack)malloc(sizeof(struct StackNode));
    // T!=null or stack is not empty
    while (T || !IsEmpty(S)) {
        while (T) { // push the left child tree in S
            Push(S, T);
            T = T->Left;
        }
        if (!IsEmpty(S)) {
            T = Pop(S);
            if (T != BT) { // root don't print
                printf("%d   ", T->Data);
            }
            T = T->Right;
        }
    }
    printf("%d   ", BT->Data); // print root
    DisposeStack(S);
}

/* sequence traversal
    Use queue
    ----------------
            A           =>
    ----------------
    ----------------
        B       C       =>
    ----------------
    ----------------
    D     F   G    I    =>
    ----------------
    ----------------
        E       H       =>
    ----------------
*/
void LevelOrderTraversal(BinTree BT) {
    Queue myqueue = CreateQueue();
    BinTree T = BT;
    BinTree temp = NULL;
    AddQ(myqueue, T); // header add in queue
    while (!IsEmptyQ(myqueue)) {
        temp = DeleteQ(myqueue);
        printf("%d   ", temp->Data);
        AddQ(myqueue, temp->Left);
        AddQ(myqueue, temp->Right);
    }
}

/**
 * description  create the binary tree node
 * @param[in]   data
 * @retval      bintree
 **/
BinTree CreateTreeNode(int dat) {
    BinTree new = (BinTree)malloc(sizeof(struct TreeNode));
    new->Data = dat;
    new->Left = NULL;
    new->Right = NULL;
    return new;
}
void ConnectNode(BinTree root, BinTree left, BinTree right) {

    if (!root) {
        printf("error in null\n");
        return;
    }
    root->Left = left;
    root->Right = right;
}

/* create bin tree like this:
                  1                           A
            /          \                /          \
           2            3              B            C
         /   \        /   \          /   \        /   \
       4      5      6     7       D      E      F     G
      /        \    / \           /        \    / \
     8          9  10  11        H          I  J   K
 */
BinTree CreateBinTree(void) {
    printf("Create Binary Tree like this:\n \
                 1                           A\n \
            /          \\                /          \\ \n \
           2            3              B            C \n  \
        /   \\        /   \\          /   \\        /   \\ \n \
       4      5      6     7       D      E      F     G \n \
      /        \\    / \\           /        \\    / \\ \n \
     8          9  10  11        H          I  J   K \n \
    ");
    BinTree A = CreateTreeNode(1);
    BinTree B = CreateTreeNode(2);
    BinTree C = CreateTreeNode(3);
    BinTree D = CreateTreeNode(4);
    BinTree E = CreateTreeNode(5);
    BinTree F = CreateTreeNode(6);
    BinTree G = CreateTreeNode(7);
    BinTree H = CreateTreeNode(8);
    BinTree I = CreateTreeNode(9);
    BinTree J = CreateTreeNode(10);
    BinTree K = CreateTreeNode(11);
    ConnectNode(A, B, C);
    ConnectNode(B, D, E);
    ConnectNode(D, H, NULL);
    ConnectNode(E, NULL, I);
    ConnectNode(C, F, G);
    ConnectNode(F, J, K);
    return A;
}

BinTree BinaryTree = NULL;
int main(int argc, char const *argv[]) {
    printf("\n \
    Binary Tree Options\n \
    (1).make new linked Binary Tree;\n \
    (2).递归先序遍历;\n \
    (3).递归中序遍历;\n \
    (4).递归后序遍历;\n \
    (5).循环先序遍历;\n \
    (6).循环中序遍历;\n \
    (7).循环后序遍历;\n \
    (8).打印叶节点;\n \
    (9).输出树高度;\n \
    (a).层序遍历;\n \
    (q).quit;\n \
    ");
    while (1) {
        switch (getchar()) {
        case '1':
            BinaryTree = CreateBinTree();
            printf("create success!\n");
            break;
        case '2':
            printf("递归先序遍历:");
            PreOrderTraversal(BinaryTree);
            printf("\n");
            break;
        case '3':
            printf("递归中序遍历:");
            InOrderTraversal(BinaryTree);
            printf("\n");
            break;
        case '4':
            printf("递归后序遍历:");
            PostOrderTraversal(BinaryTree);
            printf("\n");
            break;
        case '5':
            printf("循环先序遍历:");
            PreStackTraversal(BinaryTree);
            printf("\n\n");
            break;
        case '6':
            printf("循环中序遍历:");
            InStackTraversal(BinaryTree);
            printf("\n\n");
            break;
        case '7':
            printf("循环后序遍历:");
            PostStackTraversal(BinaryTree);
            printf("\n\n");
            break;
        case '8':
            printf("打印叶节点:");
            PreOrderPrintLeaves(BinaryTree);
            printf("\n\n");
            break;
        case '9':
            printf("打印height:%d", FindTreeHeight(BinaryTree));
            printf("\n\n");
            break;
        case 'a':
            printf("层序遍历:");
            LevelOrderTraversal(BinaryTree);
            printf("\n");
            break;
        case 'q':
            exit(0);
            break;
        default:
            break;
        }
    }
    return 0;
}

执行结果

☁  binarytree  cat 1.txt | ./a.out

     Binary Tree Options
     (1).make new linked Binary Tree;
     (2).递归先序遍历;
     (3).递归中序遍历;
     (4).递归后序遍历;
     (5).循环先序遍历;
     (6).循环中序遍历;
     (7).循环后序遍历;
     (8).打印叶节点;
     (9).输出树高度;
     (a).层序遍历;
     (q).quit;
     Create Binary Tree like this:
                  1                           A
             /          \                /          \
            2            3              B            C
          /   \        /   \          /   \        /   \
        4      5      6     7       D      E      F     G
       /        \    / \           /        \    / \
      8          9  10  11        H          I  J   K
     create success!
递归先序遍历:1   2   4   8   5   9   3   6   10   11   7
循环先序遍历:1   2   4   8   5   9   3   6   10   11   7

递归中序遍历:2   4   8   5   9   1   3   6   10   11   7
循环中序遍历:8   4   2   5   9   1   10   6   11   3   7

递归后序遍历:2   4   8   5   9   3   6   10   11   7   1
循环后序遍历:8   4   2   5   9   10   6   11   3   7   1

打印叶节点:8   5   9   10   11   7

打印height:4

层序遍历:1   2   3   4   5   6   7   8   9   10   11