/*二叉树的各种操作复习*/
#include <stdio.h>

#define BACK_ODER   -1
#define IN_ODER     0
#define PRE_ODER    1
#define LEVEL_ODER  2//层次化遍历
typedef struct _Node{
	char data;
	struct _Node *lchild;
	struct _Node *rchild;
} Node,*Tree;

/* 生成二叉树的普通方法
 * 按先序次序输入二叉树中结点的值
 * 构造二叉链表表示的二叉树T。输入空格表示空子树。 */
Node * CreateTree()
{
    char ch;
    Node *T;
    scanf("%c",&ch);
    if(ch==' ') /* 空 */
        return NULL;
    else
    {
        T=(Node *)malloc(sizeof(Node));
        if(!T)
            exit(0);
        T->data=ch; /* 生成根结点 */
        T->lchild = CreateTree(); /* 构造左子树 */
        T->rchild = CreateTree(); /* 构造右子树 */
    }
    return T;
}
/* 由先根序列和中根序列生成二叉树
 * 递归法。pre 是先跟序列，in是中根序列
 * pre_s是先根序列的起始，pre_e是先跟序列的结束
 * in_s是中根序列的起始,in_e是中根序列的结束
 */
Node *Convert(char pre[], int pre_s, int pre_e,
              char in [], int in_s , int in_e )
{


    int i = in_s;
    Node *p;
    if(in_s > in_e)return NULL;
    for(i=in_s;i<in_e&&in[i]!=pre[pre_s];i++);//找到中跟中的头所在位置
    p = (Node *)malloc(sizeof(Node));
    p->data = pre[pre_s];
    //注意以下递归过程是关键
    p->lchild = Convert(pre, pre_s+1, pre_s+i-in_s,
                        in,  in_s,i-1);
    p->rchild = Convert(pre, pre_s+i-in_s+1,pre_e,
                        in,  i+1,in_e);
    return p;
}
/* 求二叉树的度 */
int GetDegree(const Tree head)
{
    int degree = 0;
    int m,n;
    if(!head)return 0;

    if(head->lchild && head->rchild) return 2;
    else if(!head->lchild && !head->rchild) return 0;
    else {
        m = GetDegree(head->lchild) ;
        n = GetDegree(head->rchild) ;
        if(2==m || 2==n)return 2;
        else return 1;
    }
    return degree;
}
/* 求二叉树的高度 */
int GetHight(const Tree head)
{
    int m,n;
    if(!head)return 0;
    m = GetHight(head->lchild);
    n = GetHight(head->rchild);
    return 1 + (m > n ? m : n);
}
/* 输出二叉树中某个指定元素的祖父节点(包括自己)
 * 递归思想：如果那个节点在我的子树中，那么我是祖父节点
 * 返回值 ：1表示子树中有 ，0表示无 */
int GetGrandPa(const Tree head, const char e)
{
   if(!head)return 0;
   if(GetGrandPa(head->lchild,e) || GetGrandPa(head->rchild,e) || e==head->data)//子树中有此节点
   {
       printf("%c",head->data);
       return 1;
   }
   else return 0;
}
/* 遍历二叉树，参数oder控制遍历方式 */
void Tranverse(Node *head,int oder)
{
	if(!head)return ;
	if(LEVEL_ODER == oder)
	{
	    LevTranverse(&head,1);
        return;
	}
    if(PRE_ODER == oder) printf("%c\t",head->data);
	Tranverse(head->lchild,oder);
	if(IN_ODER == oder) printf("%c\t",head->data);
	Tranverse(head->rchild,oder);
	if(BACK_ODER == oder) printf("%c\t",head->data);
	return;
}
/* 层次化遍历，采用递归思想而不用队列。
 * 递归思想：把当前层遍历的同时把下一层存储好
 * nodes[]作为队列用,存储的当前层的节点
 * count记录当前层的元素个数 */
void LevTranverse(const Node* nodes[], int count)
{
    int i=0, j=0;
    Node *nextNodes[100] = {0};
    if(0 == count) return;
    for(i = 0,j=0; i<count; i++)
    {
        printf("%c\t",nodes[i]->data);
        if(nodes[i]->lchild)nextNodes[j++] = nodes[i]->lchild;
        if(nodes[i]->rchild)nextNodes[j++] = nodes[i]->rchild;
    }
    LevTranverse(nextNodes,j);
    return;
}

