[数据结构与算法]链式二叉树的前序创建，三种遍历· c语言版

相信大多数学过链表的人对链式二叉树的初始化和销毁都不会感到有什么难度，所以我们更应该关注二叉树的一些特性和它的三种遍历，通过对二叉树的学习我们可以很好地练习递归的使用。

大家可以先看一下二叉树的基本特性和结构特点

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int BTDataType;

typedef struct BinaryTreeNode
{
	BTDataType _data;
	struct BinaryTreeNode* _left;
	struct BinaryTreeNode* _right;
}BTNode;

　　1.二叉树的第i层上至多有2i-1个节点
　　2.深度为K的二叉树至多有2k-1个节点
　　3.任何一个二叉树中度数为2的节点的个数必度数为0的节点数目少1.
　　　说明:度数为0,为叶子节点。
　　4.具有n个节点的完全二叉树的深度为Log2N+1
　　5.若完全二叉树中的某节点编号为i，则若有左孩子编号为2i，若有右孩子编号为2i+1，? ? ? ? ? ? ? 父亲节点为i/2。

我们经常会遇到这样的题所以在此我推荐大家了解一下卡特兰数。?

?

卡特兰数

三种遍历

在前序遍历创建二叉树之前我们先来了解一下三种遍历

void BinaryTreePrevOrder(BTNode* root)
{
	if (!root)
	{
		printf("NULL ");
		return;
	}
	printf("%d ", root->_data);
	BinaryTreePrevOrder(root->_left);
	BinaryTreePrevOrder(root->_right);
}

void BinaryTreeInOrder(BTNode* root)
{
	if (!root)
	{
		printf("NULL ");
		return;
	}
	BinaryTreePrevOrder(root->_left);
	printf("%d ", root->_data);
	BinaryTreePrevOrder(root->_right);
}

void BinaryTreePostOrder(BTNode* root)
{
	if (!root)
	{
		printf("NULL ");
		return;
	}
	BinaryTreePrevOrder(root->_left);
	BinaryTreePrevOrder(root->_right);
	printf("%d ", root->_data);
}

前中后序只是打印的时间不同而已 。

前序创建

BTNode* Create_Tree()
{
    char c = str[pos++];//读取数组数据
    if(c =='#')//若是‘#’，说明该节点为空返回上一级节点
        return NULL;
    BTNode *root = (BTNode *)malloc(sizeof(BTNode));
    root->data = c        //若不为‘#’，则创建该节点，并为本节点赋值
    root->left = Create_Tree();//创建左子树
    root->right = Create_Tree();//创建右子树
    return root;
}
//字符数组的输入
while(scanf("%s",&str)!=EOF)
    {
        pos = 0;
        BiTNode *root = Create_Tree();
}