本文共 5465 字，大约阅读时间需要 18 分钟。

学习目标：二叉树的创建与遍历

学习内容

1.创建二叉链数

学习时间

1、 周一至周五晚上 7 点—晚上9点

学习记录

其实对于一个用链式结构构成的数据结构来说，树和链表其实有很大的相似之处，链表不过是在结构体中定义了自己的数据部分和指针部分，数据部分用来存储数据，指针部分用来存储下一个节点的地址，然后就可以通过给结构体对象开辟空间的办法来创建节点，通过将指针部分指向下一个节点的办法来创建连接。

树不过是比链表多了一个需要连接下一个节点的指针部分而已，俗称:“左孩子”，“右孩子”，其实很多人不理解的根本是递归，树基于递归实现是看起来很繁琐(用迭代打出来的代码更繁琐)。但是仔细想想不过就是每一次创建出孩子节点后，就到这个孩子节点这个地方，将孩子节点作为父节点再次进行其孩子节点的遍历和创建，当走到其叶子节点(即二叉树末尾节点的时候)，就将叶子节点的左右指针都赋值为NULL，而由于遍历到NULL使得递归函数进行往回递归，也就是一层一层的return出去。

摘自luolvzhou《二叉树的创建与遍历》

源代码

一、二叉树的创建

