二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树，且有左右之分。所以实现二叉树的遍历用双链表比较简单。
实现一个数组的二叉树插入遍历
data_type arr[] = {35,45,23,44,33,65,13,54};根据二叉树的特点，我们定义一个包含左右孩子和本身数据的结构体作为根结点
typedef int data_type;
typedef struct treeNode
{struct treeNode *lchild;
struct treeNode *rchild;
data_type data;
}tree;写一个申请根节点的函数，返回申请到的空间的首地址
tree *createTree(data_type item)
{tree *pRoot = NULL;
pRoot = (tree *)malloc(sizeof(tree));
if(pRoot == NULL)
{return NULL;
}
memset(pRoot,0,sizeof(tree));
pRoot->data = item;
return pRoot;
}插入结点时，我们要先判断插入的值和根结点值谁更大，比根结点大我们将他插入到左孩子中，否则插入到右孩子中
int insertTree(tree *pRoot,data_type item)
{tree *pNew = NULL;
pNew = (tree *)malloc(sizeof(tree));
if(pNew == NULL)
{return -1;
}
memset(pNew,0,sizeof(tree));
pNew->data = item;
while(1)
{ if(pNew->data< pRoot->data)//插入左孩子处
{ if(pRoot->lchild != NULL)
{ pRoot = pRoot->lchild;
}
else
{ pRoot->lchild = pNew;
return 0;
}
}
else
{ if(pRoot->rchild != NULL)//插入右孩子处
{ pRoot = pRoot->rchild;
}
else
{ pRoot->rchild = pNew;
return 0;
}
}
}
}
二叉树的遍历分为以下三种：
先序遍历：遍历顺序规则为【根左右】
中序遍历：遍历顺序规则为【左根右】
后序遍历：遍历顺序规则为【左右根】
利用递归思想，实现二叉树的遍历。会在末尾讲解二叉树的递归
前序遍历//前序遍历
int preOrder(tree *pRoot)
{if(pRoot == NULL)
{return -1;
}
//先访问根结点
printf("%d ",pRoot->data);
//访问左子树
preOrder(pRoot->lchild);
//访问右子树
preOrder(pRoot->rchild);
}//中序遍历
int inOrder(tree *pRoot)
{if(pRoot == NULL)
{return -1;
}
inOrder(pRoot->lchild);
printf("%d ",pRoot->data);
inOrder(pRoot->rchild);
}//后序遍历
int postOrder(tree *pRoot)
{if(pRoot == NULL)
{return -1;
}
postOrder(pRoot->lchild);
postOrder(pRoot->rchild);
printf("%d ",pRoot->data);
}
拿我们的前序遍历来讲解
if(pRoot == NULL)
{return -1;
}
//先访问根结点
printf("%d ",pRoot->data); // 1
//访问左子树
preOrder(pRoot->lchild); // 2
//访问右子树
preOrder(pRoot->rchild); // 3接下来用一张自己画的图来详细说明
以上是我对递归思想的理解，如有错误请指正！
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
