信号放大器数据结构_[11/11]数据结构二叉树应用(树型信号放大器，file transfer，遍历的非递归实现)...

川长思鸟来 2022-10-24 05:48 95阅读 0赞

## 树型分布网络信号放大器 ##

![f941620d2723d1a8feaf93e7e20656ed.png][]

![bfd83841cb47780147b21afa357c0822.png][]

![bfa861c2279c6fede53cb5d4d8e79b67.png][]

## 森林和二叉树的相互转换 ##

![6d09952367652c5af5476fd4ccfd588a.png][]

![616fa4d49a2f7f3d3a43e6fd0af54d26.png][]

![208437023f22dfa428e617176f6ad703.png][]

![e729c26daca4a8565f904c58f612544b.png][]

## 并查集 ##

例题：File transfer

![83324760b47eb8b47ca9eb45c89fe60f.png][]

![03f9fd56c5300d5b618952df842b3bf6.png][]

![4478152db2ce30ec63b96a29d77ccf3e.png][]

![0b8bbac72ffc828e64e2332e6b0adcaf.png][]

![40eaa2e3256ff3f4411990b08ca7cab9.png][]

![e5535837a6c22b7fd852009f5535da14.png][]

![91cccfa12b4cc7ff5a249b3d5ef703c1.png][]

![4240a0e29a3c3811b59287601f5badb0.png][]

![be75f123ce6b3aa9a0f140b3e1c10bb2.png][]

![cea32530c825e406a7a0ddfe101b6147.png][]

![ddd41a557a4a77ba70850d7a39cf2427.png][]

![05f4dc026b31476c48b8d0a84b03a9ff.png][]

![d4ca02bff8b7a8f66bb5f219aea03458.png][]

![cdda1b414a703005ae3e54b900f1b867.png][]

#include <iostream>
    using namespace std;
    //typedef int ElementType;
    //typedef int SetName;
    //typedef ElementType SetType[MaxSize];
    //找到X所在的集合
    int s[10001];
    int Find(int X) {
         
    	if (s[X] < 0) return X;
    	else return s[X] = Find(s[X]);
    }
    void f1(int X1, int X2) {
         
    	if (Find(X1) == Find(X2)) cout << "yes" << endl;
    	else cout << "no" << endl;
    }
    
    void Union(int X1, int X2) {
         
    	int root1 = Find(X1);//X1的树根
    	int root2 = Find(X2);
    	if (root1 < root2) {
         //说明第一个集合里元素个数多
    		s[root1] += s[root2];
    		//cout << "把" << X1 << "的根节点的值修改为" << s[root1] << endl;
    
    		s[root2] = root1;
    		//cout << "把" << X2 << "的根节点的值修改为" << s[root2] << endl;
    	}
    	if (root1 > root2) {
         
    		s[root2] += s[root1];
    		//cout << "把" << X2 << "的根节点的值修改为" << s[root2] << endl;
    		s[root1] = root2;
    		//cout << "把" << X1 << "的根节点的值修改为" << s[root1] << endl;
    	}
    }
    
    int GetNum(int n) {
         
    	int temp = 0;
    	for (int i = 1; i <= n; i++) {
         
    		if (s[i] <0) temp++;
    	}
    	return temp;
    }
    
    int main() {
         
    	int N; cin >> N;
    	for (int i = 1; i <= N; i++) 
    		s[i] = -1;
    	char choice=NULL;
    	int X1, X2;
    	while (cin >> choice) {
         
    		switch (choice) {
         
    		case 'I': {
         
    			cin >> X1 >> X2;
    			Union(X1, X2);
    			break;
    		}
    		case 'C': {
         
    			cin >> X1 >> X2;
    			f1(X1, X2);
    			break;
    		}
    		case 'S': {
         
    			if (GetNum(N) == 1) cout << "The network is connected." << endl;
    			else cout << "There are " << GetNum(N) << " components." << endl;
    			return 0;
    		}
    		}
    	}
    }

## 二叉树遍历的非递归实现 ##

中序遍历

#include <iostream>
    #include <stack>
    #include <list>
    using namespace std;
    typedef BinNode* Bintree; //二叉树
    struct BinNode {
         
    	char data;
    	BinNode* left;
    	BinNode* right;
    }; //二叉树节点
    
    stack<BinNode>S;//二叉树堆栈
    //中序遍历
    void InOrderTaversal(Bintree BT) {
         
    	Bintree T = BT;//BT指向树根
    	while (T || !S.empty()) {
         
    		while (T) {
          //其实这是递归
    			S.push(*T);
    			T = T->left;
    		}//循环结束说明左边的树空了
    		if (!S.empty()) {
         //一定到达边界了（T=NULL），可能左树为空，可能右树为空
                                     //如果左树为空，只要有节点为空说明可以出栈了
    			*T = S.pop();
    			cout << (*T).data;
    			T = T->right;
    		}
    	}
    }

先序遍历

