【二叉树】前序遍历创建二叉树 C++

1. 树结点

typedef struct treeNode* BT;
struct treeNode {
	int val;
	treeNode* left;
	treeNode* right;
};

2. 创建二叉树

BT createTree() {
	int data = 0;
	BT root;
	cin >> data;
	if (data == -1) {
		return nullptr;
	}
	root = new treeNode;
	root->val = data;
	root->left = createTree();
	root->right = createTree();
	return root;
}

3. 创建二叉树的另一种写法

void createTree(BT& root) {//以引用的方式传递指针
//不直接BT root传递的原因是 这里函数没有返回值，所以需要对参数进行地址传递，才能将传入的结点与创建的树连接起来
	cout << "请输入数据" << endl;
	int data = 0;
	cin >> data;
	if (data == -1) {
		root=nullptr;//val为-1，则无需创建结点
		return;
	}
	else {
		root = new treeNode;
		root->val = data;
		createTree(root->left);
		createTree(root->right);
	}
}

4. 前序遍历

void preOrder(BT root) {
	if (root) {
		cout << root->val << " ";
		preOrder(root->left);
		preOrder(root->right);
	}
}

5. 中序遍历

void inOrder(BT root) {
	if (root) {
		inOrder(root->left);
		cout << root->val << " ";
		inOrder(root->right);
	}
}

6. 主函数
   int main() {
   BT root;
   //root = createTree();
   createTree();//两种创建树的函数可以写到一个文件里，发生函数重载
   cout << “前序遍历” << endl;
   preOrder(root);
   cout << endl;
   cout << “中序遍历” << endl;
   inOrder(root);
   return 0;
   }
7. 实例
   2 ，3，6，-1，-1，4，-1，-1，1，5，-1，-1，2，-1，-1
   层序遍历的结果是2,3,1,6,4,5,2