二叉树（创建、遍历）<递归、非递归>

表示形式：链式结构

代码如下：

递归算法：

#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
 
using namespace std;
 
typedef int Status;
typedef char TElemType;
typedef struct BiTNode
{
	TElemType data;
	struct BiTNode *lchild, *rchild;
}BiTNode,*BiTree;
 
int Nodenum = 0;
int Count = 0;
 
Status CreateBiTree(BiTree &T)
{
	char ch;
	cin >> ch;
	if (ch == '#')
		T = NULL;
	else
	{
		if (!(T = (BiTNode *)malloc(sizeof(BiTNode))))
			exit(OVERFLOW);
		T->data = ch;
		CreateBiTree(T->lchild);
		CreateBiTree(T->rchild);
	}
	return OK;
 
}
 
Status PreOrderTraverse(BiTree T)
{
	if (T)
	{
		printf("%c", T->data);
		if (PreOrderTraverse(T->lchild))
			if (PreOrderTraverse(T->rchild))
				return OK;
		return ERROR;
	}
	else
		return OK;
}
 
Status InOrderTraverse(BiTree T)
{
	int m = 0;
	if (T)
	{
		if (InOrderTraverse(T->lchild))
			m = 1;
		cout << T->data;
		if (m)
			if (InOrderTraverse(T->rchild))
				return OK;
		return ERROR;
	}
	else
		return OK;
}
 
Status PostOrderTraverse(BiTree T)
{
	if (T)
	{
		if (PostOrderTraverse(T->lchild))
			if (PostOrderTraverse(T->rchild))
			{
				cout << T->data;
				return OK;
			}
		return ERROR;
 
	}
	else
		return OK;
}
 
Status NodeCount(BiTree T)
{
	if (T)
	{
		Nodenum++;
		if (NodeCount(T->lchild))
			if (NodeCount(T->rchild))
				return OK;
		return ERROR;
 
	}
	else
		return OK;
}
 
Status LeafCount(BiTree T)
{
	if (T)
	{
		if (T->lchild == NULL&&T->rchild == NULL)
		{
			cout << T->data;
			Count++;
		}
		if (LeafCount(T->lchild))
			if (LeafCount(T->rchild))
				return OK;
		return ERROR;
	}
	else
		return OK;
}
 
/*
交换二叉树中所有节点的左右子树
*/
Status ExchangeBiTree(BiTree &T)
{
	BiTree p;
	if (T)
	{
		if (T->lchild || T->rchild) {
			p = T->lchild;
			T->lchild = T->rchild;
			T->rchild = p;
		}
		if (ExchangeBiTree(T->lchild))
			if (ExchangeBiTree(T->rchild))
				return OK;
		return ERROR;
	}
	else
		return OK;
}
 
Status CopyBiTree(BiTree T, BiTree &B)
{
	if (T == NULL)
		B = NULL;
	else
	{
		if (!(B = (BiTNode *)malloc(sizeof(BiTNode))))
			exit(OVERFLOW);
		B->data = T->data;
		CopyBiTree(T->lchild, B->lchild);
		CopyBiTree(T->rchild, B->rchild);
	}
	return OK;
}
 
Status DestroyTree(BiTree &T)
{
	if (T)
	{
		DestroyTree(T->lchild);
		DestroyTree(T->rchild);
		free(T);
	}
	return OK;
}
 
Status ClearTree(BiTree &T)
{
	if (T)
	{
		T = NULL;
	}
	return OK;
}
 
int Depth(BiTree T)
{
	int leftDepth, rightDepth;
	if (T == NULL)
		return 0;
	else
	{
		leftDepth = Depth(T->lchild);
		rightDepth = Depth(T->rchild);
		if (leftDepth >= rightDepth)
			return leftDepth + 1;
		else
			return rightDepth + 1;
	}
}
 