跟中序遍历差不多，不过要在第一次访问一个节点的时候就输出该节点的信息

void PreOrderTaversal(Bintree BT) {
         
    	Bintree T = BT;//BT指向树根
    	while (T || !S.empty()) {
         
    		while (T) {
          //其实这是递归
    			S.push(*T);
                            cout << (*T).data;
    			T = T->left;
    		}//循环结束说明左边的树空了
    		if (!S.empty()) {
         //一定到达边界了（T=NULL），可能左树为空，可能右树为空
                                     //如果左树为空，只要有节点为空说明可以出栈了
    			*T = S.pop();
    			T = T->right;
    		}
    	}
    }

后序遍历

![67546b5e8f3787d93dbadfae38088053.png][]

stack<BinNode2>s;
    void postOrder2(BinTree BT)    //非递归后序遍历{
         
            BinTree T=BT;
            while(T||!s.empty()){
         
                  while(T){
         
                       BinNode2 bn=new BinNode2(T,1);
                       s.push(bn); 
                       T=T->left;
                  }
                  if(!s.empty()){
         
                       BinNode temp=s.pop();
                       if(temp.isfirst){
         
                             temp.isfirst=0;
                             s.push(temp);
                             T=temp.btnode->right;
                       }
                       else{
         
                             cout<<temp.btnode->data;
                             T=NULL;
                       }
                  }
            }
    }

层序遍历（使用队列）

void LevelOrderTraversal(Bintree BT) {
         
    	Bintree T = BT;
    	list<Bintree>l;
    	l.push_back(T);
    	while (!l.empty()) {
         
    		*T = l.pop_front();
    		cout << (*T).data;
    		if (T->left) l.push_back(T->left);
    		if (T->right)l.push_back(T->right);
    	}
    }

[f941620d2723d1a8feaf93e7e20656ed.png]: /images/20221024/dd4152f69f9b4643a56f6886580cd4db.png
[bfd83841cb47780147b21afa357c0822.png]: /images/20221024/5015c899c34347c4919f61ec955fb834.png
[bfa861c2279c6fede53cb5d4d8e79b67.png]: /images/20221024/31e7b9dfa27a48eaa51eed1598e5504e.png
[6d09952367652c5af5476fd4ccfd588a.png]: /images/20221024/02ac4c4983484f70a731299fb5b165bc.png
[616fa4d49a2f7f3d3a43e6fd0af54d26.png]: /images/20221024/54214e9836114515a2310ee99b3c2d62.png
[208437023f22dfa428e617176f6ad703.png]: /images/20221024/78bed053f9db481e92e54f8708e5932e.png
[e729c26daca4a8565f904c58f612544b.png]: /images/20221024/39d0763119a542d59e4bd8b35e2dc409.png
[83324760b47eb8b47ca9eb45c89fe60f.png]: /images/20221024/3e501462924541b48da3a79cd9ff1059.png
[03f9fd56c5300d5b618952df842b3bf6.png]: /images/20221024/e228c2a5846d4eba9fd83a051462361a.png
[4478152db2ce30ec63b96a29d77ccf3e.png]: /images/20221024/35a26b2e07ed4682a7047a60d7b52171.png
[0b8bbac72ffc828e64e2332e6b0adcaf.png]: /images/20221024/34b0a04549b048478084586ed4bf94ab.png
[40eaa2e3256ff3f4411990b08ca7cab9.png]: /images/20221024/7b8bc701763b44a8a80a347a9e5a4db0.png
[e5535837a6c22b7fd852009f5535da14.png]: /images/20221024/3842fabb4be04f6caaa548a0955fd191.png
[91cccfa12b4cc7ff5a249b3d5ef703c1.png]: /images/20221024/49f5b91aba20410bbfd382a0446f605c.png
[4240a0e29a3c3811b59287601f5badb0.png]: /images/20221024/58eb07698fe84229a4c7459ffa74a8d3.png
[be75f123ce6b3aa9a0f140b3e1c10bb2.png]: /images/20221024/d7f169b05fc449d98d87ffbc5c325a65.png
[cea32530c825e406a7a0ddfe101b6147.png]: /images/20221024/f5b2a23d39d9429495bd3ae2fd1d7a21.png
[ddd41a557a4a77ba70850d7a39cf2427.png]: /images/20221024/fae86a9141f94e1b9312716dd0ce53d3.png
[05f4dc026b31476c48b8d0a84b03a9ff.png]: /images/20221024/32dd6c6fcc2f4ea8a009938004aab5f9.png
[d4ca02bff8b7a8f66bb5f219aea03458.png]: /images/20221024/28ebac3ea139426dae07e29a1f6a24ff.png
[cdda1b414a703005ae3e54b900f1b867.png]: /images/20221024/7ab06b869b1047e1917b36e4cc9bcce9.png
[67546b5e8f3787d93dbadfae38088053.png]: /images/20221024/d1ae4f746c894d11bc5f7e9b1a41b5ca.png