/* 构建二叉排序树 */
int InsertBiSearchTree(Node *head,char ch)
{
    Node *p,*pre,*newNode;
    if(NULL == head)return 1;
    p = head;
    while(p)
    {
        pre = p;
        if(ch == p->data)return 1;
        if(ch < p->data)p = p->lchild;
        else p = p->rchild;
    }
    newNode = (Node *)malloc(sizeof(Node));
    newNode->lchild = newNode->rchild = NULL;
    newNode->data = ch;
    if(ch < pre->data)pre->lchild = newNode;
    else pre->rchild = newNode;
    return 0;
}
Node* CreateBiSearchTree(void)
{
    char a;
    Node *p,*head,*q,*pre;
    scanf("%c",&a);
    if(' ' == a)return NULL;
    p = (Node *)malloc(sizeof(Node));
    p->lchild = p->rchild = NULL;
    p->data = a;
    head = p;
    while(1)
    {
        scanf("%c",&a);
        if(' ' == a)break;
        InsertBiSearchTree(head,a);
    }
    return  head;
}
/* 求一棵树的查找长度(查找成功) */
int GetSearchLength(Node *head,int hight)
{
    if(NULL == head)return 0;
    return hight
            + GetSearchLength(head->lchild,hight+1)
            + GetSearchLength(head->rchild,hight+1);

}

int main(int argc, char *argv[])
{
    char pre[]= "abcde";
	char in[] = "bcade";

	Node *head = Convert(pre,0,strlen(pre)-1,
                   in ,0,strlen(in)-1);

    printf("Hight : %d\n",GetHight(head));
    printf("Degree : %d\n",GetDegree(head));
    if(!GetGrandPa(head,'c'))printf("No grandpa !");printf("\n");
    Tranverse(head,LEVEL_ODER);printf("\n");

    printf("Now create BiSearchTree..\n");
    head = CreateBiSearchTree();
    Tranverse(head,IN_ODER);printf("\n");
    printf("%d\n",GetSearchLength(head,1));
    return 0;
}

降维问题：顺序、链式存储结构的二叉树递归遍历、层次遍历求高度

全部源代码在最后
一、概要设计
测试数据：如图所示森林



森林采用兄弟孩子链表表示法。

森林的数据输入采取输入兄弟孩子链表表示法下的等价二叉树的扩展先序遍历形成的线性串的方法（原理为森林先序遍历结果与等价二叉树的先序遍历结果相同）



输入数据：ABEK..F..CG..DH.I.J...L.MN...
算法设计
以链式存储结构为例

递归遍历求高度：由于孩子兄弟链表表示法是把兄弟当儿子,所以对应二叉树的所有左子树的最大高度便是森林的高度。这样，在求二叉树高度的算法上可以改进，将左子树给定权重1，右子树给定权重0；即只需
if(root == NULL) return 0;
return max(GetHeightByRecursion(root->firstson) + 1, GetHeightByRecursion(root->nextbrother));

层次遍历求高度：利用队列，将第一个儿子入队，再进行一系列循环操作
实验结果

二、 详细设计
1. 链式存储结构

森林链表

template<typename T>
struct ForestNode
{
	T data;
	ForestNode<T>* firstson;
	ForestNode<T>* nextbrother;
	ForestNode()
	{
		firstson = NULL;
		nextbrother = NULL;
	}
};


森林类

template<typename T>
class Forest
{
public:
	Forest() {};
	~Forest(){};
	ForestNode<T>* getFirstTreeRoot(){};
	void build(ForestNode<T>* & node){};
	void deleteAll(ForestNode<T>* node){};
	int LevelTraversalAndReturnHeight(ForestNode<T>* root){};
	int GetHeightByRecursion(ForestNode<T>* root){};
private:
	ForestNode<T>* FirstTreeRoot;
};


构造函数

 Forest() 
	{
		FirstTreeRoot = new ForestNode<T>;
	};


析构函数

 ~Forest()
	{
		deleteAll(FirstTreeRoot);
	}


获得第一个根结点

ForestNode<T>* getFirstTreeRoot() { return FirstTreeRoot; };


通过输入先序拓展遍历序列递归建立森林

void build(ForestNode<T>* & node)
	{
		T nodedata;
		nodedata = cin.get();
		if (nodedata == '.')
		{
			node = NULL;
			return;
		}
		node = new ForestNode<T>;
		node->data = nodedata;
		build(node->firstson);
		build(node->nextbrother);
	}


删除子树

void deleteAll(ForestNode<T>* node)
		{
			if (node == NULL) return;
			deleteAll(node->firstson);
			deleteAll(node->nextbrother);
			delete node;
		}


层次遍历并返回高度