#include
   
    using namespace std;template
    
     struct BTNode{   	T data;	BTNode* left;	BTNode* right;	BTNode(const T& item=T(), BTNode
     
      * lptr = NULL, BTNode
      
       * rptr = NULL):data(item),left(lptr),right(rptr){   }};template
       
        BTNode
        
         * GetBTNode(const T& item, BTNode
         
          * lp = NULL, BTNode
          
           * rp = NULL){ BTNode
           
            * p; p = new BTNode
            
             (item, lp, rp); if (p == NULL) { cerr << "Merry allocation failure" << endl; exit(1); } //cout << p->data << endl; return(p);}
            
           
          
         
        
       
      
     
    
   

二、七种遍历

（1）层次遍历

//层次遍历1 出队之后访问template
   
    void Level1(const BTNode
    
     * t){   	if (t == NULL)	{   		return;	}	queue
     
      *> Q;	Q.push(t);	while (!Q.empty())	{   		t = Q.front();//访问队首元素		Q.pop();//弹出队列第一个元素		cout << t->data << endl;		if (t->left)		{   			Q.push(t->left);			//cout << "left" << endl;		}		if (t->right)		{   			Q.push(t->right);			//cout << "right" << endl;		}	}}//层次遍历2 入队之前访问template
      
       void Level2(const BTNode
       
         *p){   	if (p == NULL)		return;	queue
        
         *>q; cout << p->data<
         
          left) { q.push(p->left); cout << p->left->data<
          
           right) { q.push(p->right); cout << p->right->data<
          
         
        
       
      
     
    
   

（2）前序遍历递归算法

//前序遍历递归算法template
   
    void Preorder(const BTNode
    
     * t){   	if (t == NULL)		return;	cout << t->data;	if (t->left)		Preorder(t->left);	if (t->right)		Preorder(t->right);}
    
   

（3）前序遍历非递归算法（栈内存）

template
   
    void SimPreorder(const BTNode
    
      *t){   	if (!t)		return;	stack
     
      *> s; // 建立一个s栈	while (t || !s.empty())	{   		if (t)		{   			cout << t->data;			cout << endl;			if (t->right)				s.push(t->right);			t=t->left;		}		else		{   			t = s.top();			s.pop();		}	}}
     
    
   

（4）中序遍历递归算法

template
   
    void Inorder(const BTNode
    
     *t){   	if (!t)		return;	if (t->left)		Inorder(t->left);	cout << t->data;	if (t->right)		Inorder(t->right);}
    
   

（5）中序遍历非递归算法

template
   
    void Simorder(const BTNode
    
     * t){   	if (!t)		return;	stack
     
      *>s;	while (t || !s.empty())	{   		if (t)		{   			s.push(t);			t = t->left;		}		else		{   			t = s.pop();			cout << t->data;			t = t->right;		}	}}
     
    
   

（6）后序遍历递归算法

template
   
    void Postorder(const BTNode
    
     * t){   	if (!t)		return;	if (t->left)		Postorder(const BTNode
     
       * t);	if (t->right)		Postorder(const BTNode
      
        * t);}
      
     
    
   

（7）后序遍历非递归算法

template
   
    void SimPostorder(const BTNode
    
     * t){   	if (!t)		return;	int tag;	stack
     
      *>S;	stack
      
       tagS;	const BTNode
       
        * temp;	while (t || !S.empty())	{   		if (t)		{   			S.push(t); tagS.push(1);			t = t->left;		}		else		{   			tamp = S.pop(); tag = tagS.pop();			if (tag == 1)			{   				S.push(temp); tagS.push(2);				t = temp->right;			}			else				cout << temp->data;		}	}}
       
      
     
    
   

三、垂直输出二叉树

在这里插入代码片///二叉树的垂直输出struct location{   	int x, y;};void Gotoxy(int x, int y){   	static int indent=0, level=0;	if (y == 0)	{   		indent = 0; level =0;	}	if (level != y)	{   		cout << endl;		level++; indent = 0;	}	cout.width(x - indent);	indent = x;}template
   
    void PrintBTree(const BTNode
    
     * t, int screenwidth){   	if (t == NULL)		return;	int level = 0, offset = screenwidth / 2;	location f, c;	queue
     
      *>q;	queue
      
        lq;	f.x = offset;	f.y = level;	q.push(t);	lq.push(f);	while (!q.empty())	{   		t = q.front();		q.pop();		f = lq.front();		lq.pop();		Gotoxy(f.x, f.y);		cout << t->data;		if (f.y != level)		{   			level++;			offset = offset / 2;		}		if (t->left)		{   			q.push(t->left);			c.x = f.x - offset/2;			c.y = f.y + 1;						lq.push(c);		}		if (t->right)		{   			q.push(t->right);			c.x = f.x + offset/2;			c.y = f.y + 1;			lq.push(c);		}	}	cout << endl;}
      
     
    
   

四、汉诺塔

void Hanoi(int n, char A, char B, char C){   	if (n <= 0)		return;	else if (n == 1)	{   		cout << A <<"->"<< C << endl;// "A->C" << endl;	}	else	{   		Hanoi(n - 1, A, C, B);		cout << A <<"->"<< C << endl;// "A->B" << endl;		Hanoi(n - 1, B, A, C);	}}

五、主函数

int main(){   	BTNode
   
    * nullp = NULL;	//注意这里定义空结点的时候不能写成BTNode
    
     *nullp=GetNode(NULL);	//不然生成的是值域为0的空结点	BTNode
     
      * g = GetBTNode(7);	BTNode
      
       * f = GetBTNode(6);	BTNode
       
        * e = GetBTNode(5);	BTNode
        
         * d = GetBTNode(4, g); BTNode
         
          * b = GetBTNode(2, nullp, d); BTNode
          
           * c = GetBTNode(3, e, f); BTNode
           
            * a = GetBTNode(1, b, c); cout << endl << endl; cout << "层次遍历1" << endl; Level1(a); cout << endl << endl; cout << "层次遍历2" << endl; Level2(a); cout << endl << endl; cout << "前序遍历递归算法" << endl; Preorder(a); cout << endl << endl; cout << "前序遍历非递归算法" << endl; SimPreorder(a); cout << endl << endl; cout << "中序遍历递归算法" << endl; Inorder(a); cout << endl << endl; cout << "中序遍历非递归算法" << endl; Simorder(a); cout << endl<
           
          
         
        
       
      
     
    
   

错误的输出：如下图