二叉树的基本操作
二叉树的基本操作（C 语言版）
1 二叉树的定义
二叉树的图长这样：
二叉树是每个结点最多有两个子树的树结构，常被用于实现二叉查找树和二叉堆。二叉树是链式存储结构，用的是二叉链，本质上是链表。二叉树通常以结构体的形式定义，如下，结构体内容包括三部分：本节点所存储的值、左孩子节点的指针、右孩子节点的指针。
struct TreeNode {//树的结点int data;//数据域struct TreeNode* lchild;//指向左孩子节点struct TreeNode* rchild;//指向右孩子节点
};
当然，我们也可以为我们的的树节点结构体重新定义一下名字，使用 C 语言中的 typedef 方法就可以了。
struct TreeNode {//树的结点int data;//数据域struct TreeNode* lchild;//指向左孩子节点struct TreeNode* rchild;//指向右孩子节点
} BiNode, *BiTree;
2 二叉树的建立
二叉树的操作通常使用递归方法，二叉树的操作可以分为两类，一类是需要改变二叉树的结构的，比如二叉树的创建、节点删除等等，这类操作，传入的二叉树的节点参数为二叉树指针的地址，这种参入传入，便于更改二叉树结构体的指针（即地址）。
如下是二叉数创建的函数，这里我们规定，节点值必须为大于 0 的数值，如果不是大于 0 的数，则表示结束继续往下创建子节点的操作。然后我们使用递归的方法以此创建左子树和右子树。
比如说，建立这个二叉树：
5/ \3 8/ / \ 2 6 9
首先根据这个二叉树，我们先模拟一下：
先序输入：5 3 2 0 0 0 8 6 0 0 9 0 0
先序遍历输出：5 3 2 8 6 9
中序遍历输出：2 3 5 6 8 9
后序遍历输出：2 3 6 9 8 5
层次遍历输出：5 3 8 2 6 9
下面通过先序的方式建立二叉树：
- 第一种建立二叉树：使用一级指针
//先序建立二叉树
BiTree CreateTree() {int data;scanf("%d", &data);//根节点数据BiTree root;if (data <= 0) {return NULL;} else {root = (BiTree)malloc(sizeof(BiNode));root->data = data;root->lchild = CreateTree();root->rchild = CreateTree();}return root;
}
测试使用：
//测试
int main() {//BiTree root;//CreateTree(&root);BiTree root = NULL; root = CreateTree();//创建树 PreOrderTraverse(root);//先序遍历输出 return 0;
}
- 第二种建立二叉树：使用二级指针
//先序建立二叉树
void CreateTree(BiTree* root) {int data;scanf("%d", &data);//根节点数据if (data <= 0) {*root = NULL;} else {(*root) = (BiTree)malloc(sizeof(BiNode));(*root)->data = data;CreateTree(&((*root)->lchild));CreateTree(&((*root)->rchild));}
}
测试使用：
//测试
int main() {BiTree root;CreateTree(&root);//BiTree root = NULL; //root = CreateTree();//创建树 PreOrderTraverse(root);//先序遍历输出 return 0;
}
如果没有要求的话，我比较倾向于第一种！
3 二叉树的遍历
3.1 先序遍历
先序遍历的思路：
先序遍历的过程是首先访问根结点，然后先序遍历根的左子树，最后先序遍历根的右子树。对于根的左子树和右子树，遍历的过程相同。
方案一：递归
- 采用递归的方式来实现：
//先序遍历二叉树:递归实现
void PreOrderTraverse(BiTree root) {if (root) {printf("%d ", root->data);PreOrderTraverse(root->lchild);PreOrderTraverse(root->rchild);}
}
方案二：非递归
- 非递归实现：引入辅助栈
//先序遍历二叉树:非递归实现
void PreOrderTraverseNonRec(BiTree root) {BiTree stack[MaxSize];BiTree p;int top = -1;if (root != NULL) {//根节点入栈top++;stack[top] = root;//栈不空时循环while (top > -1) {//出栈并访问该节点p = stack[top];top--;printf("%d ", p->data);//右孩子入栈if (p->rchild != NULL) {top++;stack[top] = p->rchild;}//左孩子入栈if (p->lchild != NULL) {top++;stack[top] = p->lchild;} } }
}
3.2 中序遍历
中序遍历的思路
中序遍历的过程是首先中序遍历左子树，然后访问根结点，最后中序遍历根的右子树。对于根的左子树和右子树，遍历的过程相同。
方案一：递归
- 采用递归的方式来实现：
//中序遍历二叉树:递归实现
void InOrderTraverse(BiTree root) {if (root) {InOrderTraverse(root->lchild);printf("%d ", root->data);InOrderTraverse(root->rchild);}
}
方案二：非递归
- 非递归实现：引入辅助栈
//中序遍历二叉树:非递归实现
void