void main()
{
	BiTree T, B;
	cout << "创建二叉树，按先序次序输入二叉树中结点的值：" << endl;
	CreateBiTree(T);
	NodeCount(T);
	cout << "二叉树的结点个数为" << Nodenum << endl;
	cout << "二叉树的深度为：" << Depth(T) << endl;
	cout << "先序遍历二叉树，结果是：" << endl;
	PreOrderTraverse(T);
	cout << endl;
	cout << "中序遍历二叉树，结果是：" << endl;
	InOrderTraverse(T);
	cout << endl;
	cout << "后序遍历二叉树，结果是：" << endl;
	PostOrderTraverse(T);
	cout << endl;
	cout << "输出二叉树的叶子结点：" << endl;
	LeafCount(T);
	cout << endl;
	cout << "统计二叉树的叶子结点个数：" << Count << endl;
	cout << "交换二叉树中所有节点的左右子树！" << endl;
	ExchangeBiTree(T);
	if (CopyBiTree(T, B) == OK)
		cout << "成功复制二叉树T到二叉树B" << endl;
	if (DestroyTree(T) == OK)
		cout << "成功销毁二叉树T！" << endl;
	if (ClearTree(T) == OK)
		cout << "成功将二叉树T置为空树！" << endl;
	cout << "先序遍历二叉树B，结果是：" << endl;
	PreOrderTraverse(B);
	cout << endl;
	cout << "中序遍历二叉树B，结果是：" << endl;
	InOrderTraverse(B);
	cout << endl;
	cout << "后序遍历二叉树B，结果是：" << endl;
	PostOrderTraverse(B);
	cout << endl;
	system("pause");
}

非递归算法：

#include<stdio.h>
#include<iostream>
#include<stdlib.h>
 
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define maxSize 50
using namespace std;
 
