[Day15]程序菜鸟自学C++资料结构演算法 – 二元树的基本应用

前言：介绍完了二元树的建立和走访方式，紧接着要来介绍其他基本应用，一样用上一篇的程序码进行修改

可以先把之前的程序码改成T指针类型，後续的操作会比较方便，更改方式如图：
注意!!! BiTree()原本T的地方改成root，避免命名重复导致程序错误(一开始命名的不好是我的疏忽˃ʍ˂)


接着就可以开始实作罗

1.求二元树的深度

可以看到树的深度如预期的一样为3

2.计算树的叶节点数目

可以看到叶节点的各数为4(DEFG)。

也可以把判断式改成if (!T->Lchild && !T->Rchild || !T->Lchild && T->Rchild)则可以检查多余的节点，来判断是否为严格二元树。

3.利用空节点标记符号(#)来建立二元树
相信很多人不懂这题的意思，其实是在走访节点的下一个节点不存在时(没有子节点)，输出一个#。

先修改之前的前序走访作为范例。

这样做的意义在哪呢？
这样做是方便还原二元树的样貌，如果没有这些符号，二元树会有多种可能，不只是人，连电脑也无法判断出这个二元树原本的样貌，来实际画画看就知道了。

左节点优先权大於右节点，所以都是先从左边开始画

接着我们现在要做的就是输入一串带有空节点符号的前序序列，来让电脑建立二元树

接着输入前序串列

如果有跑出结果就代表建立成功，顺便检查和第三行是不是一样

这种方法也可以用在另外三种走访方式，有兴趣的人可以自己操作看看

今日小结：今天讲了一些常见但实用的小技巧，尤其是第三个利用空节点符号转回二元树的方法，算是相当重要的必备技能，其实树还有非常多衍生跟应用，只不过也是会花太多篇幅，有机会再向大家介绍，树的部分先告一段落，明天也将要进入新的环节。

#include<iostream>
using T = char;
#include<queue>
using namespace std;

template<typename T>
class BiTree {
public:
	struct BiNode {
		T data;
		BiNode* Lchild{ 0 };
		BiNode* Rchild{ 0 };
	};

	BiNode* root;
	BiTree() {
		root = PreCreat(); //因为要建立新的二元树，所以原本的可以先注解掉
		/*
		root = new BiNode(); root->data = 'A';
		root->Lchild = new BiNode(); root->Lchild->data = 'B';
		root->Rchild = new BiNode(); root->Rchild->data = 'C';
		BiNode* P = root->Lchild;
		P->Lchild = new BiNode(); P->Lchild->data = 'D';
		P->Rchild = new BiNode(); P->Rchild->data = 'E';
		BiNode* S = root->Rchild;
		S->Lchild = new BiNode(); S->Lchild->data = 'F';
		S->Rchild = new BiNode(); S->Rchild->data = 'G';
		*/
	}
	void Inorder(BiNode* T) {
		if (!T)return;
		Inorder(T->Lchild);
		std::cout << T->data << " ";
		Inorder(T->Rchild);
	}

	void Preorder(BiNode* T) {
		if (!T) {
			std::cout << "#" << " ";
			return;
		} 
		std::cout << T->data;
		Preorder(T->Lchild);
		Preorder(T->Rchild);
	}

	void Postorder(BiNode* T) {
		if (!T)return;
		Postorder(T->Lchild);
		Postorder(T->Rchild);
		std::cout << T->data << " ";
	}
	void Level_order(BiNode* T) {
		queue<BiNode*> Q;
		Q.push(T);
		while (!Q.empty()) {
			BiNode* p = Q.front();
			Q.pop();
			std::cout << p->data << " ";
			if (p->Lchild) Q.push(p->Lchild);
			if (p->Rchild) Q.push(p->Rchild);
		}
	}
	void Inorder() {
		Inorder(root);
	}
	void Preorder() {
		Preorder(root);
	}
	void Postorder() {
		Postorder(root);
	}
	void Level_order() {
		Level_order(root);
	}
	int Depth(BiNode* T){
		if (!T) return 0;
		int L = Depth(T->Lchild);
		int R = Depth(T->Rchild);
		return L > R ? L + 1 : R + 1; //如果L>R，那麽树深将会是L的深度+1，否则是R的深度+1
	}
	int Depth() {
		return Depth(root);
}
	int Count(BiNode* T) {
		if (!T) return 0;
		int L = Count(T->Lchild);
		int R = Count(T->Rchild);
		if (!T->Lchild && !T->Rchild) //如果Lchild不为0且Rchild不为0
			return L + R + 1;
		else
			return L + R;
	}
	int Count() {
		return Count(root);
	}
	BiNode* PreCreat() {
		T e;
		std::cin >> e;
		if (e == '#') return 0;
		BiNode* J = new BiNode();
		J->data = e;
		J->Lchild = PreCreat();
		J->Rchild = PreCreat();
		return J;
	}
};

using T = char;
int main() {
	BiTree<char> bt;
	bt.Inorder(); std::cout << "\n";
	bt.Preorder(); std::cout << "\n";
	bt.Postorder(); std::cout << "\n";
	bt.Level_order(); std::cout << "\n";
	std::cout << std::endl;

	std:cout<<bt.Count()<< "\n";
}