数据结构-二叉树操作实践

建立二叉树的二叉链表

#include<iostream>
using namespace std;

#define MAXSIZE 50
// 二叉树的二叉链表存储表示
typedef struct BiTNode {
   
	char data;
	struct BiTNode* lchild, * rchild;  // 左右孩子指针
}BiTNode, *BiTree;

/** * 按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树， * 构造二叉链表表示的二叉树T * @param T [description] */
void CreateBiTree(BiTree& T) {
   
	char ch;
	ch = getchar();  // 输入回车结束输入，但要记得按照完整的二叉树的先序顺序输入
	if (ch == ' ')
		T = NULL;
	else {
   
		T = (BiTNode*)malloc(sizeof(BiTNode));
		if (T) {
   
			T->data = ch;  // 生成根节点
			CreateBiTree(T->lchild);  // 构造左子树
			CreateBiTree(T->rchild);  // 构造右子树
		}
	}
}

二叉树的先序递归遍历

/** * 先序递归遍历二叉树 * @param T 二叉树T */
void PreOrder(BiTree T) {
   
	if (T != NULL) {
   
		cout << T->data << " ";  // 访问根结点
		PreOrder(T->lchild);  // 遍历左子树
		PreOrder(T->rchild);  // 遍历右子树
	}
}

二叉树的中序递归遍历

/** * 中序递归遍历二叉树 * @param T 二叉树T */
void InOrder(BiTree T) {
   
	if (T != NULL) {
   
		InOrder(T->lchild);  // 遍历左子树
		cout << T->data << " ";  // 访问根结点
		InOrder(T->rchild);  // 遍历右子树
	}
}

二叉树的后序递归遍历

/** * 后序递归遍历二叉树 * @param T 二叉树T */
void PostOrder(BiTree T) {
   
	if (T != NULL) {
   
		PostOrder(T->lchild);  // 遍历左子树
		PostOrder(T->rchild);  // 遍历右子树
		cout << T->data << " ";  // 访问根结点
	}
}

二叉树的先序非递归遍历

/** * 先序遍历二叉树T的非递归算法 * @param T 二叉树T */
void PreOrderNoRecursion(BiTree T) {
   
	if (T != NULL) {
   
		BiTree Stack[MAXSIZE];  // 定义栈
		int top = -1;
		BiTNode* p = NULL;  // 定义遍历指针
		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;
		}
	}
}

二叉树的中序非递归遍历

/** * 中序遍历二叉树T的非递归算法 * @param T 二叉树T */
void InOrderNoRecursion(BiTree T) {
   
	if (T != NULL) {
   
		BiTree 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;
			}
		}
	}
}

二叉树的后序非递归遍历

/** * 后序遍历二叉树T的非递归算法 * @param T 二叉树T */
void PostOrderNoRecursion(BiTree T) {
   
	/** * 需要用到两个栈来实现，先把根入栈1，再把栈1的栈顶出栈，入栈到栈2，从栈1出栈时，将其左右孩子入栈1。重复。 * 再把栈2中的依次出栈即可。 */
	if (T != NULL) {
   
		BiTree Stack1[MAXSIZE];
		int top1 = -1;
		BiTree Stack2[MAXSIZE];
		int top2 = -1;
		BiTNode* p = T;
		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 << " ";
		}
	}
}

完整测试代码

#include<iostream>
using namespace std;

#define MAXSIZE 50
// 二叉树的二叉链表存储表示
typedef struct BiTNode {
   
	char data;
	struct BiTNode* lchild, * rchild;  // 左右孩子指针
}BiTNode, *BiTree;

/** * 按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树， * 构造二叉链表表示的二叉树T * @param T 二叉树T */
void CreateBiTree(BiTree& T) {
   
	char ch;
	ch = getchar();  // 输入回车结束输入，但要记得按照完整的二叉树的先序顺序输入

	if (ch == ' ')
		T = NULL;
	else {
   
		T = (BiTNode*)malloc(sizeof(BiTNode));
		if (T) {
   
			T->data = ch;  // 生成根节点
			CreateBiTree(T->lchild);  // 构造左子树
			CreateBiTree(T->rchild);  // 构造右子树
		}
	}

}

