//输出先序遍历中第k个节点的值
 int n =0;
 void Travel(BTNode *T, int k)
 {
      if(NULL != T)
      {
              if(++n == k)
              {
                     printf("第%d个节点的数据为:%c\n",k,T->data);
                     return ;
              }
              
              Travel(T->lchild,k);
              Travel(T->rchild,k);
              
      }
      
  
}   
 

 
 

 
 

 
 

 
 
//输出中序遍历中第k个节点的值
 int n =0;
 void Travel(BTNode *T, int k)
 {
      if(NULL != T)
      {
             
              Travel(T->lchild,k);
 

 
 
           if(++n == k)
              {
                     printf("第%d个节点的数据为:%c\n",k,T->data);
                     return ;
              }
              
              Travel(T->rchild,k);
              
      }
      
 }   
 
 

 
 

 
 

 
 

 
 
//输出后序遍历中第k个节点的值
 int n =0;
 void Travel(BTNode *T, int k)
 {
      if(NULL != T)
      {
            
              
              Travel(T->lchild,k);
              Travel(T->rchild,k);
 

 
 
           if(++n == k)
              {
                     printf("第%d个节点的数据为:%c\n",k,T->data);
                     return ;
              }
              
      }
      
 }   
 

 
文章目录
 
二叉树的定义
二叉树的特征
二叉搜索树
平衡二叉树
二叉树的重要性质
二叉树的创建
二叉树的先序遍历
二叉树的中序遍历
二叉树的后序遍历
二叉树的层序遍历
二叉树的深度
二叉树的节点数目
复制二叉树
二叉树叶子节点的数目
全部代码
测试结果
 

 
二叉树的定义
 
一个有穷的节点集合
 
二叉树的特征
 
每个节点最多只有两棵子树
每棵子树有左右之分，其次序不能颠倒，是有序数
 
二叉搜索树
 
定义：一棵二叉树，可以为空；如果不为空，满足以下性质：
 
非空左子树的所有值小于其根节点的键值
非空右子树的所有值大于其根节点的键值
左右子树都是搜索二叉树
 
平衡二叉树
 
空树或者任一节点左、右子树高度差的绝对值不超过1
 
二叉树的重要性质
 
