- 二叉链表的节点存储结构
由一个数据域和两个指针域组成。指针域分别存放指向左孩子和右孩子的指针。
struct TreeNode
{
int val;
struct TreeNode *left;
struct TreeNode *right;
};
结构示意图
- 二叉树的建立
我们要在内存建立一个如图所示的树，为了能让每个结点确认是否有左右孩子，对它进行扩展变成图2左图的样子，也就是将二叉树中每个结点的空指针引出一个虚结点，其值为特定值比如:#或0.我们称这种处理后的二叉树为原二叉树的扩展二叉树。扩展二叉树就可以做到一个遍历序列确定一颗二叉树了。如图2左图的前序遍历就为AB#D##C##
image.png
这样就可以把前序遍历AB#D##C##用键盘挨个输入。实现的算法如下:
struct TreeNode *create(struct TreeNode *tree)
{
int ch ;
scanf("%d",&ch);
if(ch == '#')
{
tree = NULL;
}
else
{
tree = new struct TreeNode;
//tree = (TreeNode *)calloc(1,sizeof(TreeNode));
tree->val = ch;
tree->left = create(tree->left);
tree->right= create(tree->right);
}
return tree;
}
- 细节说明
- 代码中的tree都应该是结点，也就是一个结构体结点。因为我用linux下的c++环境编译执行，不需要对其进行特别的强调。但是在c环境中需要对所有tree做struct关键字说明强调该结点是定义一个结构体结点，而不是一个指针类型。为了保险起见，我把代码中加入struct关键字。
- 递归过程中为每个新加入的数据开辟内存空间的方法：
可以用new分配如 tree = new struct TreeNode,
也可以使用calloc方式分配内存
tree = (TreeNode *)calloc(1,sizeof(TreeNode))
3)使用scanf输入数据时，需要注意:在一行输入，每个字符中间空格A B # D # # C # #，最后回车。
也可以把字符放入一个数组中，然后再函数中不断让数组下标加一取值。需要定义一个index_1,(因为index和包中某个命名冲突，故我们命名为index_1),该变量必须放在函数外面。
char chars_tree[] = "AB#D##C##";
int index_1 = 0;
TreeNode *create(TreeNode *tree)
{
char ch = chars_tree[index_1++];
if(ch == '#')
{
tree = NULL;
}
else
{
tree = new TreeNode;
tree->val = ch;
tree->left = create(tree->left);
tree->right= create(tree->right);
}
return tree;
}
- 详细分析构造二叉树的过程
1)index_1=0即取第一个字符A，A不等于#，执行else操作。开辟结构体结点空间，把字符A赋值给结点的数据域，递归进入A结点的左子树，递归开始。
- index_1=1即取第二个字符B，B不等于#，执行else操作。开辟结构体结点空间，把字符B赋值给结点的数据域，递归进入B结点的左子树。
- index_1=2即取第三个字符#，#等于#，执行tree = NULL操作即该结点为空。跳过else，直接return该结点即B结点无左子树。跳出tree->left = create(tree->left)该语句。进入下一条语句，找B结点的右子树。
- index_1=3即取第4个字符D，D不等于#，执行else操作。开辟结构体结点空间，把字符D赋值给结点的数据域，递归进入D结点的左子树。
- index_1=4即取第5个字符#，#等于#，执行tree = NULL操作即该结点为空。跳过else，直接return该结点，即D结点无左子树。跳出tree->left = create(tree->left)该语句。进入下一条语句，找D结点的右子树。
- index_1=5即取第6个字符#，#等于#，执行tree = NULL操作即该结点为空。跳过else，即D结点无右子树，直接return该空结点，跳出tree->right= create(tree->right)语句。返回D结点，D结点遍历完毕返回B结点，B结点遍历完毕，返回A结点,进入A结点的右子树。
- index_1=6即取第7个字符C，C不等于#，执行else操作。开辟结构体结点空间，把字符C赋值给结点的数据域，递归进入C结点的左子树。
- index_1=7即取第8个字符#，#等于#，执行tree = NULL操作即该结点为空。跳过else，直接return该结点，即C结点无左子树。跳出tree->left = create(tree->left)该语句。进入下一条语句，找C结点的右子树。
- index_1=8即取第9个字符#，#等于#，执行tree = NULL操作即该结点为空。跳过else，直接return该结点，即C结点无右子树。跳出tree->right= create(tree->right);该语句。执行完毕。
赋完整版代码
- 说明二叉树的结构为1,2,4,0,0,0,3,0,0，空结点用0代替。构建该二叉树并先序输出。
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
using namespace std;
struct TreeNode
{
int val;
TreeNode *left;
TreeNode *right;
};
int array_tree[] = {1,2,4,0,0,0,3,0,0};
int index_1 = 0;
TreeNode *create(TreeNode *tree)
{
int ch = array_tree[index_1++];
if(ch == 0)
{
tree = NULL;
}
else
{
tree = new TreeNode;
//tree = (TreeNode *)calloc(1,sizeof(TreeNode));
tree->val = ch;
tree->left = create(tree->left);
tree->right= create(tree->right);
}
return tree;
}
void preOrder(TreeNode *tree)
{
if(tree)
{
cout << tree->val <<" ";
preOrder(tree->left);
preOrder(tree->right);
}
}
int main()
{
TreeNode *tree = NULL;
tree = create(tree);
cout << "前序输出:" << endl;
preOrder(tree);
cout<<endl;
}
