[数据结构基础]链式二叉树及其前序、中序和后序遍历

一. 链式二叉树的结构和实现

1.1 链式二叉树的结构

链式二叉树，即使用链来表示一颗二叉树。链式二叉树的存储又可分为二叉链和三叉链，其中二叉链存储节点数据、指向左子节点的指针和指向右子节点的指针，三叉链相对于二叉链多存储指向父亲节点的指针，二叉链和三叉链的结构见图1.1。

1.2 链式二叉树的实现

链式二叉树的实现与链表节点的实现类似，要定义一个结构体，其成员包括存储的数据、指向左孩子节点的指针和指向右孩子节点的指针，如果是三叉链要多包含一个指向父亲节点的指针。

typedef int BTDataType;   //重定义节点数据类型//采用二叉链表定义
typedef struct BinaryTreeNode
{BTDataType data;   //节点数据struct BinaryTreeNode* left;  //指向左孩子节点的指针struct BinaryTreeNode* right; //指向右孩子节点的指针
};//采用三叉链表定义
typedef struct BinaryTreeNode
{BTDataType data;   //节点数据struct BinaryTreeNode* parent;  //指向父亲节点的指针 struct BinaryTreeNode* left;    //指向左孩子节点的指针struct BinaryTreeNode* right;   //指向右孩子节点的指针
};

1.3 链式二叉树节点的创建

采用BuyNode函数，创建链式二叉树节点（这里以二叉链表为例）。BuyNode函数有一个参数x，为节点要存储的数据，函数进行的操作有：为节点动态开辟内存空间、将x存入节点空间、将指向左孩子节点的指针和指向右孩子节点的指针均置为NULL。

BuyNode函数代码：

BTNode* BuyNode(BTDataType x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));assert(newnode);newnode->data = x;newnode->left = newnode->right = NULL;return newnode;
}

二. 二叉树的前序、中序和后序遍历

2.1 前序、中序和后序遍历的概念

前序遍历（Preorder Traversal 亦称先序遍历）：在遍历左右子树之前访问根节点。具体遍历顺序为：根节点 -> 左子树 -> 右子树。
中序遍历（Inorder Traversal）：访问根节点发生在遍历左右子树之间。具体遍历顺序为：左子树 -> 根节点 -> 右子树。
后序遍历（Postorder Traversal）：在遍历左右子树之后访问根节点。具体遍历顺序为：左子树 -> 右子树 -> 根节点。

如图1.2所示的二叉树（ $\varphi$ 表示空），其前序、中序、后序遍历的访问顺序分别为：

前序遍历：1 -> 2 -> 3 -> NULL -> 4 -> 5 -> 6
中序遍历：3 -> 2 -> NULL -> 1 -> 5 -> 4 -> 6
后序遍历：3 -> NULL -> 2 -> 5 -> 6 -> 4 -> 1

2.2 链式二叉树的前序、中序、后序遍历的函数实现

无论是对链式二叉树进行前序、中序还是后序遍历，都是采用递归的思想来实现的。

2.2.1 前序遍历函数PreOrder

向函数传入指向根节点的指针作为参数，判断根节点是否为空，如果为空，则函数返回。如果不为空，则先打印该节点的数据，然后先后将指向左孩子节点的指针和指向右孩子节点的指针作为参数传入函数PreOrder进行递归调用即可。

PreOrder函数代码：

void PreOrder(BTNode* root)
{if (NULL == root){return;}printf("%d ", root->data);PreOrder(root->left);PreOrder(root->right);
}

2.2.2 中序遍历函数InOrder

向函数传入指向根节点的指针作为参数，判断根节点是否为空，如果为空，则函数返回。如果不为空，则先将指向左孩子节点的指针作为参数传给函数InOrder递归调用，再打印当前节点数据，最后将指向右孩子节点的指针作为参数传给函数InOrder递归调用即可。

InOrder函数代码：

void InOrder(BTNode* root)
{if (NULL == root){return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right);
}

2.2.3 后序遍历函数PostOrder

向函数传入指向根节点的指针作为参数，判断根节点是否为空，如果为空，则函数返回。如果不为空，则首先先后将指向左孩子节点的指针和指向右孩子节点的指针作为传入函数进行递归调用，然后打印节点数据即可。

PostOrder函数代码：

void PostOrder(BTNode* root)
{if (NULL == root){return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->data);
}