/** * 先序递归遍历二叉树 * @param T 二叉树T */
void PreOrder(BiTree T) {
   
	if (T != NULL) {
   
		cout << T->data << " ";  // 访问根结点
		PreOrder(T->lchild);  // 遍历左子树
		PreOrder(T->rchild);  // 遍历右子树
	}
}

/** * 中序递归遍历二叉树 * @param T 二叉树T */
void InOrder(BiTree T) {
   
	if (T != NULL) {
   
		InOrder(T->lchild);  // 遍历左子树
		cout << T->data << " ";  // 访问根结点
		InOrder(T->rchild);  // 遍历右子树
	}
}

/** * 后序递归遍历二叉树 * @param T 二叉树T */
void PostOrder(BiTree T) {
   
	if (T != NULL) {
   
		PostOrder(T->lchild);  // 遍历左子树
		PostOrder(T->rchild);  // 遍历右子树
		cout << T->data << " ";  // 访问根结点
	}
}

/** * 先序遍历二叉树T的非递归算法 * @param T 二叉树T */
void PreOrderNoRecursion(BiTree T) {
   
	if (T != NULL) {
   
		BiTree Stack[MAXSIZE];  // 定义栈
		int top = -1;
		BiTNode* p = NULL;  // 定义遍历指针
		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;
		}
	}
}

/** * 中序遍历二叉树T的非递归算法 * @param T 二叉树T */
void InOrderNoRecursion(BiTree T) {
   
	if (T != NULL) {
   
		BiTree 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;
			}
		}
	}
}

/** * 后序遍历二叉树T的非递归算法 * @param T 二叉树T */
void PostOrderNoRecursion(BiTree T) {
   
	/** * 需要用到两个栈来实现，先把根入栈1，再把栈1的栈顶出栈，入栈到栈2，从栈1出栈时，将其左右孩子入栈1。重复。 * 再把栈2中的依次出栈即可。 */
	if (T != NULL) {
   
		BiTree Stack1[MAXSIZE];
		int top1 = -1;
		BiTree Stack2[MAXSIZE];
		int top2 = -1;
		BiTNode* p = T;
		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 << " ";
		}
	}
}

int main() {
   
	BiTree T=NULL;

	CreateBiTree(T);

	cout << "先序递归遍历：";
	PreOrder(T);
	cout << endl;

	cout << "中序递归遍历：";
	InOrder(T);
	cout << endl;

	cout << "后序递归遍历：";
	PostOrder(T);
	cout << endl;

	cout << "先序非递归遍历：";
	PreOrderNoRecursion(T);
	cout << endl;

	cout << "中序非递归遍历：";
	InOrderNoRecursion(T);
	cout << endl;

	cout << "后序非递归遍历：";
	PostOrderNoRecursion(T);
	cout << endl;
	return 0;
}

注：

• 下列实例所对应的二叉树为：
  
• 以下实例按二叉树的先序遍历顺序输入。但是请注意，必须要输入完整的二叉树，即每个结点的左右为空时均要输入空格（这里以空格代表空结点）。
• 下面的输入为：ABC##DE#G##F###（#表示输入的是空格）。C和G的后面均有两个空格，因为C和G的左右孩子均为空，E的后面有一个空格，因为E的右孩子为空，F的后面有3个空格，因为F的左右孩子为空，并且A的右孩子为空，最后一个空格表示A的右孩子为空。
• 由于getchar()的特点，输入时可以一次性输入完，以回车键结束输入，递归时，gechar()会每次从缓存中读取一个字符。
  

创作不易，喜欢的话加个关注点个赞，谢谢谢谢谢谢！