typedef int Status;
typedef char TElemType;
typedef struct BiTNode
{
	TElemType data;
	struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
 
int Nodenum = 0;
int Count = 0;//二叉树叶子结点统计
 
BiTree CreateBiTree()
{
	TElemType ch[maxSize];
	cin >> ch;
	int len = (int)strlen(ch);
	BiTree stack[maxSize];
	int top = -1;
	int i = 0;
	if (ch[i] == 0)
		return NULL;
	BiTree temp;
	BiTree root = new BiTNode();
	root->data = ch[i];
	root->lchild = NULL;
	root->rchild = NULL;
	stack[++top] = root;//根节点入栈
	i++;
	int flag = 1;//标志位：第一种情况：创建左孩子；2：创建右孩子；3：左右孩子均创建，出栈
	while (i < len)
	{
		BiTree pNew = NULL;
		if (flag == 1)//创建左孩子
		{
			/*
			'#'说明这是栈顶结点无左孩子，把标志位置2，判断右孩子
			*/
			if (ch[i] == '#')
			{
				
				flag = 2;
			}
			else
			{
				pNew = new BiTNode();
				pNew->data = ch[i];
				pNew->lchild = NULL;
				pNew->rchild = NULL;
 
				temp = stack[top];//取出当前栈顶
				temp->lchild = pNew;//当前结点为栈顶结点的左孩子
				stack[++top] = pNew;//当前结点入栈
				flag = 1;//使标志位初始化
			}
		}
		else if (flag == 2)//创建右孩子
		{
			/*
			栈顶结点无右孩子
			*/
			if (ch[i] == '#')
			{
				
				flag = 3;
			}
			else
			{
				/*
				与创建左孩子同理
				*/
				pNew = new BiTNode();
				pNew->data = ch[i];
				pNew->lchild = NULL;
				pNew->rchild = NULL;
 
				temp = stack[top];
				temp->rchild = pNew;
				stack[++top] = pNew;
				flag = 1;//置1继续判断结点的左孩子（左孩子优先）
			}
		}
		else//左右孩子都创建
		{
			temp = stack[top--];
			while (top > 0 && stack[top]->rchild == temp)
				--top;
 
			flag = 2;
			--i;
		}
		++i;
	}
	return root;
}
/*
先序遍历非递归算法
*/
void PreOrderTraverse(BiTree T)
{
	if (T)
	{
		BiTNode *Stack[maxSize];
		int top = -1;
		BiTNode *p;
		Stack[++top] = T;
		while (top != -1)
		{
			p = Stack[top--];
			cout << p->data;
			if (p->rchild != NULL)
				Stack[++top] = p->rchild;
			if (p->lchild != NULL)
				Stack[++top] = p->lchild;
		}
	}
}
/*
中序遍历的非递归算法
*/
void InOrderTraverse(BiTree T)
{
	
	if (T)
	{
		BiTNode *Stack[maxSize];
		int top = -1;
		BiTNode *p = T;
		while (top != -1 || p != NULL)
		{
			while (p != NULL)
			{
				Stack[++top] = p;
				p = p->lchild;
			}
			if (top != -1)
			{
				p = Stack[top--];
				cout << p->data;
				p = p->rchild;
			}
		}
	}	
}
 
/*
后序遍历的非递归算法
*/
 
void PostOrderTraverse(BiTree T)
{
	if (T)
	{
		BiTNode *Stack1[maxSize];
		int top1 = -1;
		BiTNode *Stack2[maxSize];
		int top2 = -1;
		BiTNode *p = NULL;
		Stack1[++top1] = T;
		while (top1 != -1)
		{
			p = Stack1[top1--];
			Stack2[++top2] = p;
			if (p->lchild!=NULL)
				Stack1[++top1] = p->lchild;
			if (p->rchild != NULL)
				Stack1[++top1] = p->rchild;
		}
		while (top2 != -1)
		{
			p = Stack2[top2--];
			cout << p->data;
		}
	}
	
}
/*
层次遍历非递归算法
*/
void level(BiTree T)
{
	int front, rear;
	BiTNode *queue[maxSize];//队列先进先出
	front = rear = 0;
	BiTNode *q;
	if (T != NULL)
	{
		rear = (rear + 1) % maxSize;//循环队列，避免越界
		queue[rear] = T;//首节点结点插入队尾
		while (front != rear)//说明队列中尚有结点
		{
			front = (front + 1) % maxSize;//避免越界
			q = queue[front];//队头结点出队
			cout << q->data;
			/*
			判断左右孩子，左孩子先进队列
			*/
			if (q->lchild != NULL)
			{
				rear = (rear + 1) % maxSize;
				queue[rear] = q->lchild;
			}
			if (q->rchild != NULL)
			{
				rear = (rear + 1) % maxSize;
				queue[rear] = q->rchild;
			}
		}
	}
 
}
 
Status NodeCount(BiTree T)
{
	if (T)
	{
		Nodenum++;
		if (NodeCount(T->lchild))
			if (NodeCount(T->rchild))
				return OK;
		return ERROR;
 
	}
	else
		return OK;
}
/*
   原理和层次遍历相同，稍作修改加个判断条件：
       此结点左右孩子是否为空，是则输出，不是则判断下一个
*/
void LeafCount(BiTree T)
{
	int front, rear;
	BiTNode *queue[maxSize];//队列先进先出
	front = rear = 0;
	BiTNode *q;
	if (T != NULL)
	{
		rear = (rear + 1) % maxSize;//循环队列，避免越界
		queue[rear] = T;//首节点结点插入队尾
		while (front != rear)//说明队列中尚有结点
		{
			front = (front + 1) % maxSize;//避免越界
			q = queue[front];//队头结点出队
			/*
			判断左右孩子，左孩子先进队列
			*/
			if (q->lchild != NULL)
			{
				rear = (rear + 1) % maxSize;
				queue[rear] = q->lchild;
			}
			if (q->rchild != NULL)
			{
				rear = (rear + 1) % maxSize;
				queue[rear] = q->rchild;
			}
			if (q->lchild == NULL&&q->rchild == NULL)
			{
				cout << q->data;
				Count++;
			}
		}
	}
}
 
/*
交换二叉树中所有节点的左右子树:
(非递归）
     第一步：层次遍历：入队列
	 第二步：交换每个结点的左右子树
*/
void ExchangeBiTree(BiTree &T)
{
	if (T)
	{
		BiTNode *temp;
		BiTNode *p;
		int front, rear;
		front = rear = 0;
		BiTNode *queue[maxSize];
		if (T != NULL)
		{
			rear = (rear + 1) % maxSize;//循环队列，避免越界
			queue[rear] = T;//首节点结点插入队尾
			while (front != rear)//说明队列中尚有结点
			{
				front = (front + 1) % maxSize;//避免越界
				p = queue[front];//队头结点出队
				/*
				判断左右孩子，左右孩子进队列
				*/
				if (p->lchild != NULL)
				{
					rear = (rear + 1) % maxSize;
					queue[rear] = p->lchild;
				}
				if (p->rchild != NULL)
				{
					rear = (rear + 1) % maxSize;
					queue[rear] = p->rchild;
				}
 
				temp = p->lchild;
				p->lchild = p->rchild;
				p->rchild = temp;
			}
		}
	}
}
 
Status CopyBiTree(BiTree T, BiTree &B)
{
	if (T == NULL)
		B = NULL;
	else
	{
		if (!(B = (BiTNode *)malloc(sizeof(BiTNode))))
			exit(OVERFLOW);
		B->data = T->data;
		CopyBiTree(T->lchild, B->lchild);
		CopyBiTree(T->rchild, B->rchild);
	}
	return OK;
}
/*
    销毁二叉树
*/
Status DestroyTree(BiTree &T)
{
	if (T)
	{
		DestroyTree(T->lchild);
		DestroyTree(T->rchild);
		free(T);
	}
	return OK;
}
/*
   清空二叉树
*/
Status ClearTree(BiTree &T)
{
	if (T)
	{
		T = NULL;
	}
	return OK;
}
/*
   求二叉树的深度(非递归算法）：（层次遍历）
*/
int Depth(BiTree T)
{
	int level = 0;//层次
	if (T)
	{
		int front = 0, rear = 0;
	BiTNode *Queue[maxSize]; 
	Queue[rear++] = T;
	
			
	while (front!=rear)
	{
		int len = rear - front;
		level++;
		while (len--)
		{
			BiTNode *temp = Queue[front];
			front++;
			if (temp->lchild)
				Queue[rear++] = temp->lchild;
			if (temp->rchild)
				Queue[rear++] = temp->rchild;
		}
	}					
	}
 
 
	return level;
}
 
void main()
{
	BiTree T, B;
	cout << "创建二叉树，按先序次序输入二叉树中结点的值：" << endl;
	T=CreateBiTree();
	NodeCount(T);
	cout << "二叉树的结点个数为" << Nodenum << endl;
	cout << "二叉树的深度为：" << Depth(T) << endl;
	cout << "先序遍历二叉树，结果是：" << endl;
	PreOrderTraverse(T);
	cout << endl;
	cout << "中序遍历二叉树，结果是：" << endl;
	InOrderTraverse(T);
	cout << endl;
	cout << "后序遍历二叉树，结果是：" << endl;
	PostOrderTraverse(T);
	cout << endl;
	cout << "层次遍历二叉树，结果是：" << endl;
	level(T);
	cout << endl;
	cout << "输出二叉树的叶子结点：" << endl;
	LeafCount(T);
	cout << endl;
	cout << "统计二叉树的叶子结点个数：" << Count << endl;
	cout << "交换二叉树中所有节点的左右子树！" << endl;
	ExchangeBiTree(T);
	if (CopyBiTree(T, B) == OK)
		cout << "成功复制二叉树T到二叉树B" << endl;
	if (DestroyTree(T) == OK)
		cout << "成功销毁二叉树T！" << endl;
	if (ClearTree(T) == OK)
		cout << "成功将二叉树T置为空树！" << endl;
	cout << "先序遍历二叉树B，结果是：" << endl;
	PreOrderTraverse(B);
	cout << endl;
	cout << "中序遍历二叉树B，结果是：" << endl;
	InOrderTraverse(B);
	cout << endl;
	cout << "后序遍历二叉树B，结果是：" << endl;
	PostOrderTraverse(B);
	cout << endl;
	system("pause");
}