1.树的几个基本概念

（1）n个结点的集合，如果n=0， S是空树；

（2）结点的度：一个节点含有的子树的个数；

（3）树的度：树中节点的度的最大值；

（4）树的高度（深度）：树的层数。

2.二叉树的特点

（1）每个节点最多只能有两棵子树，也就是说二叉树不存在度大于2的节点；

（2）二叉树的子树有左右之分，左右子树的次序不能颠倒；

（3）二叉树有五种形态：①空树、②只有一个根节点、③一个根节点和一个左子树、④一个根节点和一个右子树、⑤一个根节点和左右子树。

（4）满二叉树：一个二叉树，如果每一层的节点数都达到了最大值2；

（5）完全二叉树：从上到下，从左到右，按照每个节点有两个分支进行编号，中间只要没有断开的，就是完全二叉树。

3.递归算法的遍历（顺序依次为先序遍历、中序遍历、后序遍历、层次遍历）

（1）先序遍历：根左右，创建二叉树，先遍历根节点，再遍历左子树，最后遍历右子树。

（2）中序遍历：左根右，创建二叉树，先遍历左子树，再遍历根节点，最后遍历右子树。

（3）后续遍历：左右根，创建二叉树，先遍历左子树，再遍历右子树，最后遍历根节点。

（4）层遍历——借助队列，从上到下，从左到右依次遍历。

        算法思想：

      1.将根节点入队；

      2.判断队列是否为空，如果不空，则获取对头元素front，访问并出队；

      3.判断front是否有左右孩子，如果有，按照先入左，再入右的顺序将孩子入队；

     4.循环2.3，直到队列为空，则遍历完毕。

参考代码如下：

#include<iostream>
using namespace std;
#include<stack>
#include<queue>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>


//节点的结构
typedef struct node
{
    char value;//当前节点本身的值
    struct node* left;//当前节点指向左子树的指针
    struct node* right;//当前节点指向右子树的指针
}Node;

//树的结构
typedef struct tree
{
    Node* root;//指向树的根节点的指针
}Tree;

//递归
void InitTree(Tree* t);//初始化树，其实就是将树的root初始化为NULL
Node* Create(char*& str);//创建二叉树，创建成功后，将根节点返回
void PreOrder(Node* root);//先序遍历以根为root的二叉树 根左右
void InOrder(Node* root);//中序遍历以根为root的二叉树 左根右
void PostOrder(Node* root);//后序遍历以根为root的二叉树 左右根
void LevOrder(Node* root);//层遍历

//根据先序遍历创建二叉树，先创建根，在创建根的左子树，最后 创建根的右子树
Node* Create(char*& str)
{
    if (*str == '*')
        return NULL;
    else
    {
        Node* newnode = (Node*)malloc(sizeof(Node));//先开辟一个节点空间
        newnode->value = *str;//将当前不是*的字符赋给当前节点，创建根
        newnode->left = Create(++str);//创建当前节点的左子树，调用创建函数
        newnode->right = Create(++str);//创建当前结点的右子树
        return newnode;

    }
}

//初始化
void InitTree(Tree* t)
{
    t->root = NULL;
}

//递归算法——先序遍历二叉树
void PreOrder(Node* root)
{
    if (root != NULL)
    {
        //cout << root->value << " ";//先遍历root
        printf("%c ", root->value);//先遍历root
        PreOrder(root->left);//遍历当前根的左子树
        PreOrder(root->right);//遍历当前根的右子树
    }
}

//递归算法——中序遍历二叉树
void InOrder(Node* root)
{
    if (root != NULL)
    {
        InOrder(root->left);//先遍历左子树
        printf("%c ", root->value);//遍历根
        InOrder(root->right);//遍历右子树
    }
}

//递归算法——后序遍历二叉树
void PostOrder(Node* root)
{
    if (root != NULL)
    {
        PostOrder(root->left);//递归遍历左子树
        PostOrder(root->right);//递归遍历右子树
        printf("%c ", root->value);//遍历根
    }
}

//层次遍历二叉树
void LevOrder(Node* root)
{
    queue<Node*>qq;//定义队列qq，存储指向每个节点的指针
    if (root == NULL)
        return;
    Node* front = NULL;//指向队头的指针
    qq.push(root);//将根入队
    while (!qq.empty())
    {
        front = qq.front();//获取队头
        qq.pop();
        printf("%c ", front->value);
        //将当前front的左右孩子（下一层）入队
        if (front->left != NULL)
            qq.push(front->left);
        if (front->right != NULL)
            qq.push(front->right);
    }
    printf("\n");
}



int main()
{
    Tree t;
    InitTree(&t);//空树
     char* str =(char*) "ABDG**HI****CE*J**F**";//变量强转
    t.root = Create(str);
 
    printf("先序遍历二叉树\n");
    PreOrder(t.root);
    printf("\n");

    printf("中序遍历二叉树:\n");
    InOrder(t.root);
    printf("\n");

    printf("后序遍历二叉树:\n");
    PostOrder(t.root);
    printf("\n");

    printf("层遍历二叉树:\n");
    LevOrder(t.root);
    printf("\n");
}

4.非递归算法的遍历（顺序依次为先序遍历、中序遍历、后序遍历）

非递归算法——借助栈

 （1）先序遍历

          算法思想：根左右

