二叉树的建立及其递归遍历（用C语言实现）

最近学习了数据结构中树的概念，但我还没有开始. 这应该是由我自己的懒惰和没有勤奋的练习造成的. 我以后应该多练习

以下是我对二叉树的总结

二叉树的特征是:

-每个节点最多具有两个子树，因此在二叉树中不存在度数大于2的节点. 请注意，最多有两个，也可能没有.

左子树和右子树按顺序排列二叉树的遍历算法c实现，并且顺序不能颠倒. 这可以反映在霍夫曼编码中. 顺序不同，编码方式也不同

-即使树中某个节点上只有一棵子树花，也有必要区分它是左子树还是右子树

二叉树通常具有五种形式

1. 空的二叉树

2. 根节点只有一个

3. 根节点只有左子树

4. 根节点只有正确的子树

二叉树的性质

1: 二叉树的第i层上最多有2 ^ i-1个节点

2: 深度为K的二叉树最多有2 ^ k-1个节点

注意: 深度K在这里表示具有K层的二叉树

3: 对于任何二叉树T，如果没有终端节点，且度为2的节点数为N2，则No = N2 + 1

4: 具有n个节点的完整二叉树的深度为[log2n] +1（[x]表示不大于x的最大整数）

1. 二叉树的存储结构（二进制链表）

//二叉树的存储结构，一个数据域，2个指针域
 typedef struct BiTNode
{
     char data;
     struct BiTNode *lchild,*rchild;
  }BiTNode,*BiTree;

2. 首先，我们必须建立一个二叉树. 要构建二叉树，我们必须了解二叉树的遍历方法. ，我在这里展示了构建二叉树的递归方法

///我在这里意识到的是，二叉树是在预遍历模式下创建的. 如果要使用中间顺序或后顺序方法来构建二叉树，则只需更改生成节点以及构造左右子树的顺序. <

//我在这里实现的是，二叉树的前序遍历方式创建，如果要使用中序或者后序的方式建立二叉树，只需将生成结点和构造左右子树的顺序改变即可
 void CreateBiTree(BiTree *T)
  {
      char ch;
      scanf("%c",&ch);
      if(ch=='#')
          *T=NULL;
      else
     {
         *T=(BiTree  )malloc(sizeof(BiTNode));
         if(!*T)
             exit(-1);
          (*T)->data=ch;
          CreateBiTree(&(*T)->lchild);
         CreateBiTree(&(*T)->rchild);
      }
 }

3. 二叉树遍历方法（递归建立）

void PreOrderTraverse(BiTree T)//二叉树的先序遍历
{
    if(T==NULL)
        return ;
    printf("%c ",T->data);
    PreOrderTraverse(T->lchild);
    PreOrderTraverse(T->rchild);
}
void InOrderTraverse(BiTree T)//二叉树的中序遍历
{
   if(T==NULL)
       return ;
   InOrderTraverse(T->lchild);
    printf("%c ",T->data);
   InOrderTraverse(T->rchild);
}
void PostOrderTraverse(BiTree T)//后序遍历
{
    if(T==NULL)
        return;
    PostOrderTraverse(T->lchild);
    PostOrderTraverse(T->rchild);
    printf("%c ",T->data);
}

4. 完整的代码

#include<stdio.h>
#include<stdlib.h>
typedef struct BiTNode
{
    char data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
void PreOrderTraverse(BiTree T)//二叉树的先序遍历
{
    if(T==NULL)
        return ;
    printf("%c ",T->data);
    PreOrderTraverse(T->lchild);
    PreOrderTraverse(T->rchild);
}
void InOrderTraverse(BiTree T)//二叉树的中序遍历
{
   if(T==NULL)
       return ;
   InOrderTraverse(T->lchild);
    printf("%c ",T->data);
   InOrderTraverse(T->rchild);
}
void PostOrderTraverse(BiTree T)//后序遍历
{
    if(T==NULL)
        return;
    PostOrderTraverse(T->lchild);
    PostOrderTraverse(T->rchild);
    printf("%c ",T->data);
}
void CreateBiTree(BiTree *T)
{
    char ch;
    scanf("%c",&ch);
    if(ch=='#')
        *T=NULL;
    else
    {
        *T=(BiTree  )malloc(sizeof(BiTNode));
        if(!*T)
            exit(-1);
        (*T)->data=ch;
        CreateBiTree(&(*T)->lchild);
        CreateBiTree(&(*T)->rchild);
    }
}
int main()
{
    BiTree T;
    CreateBiTree(&T);
    PreOrderTraverse (T);
    InOrderTraverse(T);
    PostOrderTraverse(T);
    return 0;
}

知识要点的补充

（1）构建二叉树时，这是先前顺序遍历的方式. 输入是展开二叉树，即告诉计算机什么是叶节点，否则它将始终递归. 输入“#”时，指针指向NULL，描述为叶节点.

转载后请注意实际的测试代码

（2）输入时，由于有缓冲区，请注意这一点，如果使用scanf进行输入二叉树的遍历算法c实现，则必须一次输入所有要输入的数据，然后按Enter

不要输入数据，只需按一次Enter键，就永远不会退出递归功能. 该界面停留在输入界面上，或者您想一一使用cin进入

图片显示了扩展的二叉树: （预遍历为: ABDG ## H ## CE#I ## F ##）

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-284321-1.html