int LevelTraversalAndReturnHeight(ForestNode<T>* root)
	{
		queue<ForestNode<T>*> Queue;
		Queue.push(root);
		int height = 0;
		while (Queue.size() != 0)
		{
			cout << "level" << height + 1 << ":";
			int len = Queue.size();
			ForestNode<T>* node;
			for (int i = 1; i <= len; i++)
			{
				node = Queue.front();
				Queue.pop();
				while (node != NULL)
				{
					cout << node->data << " ";
					if (node->firstson != NULL) Queue.push(node->firstson);
					node = node->nextbrother;
				}
				cout << "   ";
			}
			cout << endl;
			height++;
		}
		return height;
	}


递归遍历求高度（）

int GetHeightByRecursion(ForestNode<T>* root)
	{
		if(root == NULL) return 0;
		return max(GetHeightByRecursion(root->firstson) + 1, GetHeightByRecursion(root->nextbrother));
	}

2.顺序存储结构
template<typename T>
class SeqForest
{
public:
	SeqForest(int totalnum)
	{
		if (totalnum > 0)
		{
			this->totalnum = totalnum;
			array = new T[totalnum + 1];
			memset(array, ' ', (totalnum + 1) * sizeof(T));
		}
	}
	~SeqForest()
	{
		delete[]array;
	}
	void build(int index = 1)
	{
		T data;
		data = cin.get();
		if (data == '.'||index>totalnum) return;
		array[index] = data;
		build(2 * index);
		build(2 * index + 1);
	}
	int GetHeightByRecursion(int i = 1)
	{
		if (i> totalnum || array[i] == ' ') return 0;
		return max(GetHeightByRecursion(2 * i) + 1, GetHeightByRecursion(2 * i + 1));
	}
	int LevelTraversalAndReturnHeight(int i = 1)
	{
		queue<int> Queue;
		Queue.push(i);
		int height = 0;
		while (!Queue.empty())
		{
			cout << "level" << ++height << ":";
			int len = Queue.size();
			for (int j = 1; j <= len; j++)
			{
				int index = Queue.front();
				Queue.pop();
				while (array[index] != ' ')
				{
					if (array[2 * index] != ' ') Queue.push(2 * index);
					cout << array[index] << " ";
					index = 2 * index + 1;
				}
			}
			cout << endl;
		}
		return height;
	}
private:
	int totalnum;
	T* array;
};

三、全部源代码
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

//顺序存储结构
template<typename T>
class SeqForest
{
public:
	SeqForest(int totalnum)
	{
		if (totalnum > 0)
		{
			this->totalnum = totalnum;
			array = new T[totalnum + 1];
			memset(array, ' ', (totalnum + 1) * sizeof(T));
		}
	}
	~SeqForest()
	{
		delete[]array;
	}
	void build(int index = 1)
	{
		T data;
		data = cin.get();
		if (data == '.'||index>totalnum) return;
		array[index] = data;
		build(2 * index);
		build(2 * index + 1);
	}
	int GetHeightByRecursion(int i = 1)
	{
		if (i> totalnum || array[i] == ' ') return 0;
		return max(GetHeightByRecursion(2 * i) + 1, GetHeightByRecursion(2 * i + 1));
	}
	int LevelTraversalAndReturnHeight(int i = 1)
	{
		queue<int> Queue;
		Queue.push(i);
		int height = 0;
		while (!Queue.empty())
		{
			cout << "level" << ++height << ":";
			int len = Queue.size();
			for (int j = 1; j <= len; j++)
			{
				int index = Queue.front();
				Queue.pop();
				while (array[index] != ' ')
				{
					if (array[2 * index] != ' ') Queue.push(2 * index);
					cout << array[index] << " ";
					index = 2 * index + 1;
				}
			}
			cout << endl;
		}
		return height;
	}
private:
	int totalnum;
	T* array;
};
//链式存储结构
template<typename T>
struct ForestNode
{
	T data;
	ForestNode<T>* firstson;
	ForestNode<T>* nextbrother;
	ForestNode()
	{
		firstson = NULL;
		nextbrother = NULL;
	}
};
template<typename T>
class Forest
{
public:
	Forest() 
	{
		FirstTreeRoot = new ForestNode<T>;
	};
	~Forest()
	{
		deleteAll(FirstTreeRoot);
	}
	ForestNode<T>* getFirstTreeRoot() { return FirstTreeRoot; };
	void build(ForestNode<T>* & node)
	{
		T nodedata;
		nodedata = cin.get();
		if (nodedata == '.')
		{
			node = NULL;
			return;
		}
		node = new ForestNode<T>;
		node->data = nodedata;
		build(node->firstson);
		build(node->nextbrother);
	}
		void deleteAll(ForestNode<T>* node)
		{
			if (node == NULL) return;
			deleteAll(node->firstson);
			deleteAll(node->nextbrother);
			delete node;
		}
	int LevelTraversalAndReturnHeight(ForestNode<T>* root)
	{
		queue<ForestNode<T>*> Queue;
		Queue.push(root);
		int height = 0;
		while (Queue.size() != 0)
		{
			cout << "level" << height + 1 << ":";
			int len = Queue.size();
			ForestNode<T>* node;
			for (int i = 1; i <= len; i++)
			{
				node = Queue.front();
				Queue.pop();
				while (node != NULL)
				{
					cout << node->data << " ";
					if (node->firstson != NULL) Queue.push(node->firstson);
					node = node->nextbrother;
				}
				cout << "   ";
			}
			cout << endl;
			height++;
		}
		return height;
	}
	int GetHeightByRecursion(ForestNode<T>* root)
	{
		if(root == NULL) return 0;
		return max(GetHeightByRecursion(root->firstson) + 1, GetHeightByRecursion(root->nextbrother));
	}
private:
	ForestNode<T>* FirstTreeRoot;
};
int main()
{
	cout << "Seqeuence storage structure：" << endl;
	SeqForest<char> sequenceBT(200);
	cout << "Please enter the expanded forest preorder list of Child brother list notation:";
	sequenceBT.build();
	cout << "Get height by recursion traversal:" << endl;
	cout << sequenceBT.GetHeightByRecursion() << endl;
	cout << "Forest's level traversal and get height:" << endl;
	cout << sequenceBT.LevelTraversalAndReturnHeight() << endl;
	cout << endl;
	cout << "List storage structure：" << endl;
	Forest<char> forest;
	ForestNode<char>* root = forest.getFirstTreeRoot();
	cin.get();
	cout << "Please enter the expanded forest preorder list of Child brother list notation:";
	forest.build(root);
	cout << "Get height by recursion traversal：";
	cout << forest.GetHeightByRecursion(root) << endl;
	cout << "Forest's level traversal and get height:" << endl;
	cout << forest.LevelTraversalAndReturnHeight(root) << endl;
}

