[数据结构与算法]二叉树遍历——先序遍历

二叉树遍历——先序遍历

遍历顺序如下图：依次遍历左孩子,到头了就转向右孩子

#include<iostream>
#include<stack>
using namespace std;

//排序二叉树有如下性质
//若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
//若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
//左、右子树也分别为二叉排序树

struct BT//定义一个BT结构的节点,每一个BT结构的节点都具有val值,和指向组偶有孩子的指针
{
	int val;
	BT* left;//左指针
	BT* right;//右指针
	
};
struct Tree//定义一个树结构，每个树都有BT类型的节点指向的根
{
	BT *root;
};

void insert(Tree* tree, int val)//形参为指向tree的指针
{
	BT* temp, *newnode;
	newnode = new BT;//为newnode开辟一个新的BT空间
	newnode->val = val;
	newnode->right = NULL;//初始化为一个空
	newnode->left = NULL;//
	if (tree->root==NULL)//如果现在的树为空的树，当前的点为根
	{
		tree->root = newnode;
	}
	else
	{
		temp = tree->root;//temp从根节点开始判断要插入的位置,将当前值与temp值比较，
		while (NULL != temp)//若大于temp，则判断temp的右儿子存不存在，存在就重新赋值temp，继续进行比较
		{
			if (temp->val<newnode->val)
			{
				if (temp->right==NULL)
				{
					temp->right = newnode;
					return;
				}
				else
				{
					temp = temp->right;
				}
			}
			else
			{
				if (temp->left == NULL)
				{
					temp->left = newnode;
					return;
				}
				else
				{
					temp = temp->left;
				}
			}
		}
	}
}

//先序访问
void preorder(BT* ptr)//先序访问 ， 根左右，即先访问根节点，再访问左结点，最后访问右结点
{
	if (ptr != NULL)//递归调用→转化为迭代形式
	{
		std::cout << ptr->val << " ";
		preorder(ptr->left);    
		preorder(ptr->right);
	}
}
//先序访问，迭代实现
void preorder_1(BT* ptr)//参数为根结点
{
	stack<BT*>s;//辅助栈
	s.push(ptr);
	while (!s.empty())
	{
		BT* current;
		current = s.top();
		std::cout << "当前结点的值为： " << current->val << endl;//访问当前值
		s.pop();//弹出
		if(current->right!=NULL)s.push(current->right);
		if (current->left != NULL)s.push(current->left);
	}
}
//新迭代算法leftbranch
void leftbranch(BT* ptr, stack<BT*>&s)
{
	BT* current = ptr;
	
	while (current!=NULL)
	{
		std::cout <<"当前节点为：  " <<current->val;
		if (current->right != NULL)s.push(current->right);
		current = current->left;
	}
}
void preorder_2(BT* ptr)
{
	BT* current = ptr;
	stack<BT*>st;
	while (true)
	{
		leftbranch(current, st);
		if (st.empty())break;
		current = st.top();
		st.pop();
	}
}

int main()
{
	Tree tree;//定义一个类型为Tree的tree

	BT* b1 = new BT;//由于树的根结点为指向BT的指针，故需要
	b1->val =10;
	b1->left = new BT;
	b1->left->val = 9;
	b1->left->left = NULL;
	b1->left->right = NULL;
	b1->right = new BT;
	b1->right->val = 11;
	b1->right->left = NULL;
	b1->right->right = NULL;

	tree.root = b1;
	preorder(tree.root);
	std::cout << endl;        

	Tree* to_tree = &tree;
	insert(to_tree, 20);
	insert(to_tree, 7);
	insert(to_tree, 10);
	insert(to_tree, 34);
	insert(to_tree, 13);

	preorder_1(tree.root);
	std::cout << endl;
	preorder_2(tree.root);
	std::cout << endl;

	
	system("pause");
	return 0;
}