1.                           1.将根节点入栈；
2.                          2.判断栈是否为空，如果栈不空，则获取栈顶元素top，并出栈输出；
3.                          3.看top是否有右左孩子，如果有，将孩子有右左的顺序入栈——将右孩子记住，                                防止左子树访问完后，右孩子找不到；
4.                          4.继续执行2.3，直到栈空为止。

（2）中序遍历

        算法思想：左根右，要将当前左子树分支上的所有节点都入栈，要么找不到

1.                         1.从根开始，如果不为空，依次将左子树入栈；
2.                         2.判断栈是否为空，如果不空，获取栈顶top，出栈并输出，然后用指针p记住当前                           出栈结点的右孩子；
3.                         3.判断栈是否为空，如果不空，获取栈顶top，出栈并输出，然后用指针p记住当前                             出栈结点的右孩子；
4.                        4.循环2，3步骤，直到p为空并且栈为空结束

(3)后序遍历

 算法思想：左右根，需要一个指针记住已经遍历过的节点

1. ①入栈的情况：1.如果当前节点有孩子，则按照右左的顺序入栈；
2.                       2.指向上一次出栈的节点；
3. ②出栈的情况：1.如果当前节点没有孩子，则当前节点出栈；
4.                     2.如果当前栈顶节点有孩子，但是孩子已经遍历（出栈），则需要出栈。
5. 参考代码如下：

6. #include<iostream>
   using namespace std;
   #include<stack>
   #include<queue>
   #include<stdio.h>
   #include<stdlib.h>
   #include<string.h>
   
   
   //节点的结构
   typedef struct node
   {
       char value;//当前节点本身的值
       struct node* left;//当前节点指向左子树的指针
       struct node* right;//当前节点指向右子树的指针
   }Node;
   
   //树的结构
   typedef struct tree
   {
       Node* root;//指向树的根节点的指针
   }Tree;
   
   //非递归
   void InitTree(Tree* t);//初始化树，其实就是将树的root初始化为ULL
   Node* Create(char*& str);//创建二叉树，创建成功后，将根节点返回
   void PreOrder1(Node* root);//前序遍历
   void InOrder1(Node* root);//中序遍历
   void PostOrder1(Node* root);//后序遍历
   
   //根据先序遍历创建二叉树，先创建根，在创建根的左子树，最后 创建根的右子树
   Node* Create(char*& str)
   {
       if (*str == '*')
           return NULL;
       else
       {
           Node* newnode = (Node*)malloc(sizeof(Node));//先开辟一个节点空间
           newnode->value = *str;//将当前不是*的字符赋给当前节点，创建根
           newnode->left = Create(++str);//创建当前节点的左子树，调用创建函数
           newnode->right = Create(++str);//创建当前结点的右子树
           return newnode;
   
       }
   }
   
   //初始化
   void InitTree(Tree* t)
   {
       t->root = NULL;
   }
   
   
   void PreOrder1(Node* root)//非递归先序遍历
   {
       stack<Node*>ss;//定义栈，存储指向结点的指针
       if (root == NULL)
           return;
       ss.push(root);
       Node* top = NULL;//top指向栈顶元素
       while (!ss.empty())
       {
           top = ss.top();
           printf("%c ", top->value);
           ss.pop();//出栈
           //将当前节点的toop的孩子入栈，按照右左的顺序入栈
           if (top->right != NULL)
               ss.push(top->right);
           if (top->left != NULL)
               ss.push(top->left);
       }
       printf("\n");
   }
   
   void InOrder1(Node* root)//非递归中序遍历
   {
       if (root == NULL)
           return;
       Node* p = root, * top = NULL;
       stack<Node*>ss;
       while (p != NULL || !ss.empty())
       {
           //从p开始，将所有左分支入栈
           while (p!=NULL)
           {
               ss.push(p);
               p = p->left;
           }
           if (!ss.empty())
           {
               top = ss.top();
               ss.pop();
               printf("%c ", top->value);
               //过程到当前节点的右分支
               p = top->right;
           }
       }
       printf("\n");
   }
   
   void PostOrder1(Node* root)//非递归后序遍历
   {
       if (root == NULL)
           return;
       stack<Node*>ss;
       Node* top = NULL, * pre = NULL;
       ss.push(root);
       while (!ss.empty())
       {
           top = ss.top();//获得栈顶
           //出栈，要么没孩子，要么孩子已经出栈
           if (top->left == NULL && top->right == NULL ||pre!=NULL&& pre == top->left ||pre!=NULL&& pre == top->right)
           {
               printf("%c ", top->value);
               ss.pop();
               pre = top;//pre指针记住当前节点，为了下一次查看是否已经出栈
           }
           else//右孩子，则按照右左顺序入栈
           {
               if (top->right != NULL)
                   ss.push(top->right);
               if (top->left != NULL)
                   ss.push(top->left);
           }
       }
       printf("\n");
   }
   
   int main()
   {
       Tree t;
       InitTree(&t);//空树
        char* str =(char*) "ABDG**HI****CE*J**F**";//变量强转
       t.root = Create(str);
       
       printf("非递归先序遍历二叉树:\n");
       PreOrder1(t.root);
       printf("\n");
   
       printf("非递归中序遍历二叉树:\n");
       InOrder1(t.root);
       printf("\n");
   
       printf("非递归后序遍历二叉树:\n");
       PostOrder1(t.root);
       printf("\n");
   }

   如有错误，敬请指正！

7. 您的点赞与收藏是对我最大的鼓励与支持。