思路

利用顺序栈，循环结束条件用队列非空判断，当栈为空时，二叉树即遍历完。
1、首先将根节点入队，然后进入循环。
2、每次循环将队首节点出队，并依次将当前处理节点的左、右孩子入队。用一个指针来标记层尾节点，当队头指针=层尾指针时，说明遍历完了一层，层数+1并更新层尾指针指向的层尾节点。
3、循环处理直到队列为空即遍历完二叉树所有节点。

.

typedef struct BiTNode {   //二叉树节点定义
	char data;
	struct BiTNode* lchild, * rchild;
}BiTNode, * BiTree;


typedef struct {      //顺序队列定义
	BiTree* base;     //以指向BiTNode的指针作为元素
	int front;
	int rear;
}SqQueue;


//层次遍历得到二叉树高度
int LevelGetBiTreeHeight(BiTree T) {
	if (T == NULL)	 return 0;    //树为空

	SqQueue Q;
	BiTree temp;
	int level = 0;  //记录层数
	int last = 1;  //last标记当前层的最后一个节点

	InitQueue(Q);

	EnQueue(Q, T);      //队首节点入队

	while (Q.front < Q.rear) {
		DeQueue(Q, temp);      //队首节点出队

		if (temp->lchild)
			EnQueue(Q, temp->lchild);    //将当前输出节点的左孩子入队

		if (temp->rchild)
			EnQueue(Q, temp->rchild);    //将当前输出节点的右孩子入队

		if (Q.front == last) {      //处理分层
			level++;
			last = Q.rear;      //改变层尾
		}
	}
	return level;    //返回层数即为高度

}

以上

来自大佬群主的第二题



所谓层次遍历，是将二叉树中的元素从根节点按照节点层数一层层的输出。

代码如下：

int GetDepth(bitreenode *root)
{
    int depth=0;
    bitreenode *p=root;
    queue<bitreenode*> q;
    q.push(p);  //根指针入队
    while(!q.empty())
    {
        depth++;  //高度加一
        int width=q.size();  //获取当前层次宽度
        for(int i=0;i<width;i++)
        {
            p=q.front();  //获取队顶元素
            q.pop();  //弹出队顶元素
            if(p->leftchild!=NULL)  //左孩子入队
                q.push(p->leftchild);
            if(p->rightchild!=NULL)  //右孩子入队
                q.push(p->rightchild);
        }

    }
    cout<<depth<<endl;
}