在二叉树的第i层上至多有 2^(i-1)个节点
深度为k的二叉树上至多含有2^k-1(k>=1)个节点
对任意一棵二叉树，若它含有n0个叶子节点、n2个度为2的节点，则必存在n0 = n2+1
具有 n 个结点的完全二叉树的深度为 [ log2n]+1 ([ log2n]：表示以2为底，对n取对数，并向下取整）
若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点：
 (1) 若 i=1，则该结点是二叉树的根，无双亲；否则，编号为 [i/2] 的结点为其双亲结点；
 (2) 若 2i>n，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子结点；
 (3) 若 2i+1>n，则该结点无右孩子结点，否则，编号为2i+1 的结点为其右孩子结点。
 
二叉树的创建
 
Node * CreatBiTree() {
	//先序创建二叉树
	char ch;
	scanf("%c", &ch);
	if (ch=='#')
	{
		return NULL;
	}
	else {
		Node *T = (Node *)malloc(sizeof(Node));
		T->data = ch;
		T->lchild = CreatBiTree();
		T->rchild = CreatBiTree();
		return T;
	}
}

 
二叉树的先序遍历
 
void PreOrderTraverse(Node *T) {
	//先序遍历
	if (T)
	{
		printf("%2c ", T->data);
		PreOrderTraverse(T->lchild);
		PreOrderTraverse(T->rchild);
	}
}

 
二叉树的中序遍历
 
void MidOrderTraverse(Node *T) {
	//中序遍历
	if (T)
	{
		
		MidOrderTraverse(T->lchild);
		printf("%2c ", T->data);
		MidOrderTraverse(T->rchild);
	}
}

 
二叉树的后序遍历
 
void LaOrderTraverse(Node *T) {
	//后序遍历
	if (T)
	{

		LaOrderTraverse(T->lchild);
		LaOrderTraverse(T->rchild);
		printf("%2c ", T->data);
	}
}

 
二叉树的层序遍历
 
/**
层序遍历要结合队列的出队，入队来写*/
void LevelOrderTraversal(Queue *q, struct node *root) {
	//层次遍历，边进边出
	struct node *temp;
	Push(q, root);
	while (!empty(q))
	{
		temp = Pop(q);
		printf("%2c", temp->data);
		if (temp->lchild)
		{
			Push(q, temp->lchild);
		}
		if (temp->rchild)
		{
			Push(q, temp->rchild);
		}
	}

 
二叉树的深度
 
int countDepth(Node *t) {
	//求二叉树的深度
	if (t==NULL)
	{
		return 0;
	}
	else if (t->lchild == NULL && t->rchild == NULL) {
		return 1;
	}
	else {
		int depth1 = countDepth(t->lchild) ;
		int depth2 = countDepth(t->rchild) ;
		return depth1 > depth2 ? depth1 + 1 : depth2 + 1;
	}
}

 
二叉树的节点数目
 
int countNode(Queue *q, struct node *root) {
	//通过对队列的遍历求节点数目

	struct node *temp;
	Push(q, root);
	int num = 0;
	while (!empty(q))
	{
		temp = Pop(q);
		num++;
		if (temp->lchild)
		{
			Push(q, temp->lchild);
		}
		if (temp->rchild)
		{
			Push(q, temp->rchild);
		}
	}
	return num;
}



 
复制二叉树
 
//二叉树的复制
Node *CopyTree(Node *T) {
	Node *t = (Node *)malloc(sizeof(Node));
	if (T == NULL) {
		t = NULL;
		return t;
	}
	else {
		t->data = T->data;
		t->lchild = CopyTree(T->lchild);
		t->rchild = CopyTree(T->rchild);
		return t;
	}
}
 
二叉树叶子节点的数目
 
int CountLeaf(Node *t) {//叶子节点的数目
	static int num = 0;
	if (t == NULL) {
		return 0;
	}
	else {
		if (t->lchild==NULL&&t->rchild==NULL)
		{
			num++;
		}
		CountLeaf(t->lchild);
		CountLeaf(t->rchild);
	}
	return num;
}




//统计叶子节点
void CountLeaf(Node *T) {
	if (T == NULL) {
		return ;
	}

	else {
		if (T->lchild == NULL && T->rchild == NULL) {
			printf("%2c ", T->data);
		}
		CountLeaf(T->lchild);
		CountLeaf(T->rchild);
	}
}
 
全部代码
 
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<malloc.h>
#define max 100
typedef struct node {
	char data;
	struct node *lchild, *rchild;
}Node;
typedef struct queue {
	struct node * num[max];
	int front;
	int rear;
}Queue;
Queue * initilize() {
	Queue *q = (Queue*)malloc(sizeof(Queue));
	q->front = 0;
	q->rear = 0;
	return q;//初始化队列
}
void Push(Queue *q, struct node *root) {
	q->num[++q->rear] = root;//入队
}
struct node *Pop(Queue *q) {
	return q->num[++q->front];//出队
}
bool empty(Queue *q) {
	return q->front == q->rear;//判断队列是否为空
}
Node * CreatBiTree() {
	//先序创建二叉树
	char ch;
	scanf("%c", &ch);
	if (ch=='#')
	{
		return NULL;
	}
	else {
		Node *T = (Node *)malloc(sizeof(Node));
		T->data = ch;
		T->lchild = CreatBiTree();
		T->rchild = CreatBiTree();
		return T;
	}
}
void PreOrderTraverse(Node *T) {
	//先序遍历
	if (T)
	{
		printf("%2c ", T->data);
		PreOrderTraverse(T->lchild);
		PreOrderTraverse(T->rchild);
	}
}
void MidOrderTraverse(Node *T) {
	//中序遍历
	if (T)
	{
		
		MidOrderTraverse(T->lchild);
		printf("%2c ", T->data);
		MidOrderTraverse(T->rchild);
	}
}
void LaOrderTraverse(Node *T) {
	//后序遍历
	if (T)
	{

		LaOrderTraverse(T->lchild);
		LaOrderTraverse(T->rchild);
		printf("%2c ", T->data);
	}
}
void LevelOrderTraversal(Queue *q, struct node *root) {
	//层次遍历，边进边出
	struct node *temp;
	Push(q, root);
	while (!empty(q))
	{
		temp = Pop(q);
		printf("%2c", temp->data);
		if (temp->lchild)
		{
			Push(q, temp->lchild);
		}
		if (temp->rchild)
		{
			Push(q, temp->rchild);
		}
	}
}
int countDepth(Node *t) {
	//求二叉树的深度
	if (t==NULL)
	{
		return 0;
	}
	else if (t->lchild == NULL && t->rchild == NULL) {
		return 1;
	}
	else {
		int depth1 = countDepth(t->lchild) ;
		int depth2 = countDepth(t->rchild) ;
		return depth1 > depth2 ? depth1 + 1 : depth2 + 1;
	}
}
int countNode(Queue *q, struct node *root) {
	//通过对队列的遍历求节点数目

	struct node *temp;
	Push(q, root);
	int num = 0;
	while (!empty(q))
	{
		temp = Pop(q);
		num++;
		if (temp->lchild)
		{
			Push(q, temp->lchild);
		}
		if (temp->rchild)
		{
			Push(q, temp->rchild);
		}
	}
	return num;
}
int CountLeaf(Node *t) {//叶子节点的数目
	static int num = 0;
	if (t == NULL) {
		return 0;
	}
	else {
		if (t->lchild==NULL&&t->rchild==NULL)
		{
			num++;
		}
		CountLeaf(t->lchild);
		CountLeaf(t->rchild);
	}
	return num;
}
int main() {
	printf("先序遍历输入：");
	Node *T = CreatBiTree();
	printf("先序遍历输出：\n");
	PreOrderTraverse(T);
	printf("\n");
	printf("中序遍历输出：\n");
	MidOrderTraverse(T);
	printf("\n");
	printf("后序遍历输出：\n");
	LaOrderTraverse(T);
	printf("\n");
	printf("层次遍历输出：\n");
	Queue *q = initilize();
	LevelOrderTraversal(q, T);
	printf("\n");
	printf("树的深度为：%d\n", countDepth(T));
	printf("节点的数目为：%d\n", countNode(q,T));
	printf("叶子节点的数目为：%d\n", CountLeaf(T));
}


 
测试结果
 

本文主要分为两个部分：包括二叉树的构造和非递归后序遍历，都比较有参考价值，这里将思路整理出来。
 第一个部分主要是通过先序和中序构造二叉树，参考文章为https://blog.csdn.net/qq_35733751/article/details/80970664我觉得他的构造方式比较通用而且简洁，其实还有通过递归构造的方式我觉得比较麻烦，就没有采用。下为原理图：
 
 主要思想：1.找到pre数组中先序序列中的根节点并创建树的根节点；2.通过匹配in数组中中序序列中的根节点，找到先序和中序中分割点位置；3.分别递归构建左子树和右子树。
 
bitnode *createbt1(char*pre,char*in,int n){
	if(n<=0){
		return NULL;
	}
	if(pre==NULL||in==NULL){
		return NULL;
	}
	
	int k;
	bitnode *s=NULL;
	char*p=NULL;
	
	s=(bitnode*)malloc(sizeof(bitnode));
	s->data=*pre;
	
	for(p=in;p<in+n;p++)
	  if(*p==*pre)
	   break;
	k=p-in;
	
	s->lchild = createbt1(pre+1,in,k);
    s->rchild = createbt1(pre+k+1,p+1,n-k-1);
    return s;
}
 
第二部分为非递归遍历二叉树，访问序列为左-右-中，主要思想：1.将左孩子节点全部入栈；2.如果栈不为空且右孩子节点已被访问，出栈并访问该节点；3.找到栈顶元素遍历其右子树；4.循环上述过程直到栈为空；这里需要设置flag标记以访问过的变量，左孩子若被访问过标记0，右孩子若被访问过标记1。这里参考了：https://www.cnblogs.com/hicjiajia/archive/2010/08/27/1810055.html有兴趣可以进去看看。
 
void postorder(bitree T){
    bitree p;
	p=T;   
	stack s;
	inistack(s);
	int flag[50];
	while(p||!isempty(s)){
		while(p){
			push(s,p);
			flag[s.top]=0;
			p=p->lchild; 
		}
		while(!isempty(s)&&flag[s.top]==1){
		    pop(s,p);
			visit(p);
		}
        if(!isempty(s)){
        	flag[s.top]=1;
        	p=gettop(s);
        	p=p->rchild;
		}
		else break;
	}
}
 
以下附上完整代码，通过了Dev c++调试了：
 
#include <stdio.h>
#include <stdlib.h>
#define elemtype int 
typedef struct BiTNode{
	elemtype data;
	struct BiTNode *lchild,*rchild; 
}bitnode,*bitree;
//*********************创建二叉树************************
bitnode *createbt1(char*pre,char*in,int n){
	if(n<=0){
		return NULL;
	}
	if(pre==NULL||in==NULL){
		return NULL;
	}
	
	int k;
	bitnode *s=NULL;
	char*p=NULL;
	
	s=(bitnode*)malloc(sizeof(bitnode));
	s->data=*pre;
	
	for(p=in;p<in+n;p++)
	  if(*p==*pre)
	   break;
	k=p-in;
	
	s->lchild = createbt1(pre+1,in,k);
    s->rchild = createbt1(pre+k+1,p+1,n-k-1);
    return s;
}

//*********************非递归后序遍历二叉树************************

typedef struct {
	bitree data[50];
	int top;
}stack;

void inistack(stack &s){
	s.top=-1;
}

void push(stack &s,bitree p){
    if(s.top==49) return;
	s.data[++s.top]=p;
}

void pop(stack &s,bitree &p){
	if(s.top==-1) return;
	p=s.data[s.top--];
} 

void visit(bitree p){
	printf("%c\n",p->data);
}

bool isempty(stack s){
	if(s.top==-1){
		return 1;
	}else
	    return 0;
}

bitree gettop(stack s){
   if(s.top==-1)
     return false;
   bitree p;  
   p=s.data[s.top];
   return p;	
}

void postorder(bitree T){
    bitree p;
	p=T;   
	stack s;
	inistack(s);
	int flag[50];
	while(p||!isempty(s)){
		while(p){
			push(s,p);
			flag[s.top]=0;
			p=p->lchild; 
		}
		while(!isempty(s)&&flag[s.top]==1){
		    pop(s,p);
			visit(p);
		}
        if(!isempty(s)){
        	flag[s.top]=1;
        	p=gettop(s);
        	p=p->rchild;
		}
		else break;
	}
}

int main(){
  char pre[]={'a','b','d','g','c','e','f'};
  char in[]={'d','g','b','a','e','c','f'};
  bitree s=createbt1(pre,in,7);
  postorder(s);
}

1.题目：
 
 
 
 
 
 
  Problem Description
 
 
 
设有一棵二叉树，其节点值为字符型并假设各值互不相等，采用二叉链表存储表示。现输入其扩展二叉树的前序遍历序列，要求建立该二叉树，并输出其后序遍历序列的第k个结点值（假设该值一定存在）。
 
 
 
 
 
  Input
 
 
 第一行为一个整数n，表示以下有n组数据，每组数据占两行，第一行为一个整数k（1<=k<=二叉树中的结点总数），第二行为扩展二叉树的前序遍历序列。
 
 
 
 
  Output
 
 
 输出该二叉树后序遍历序列的第k个结点值。
 
 
 
 
  Sample Input
 
 
 
2
1
AB#D##C##
4
ABD##E##C#F##
 
 
 
 
 
  Sample Output
 
 
 
D
F
 
 

  
 

 
 
2.参考代码：
 
 
#include <iostream>
using namespace std;

char ans[1111];
int t;
struct BiNode{
	char data;
	BiNode* lchild,* rchild;
};

class BiTree{
private:
	BiNode* root;
	BiNode* Creat();
	void Release(BiNode* root);
public:
	BiTree();
	~BiTree();
	BiNode* GetRoot(){
		return root;
	}
	void PostOrder(BiNode* root);
};

BiNode* BiTree::Creat(){
	BiNode* root=new BiNode;
	char ch;
	cin>>ch;
	if(ch=='#')
		root=NULL;
	else{
		root->data=ch;
		root->lchild=Creat();
		root->rchild=Creat();
	}
	return root;
}

void BiTree::Release(BiNode* root){
	if(root){
		Release(root->lchild);
		Release(root->rchild);
		delete root;
	}
}

BiTree::BiTree(){
	root=Creat();
}

BiTree::~BiTree(){
	Release(root);
}

void BiTree::PostOrder(BiNode* root){
	if(root==NULL)
		return ;
	else{
		PostOrder(root->lchild);
		PostOrder(root->rchild);
		ans[t++]=root->data;
	}
}

int main()
{
	int n,x;
	cin>>n;
	while(n--)
	{
		cin>>x;
		BiTree bt;
		BiNode* root=bt.GetRoot();
		bt.PostOrder(root);
		cout<<ans[x-1]<<endl;
		t=0;
	}
	return 0;
}