从二叉树到八皇后问题

2019-11-06 09:13:23

字体：大中小

来源：转载

供稿：网友

一、树的基本概念

树的定义：

由一个或多个(n≥0)结点组成的有限集合T，有且仅有一个结点称为根（root），当n>1 时，其余的结点分为m(m≥0)个互不相交的有限集合T1,T2，…，Tm。每个集合本身又是棵树，被称作这个根的子树

树的存储结构

顺序存储

可规定为：从上至下、从左至右将树的结点依次存入内存。重大缺陷：复原困难（不能唯一复原就没有实用价值）。

链式存储

可用多重链表：一个前趋指针，n 个后继指针。细节问题：树中结点的结构类型样式该如何设计？即应该设计成“等长”还是“不等长”？缺点：等长结构太浪费（每个结点的度不一定相同）；不等长结构太复杂（要定义好多种结构类型）。以上两种存储方式都存在重大缺陷，应该如何解决呢？计算机实现各种不同进制的运算是通过先研究最简单、最有规律的二进制运算规律，然后设法把各种不同进制的运算转化二进制运算。树的存储也可以通过先研究最简单、最有规律的树，然后设法把一般的树转化为这种简单的树，这种树就是二叉树。

二、二叉树

二叉树相关的知识很多，故而这里不再一一说明，直接进入二叉树的遍历，我们都知道，二叉树的遍历包含递归遍历和非递归遍历。

遍历的思想

指按某条搜索路线遍访每个结点且不重复（又称周游）

遍历的方式

先序遍历中序遍历后序遍历

递归遍历的代码

typedef struct _BtreeNode{ char ch; struct _BtreeNode* lchild; struct _BtreeNode* rchild;}BtreeNode;//先序遍历void before_recursion_btree(BtreeNode *root){ PRintf("%s/n",root->ch); recursion_btree(root->lchild); recursion_btree(root->rchild);}//中序遍历void middle_recursion_btree(BtreeNode *root){ recursion_btree(root->lchild); printf("%s/n",root->ch); recursion_btree(root->rchild);} //后序遍历 void middle_recursion_btree(BtreeNode *root){ recursion_btree(root->lchild); recursion_btree(root->rchild); printf("%s/n",root->ch); }

二茶树的非递归遍历的代码(借用STL中的栈,使用C++完成)

由于STL是C++的标准库，故而要借助STL中的栈来进行二叉树的遍历，必须使用C++，我们也可以自己用C语言封装一个栈，然后再使用自己封装的栈来进行二叉树的遍历，下面用C非递归遍历的二叉树。

C 语言版本的二叉树的非递归遍历

自己封装一个栈

SelfDefStack.h#ifndef _SELDEFSTACCK_H_#define _SELDEFSTACCK_H_#include <stdio.h>#include <stdlib.h>#define MAXSIZE　128typedef struct _SelfDefStack{ void *data[MAXSIZE]; int length;}SelfDefStack;//初始化栈SelfDefStack *init_stack();//入栈void push_stack(SelfDefStack* stack, void *data);//出栈void pop_stack(SelfDefStack* stack);//获得栈顶元素void* top_stack(SelfDefStack* stack);//获得栈大小int length_stack(SelfDefStack* stack);//清空栈void clear_stack(SelfDefStack* stack);//销毁栈void destroy_stack(SelfDefStack* stack);#endifSelfDefStack.c#include"SeqStack.h"SelfDefStack *init_stack(){ SelfDefStack stack = (SelfDefStack *)malloc(sizeof(SelfDefStack)); if(stack == NULL) { return NULL; } for(int i = 0; i < MAXSIZE; i++) { stack->data[i] = NULL; } stack->length = 0; return stack;}void push_stack(SelfDefStack* stack, void *data){ if(stack == NULL || data == NULL) { return; } stack->data[stack->length] = data; stack->length++;}void pop_stack(SelfDefStack* stack){ if(stack == NULL) { return NULL; } stack->data[stack->length - 1] = NULL; stack->length--;}void* top_stack(SelfDefStack* stack){ if(stack == NULL) { return NULL; } return stack->data[stack->length-1];}int length_stack(SelfDefStack* stack){ if(stack == NULL) { return -1; } return stack->length;}void clear_stack(SelfDefStack* stack){ if (stack == NULL) { return; } while (length_stack(stack) > 0) { pop_stack(stack); }}void destroy_stack(SelfDefStack** stack){ if (stack == NULL) { return; } free(*stack); *stack = NULL;}

二叉树的非递归遍历源码

//二叉树的节点定义typedef struct _BiNode{ char data; struct _BiNode *lchild; struct _BiNode *rchild;}BiNode;void non_recursion(BiNode* root){ BiNode *childNode = root; //创建栈 SelfDefStack *stack = init_stack(); while(length_stack(stack) || childNode ) { while(childnode) { printf("%c/n", childnode->data); push_stack(stack, childnode); childnode = childnode->lchild; } if(length_stack(stack) > 0) { BiNode* node = (BiNode*)top_stack(stack); pop_stack(stack); childnode = node->rchild; } }}

C++版二叉树非递归

(此处资料来源于http://blog.csdn.net/j_anson/article/details/49671523)

/* 二叉树实现 */ #include<iostream> #include<string> #include<stack> #include<fstream> using namespace std; const int MAX_N = 100; //数据节点 class Node { public: char data;//数据 class Node *lchild;//左节点 class Node *rchild;//右节点 }; //二叉树 class Tree { public: Tree(){} ~Tree(){} //先序遍历非递归算法 void Disp() { if (t == NULL) { return; } stack<Node *> m_stack; m_stack.push(t); while (!m_stack.empty()) { Node *p = m_stack.top();//赋值一份当前双亲节点 cout << p->data << ends; m_stack.pop(); if (p->rchild)//先存储右子树，确保先输出左子树 { m_stack.push(p->rchild); } if (p->lchild)//后存储左子树 { m_stack.push(p->lchild); } } } //非递归中序遍历二叉树 void DispMid() { if (t == NULL) { return; } Node *p = t; stack<Node *>m_stack; while (p != NULL || !m_stack.empty()) { while (p != NULL)//一路直走至左下角 { m_stack.push(p); p = p->lchild; } if (!m_stack.empty()) { p = m_stack.top();//备份当前栈顶地址 m_stack.pop(); cout << p->data << ends; p = p->rchild; } } } //非递归后序遍历二叉树 void DispBehid() { if (t == NULL) { return; } Node *pre = NULL, *p = t; stack<Node *>m_stack; while (p != NULL || !m_stack.empty()) { while (p != NULL)//一路直走至左下角 { m_stack.push(p); p = p->lchild; } p = m_stack.top(); //右子树为空或者已访问，输出当前节点 if (p->rchild == NULL || p->rchild == pre) { cout << p->data << ends; pre = p;//将当前结点地址赋值pre作为下一次判断标志，防止重复访问 m_stack.pop(); p = NULL;//p赋值空以便访问右子树 } else { p = p->rchild;//访问子树的右子树 } } } //构建二叉树 void Create(string name) { ifstream readfile; string str; readfile.open(name); if (readfile.is_open()) { getline(readfile, str);//读取一行 } readfile.close(); CreateNode(str);//构建二叉树 } //递归先序遍历输出二叉树 void display() { cout << "Output:"; output(t); cout << endl; } //递归中序遍历输出二叉树 void displayMid() { cout << "Output:"; outputMid(t); cout << endl; } //递归后序遍历输出二叉树 void displayBhind() { cout << "output:"; outputBhind(t); cout << endl; } //二叉树高度 void Height() { int height = get_height(t); cout << "Height: " << height << endl; } //输出叶子节点值 void display_leaf() { cout << "Leaves: "; output_leaf(t); cout << endl; } private: Node *t; //构建二叉树 void CreateNode(string str) { stack<Node *> m_stack; Node *p; int k; while (str.length() != 0) { //若当前为'('，将双亲节点推入栈，下一位存储的p值作为左节点处理 if (str[0] == '(') { m_stack.push(p); k = 1; } //为右括号则栈顶退出一位 else if (str[0] == ')') { m_stack.pop(); } //为','，则下一个字符作右节点处理 else if (str[0] == ',') { k = 2; } //存储值用作双亲结点 else { p = (Node *)malloc(sizeof(Node)); p->data = str[0]; p->lchild = p->rchild = NULL; //树根为空时，将第一个节点作为树根并赋值给私有成员变量 if (t == NULL) { t = p; } //树根不为空 else { if (k == 1)//作为左节点处理，将栈中双亲节点的左指针指向当前节点 { m_stack.top()->lchild = p; } else//作为右节点处理 { m_stack.top()->rchild = p; } } } //重构串，除去首字符，并将串长度减小1 str.assign(str.substr(1, str.length() - 1)); } } //递归先序遍历输出二叉树 void output(Node *t) { if (t != NULL)//当树根不为空时 { cout << t->data;//输出 if (t->lchild != NULL || t->rchild != NULL)//左/右结点不为空时递归到下一层 { cout << "("; output(t->lchild); if (t->rchild != NULL)//当左节点遍历结束后，左节点递归返回一层，递归右节点 { cout << ","; } output(t->rchild); cout << ")"; } } } //递归中序遍历二叉树 void outputMid(Node *t) { if (t == NULL) { return; } else { cout << "("; outputMid(t->lchild); if (t->rchild != NULL) { cout << ","; } cout << t->data; outputMid(t->rchild); cout << ")"; } } //递归后序遍历输出二叉树 void outputBhind(Node *t) { if (!t) { return; } else { cout << "("; outputBhind(t->lchild); if (t->rchild != NULL) { cout << ","; } outputBhind(t->rchild); cout << t->data; cout << ")"; } } //求树高 int get_height(Node *t) { int leftheight, rightheight; if (t == NULL)//递归至不存在子节点时返回0 { return 0; } else { leftheight = get_height(t->lchild);//递归求左子树高度 rightheight = get_height(t->rchild);//递归其右子树高度 return leftheight > rightheight ? leftheight+1 : rightheight+1;//递归返回时返回最大值 } } //查找左节点 Node *leftchild(Node *p) { return p->lchild; } //查找右节点 Node *rightchild(Node *p) { return p->rchild; } //输出叶子节点 void output_leaf(Node *t) { if (t != NULL)//树根不为空时 { //当前节点没有子节点时输出节点数据 if (t->lchild == NULL&&t->rchild == NULL) { cout << t->data << ends; } output_leaf(t->lchild);//递归左子树 output_leaf(t->rchild);//递归右子树 } } };

八皇后（8Q）问题

(此处资料来源于http://www.cnblogs.com/gaoteng/archive/2012/04/11/2442692.html) 在国际象棋棋盘上（8*8）放置八个皇后，使得任意两个皇后之间不能在同一行，同一列，也不能位于同于对角线上。问共有多少种不同的方法，并且指出各种不同的放法(写代码实现)

算法思路：

　　首先我们分析一下问题的解，我们每取出一个皇后，放入一行，共有八种不同的放法，然后再放第二个皇后，同样如果不考虑规则，还是有八种放法。于是我们可以用一个八叉树来描述这个过程。从根节点开始，树每增加一层，便是多放一个皇后，直到第8层（根节点为0层），最后得到一个完全八叉树。　　

　　紧接着我们开始用深度优先遍历这个八叉树，在遍历的过程中，进行相应的条件的判断。以便去掉不合规则的子树。

　　那么具体用什么条件来进行子树的裁剪呢？

　　我们先对问题解的结构做一个约定。

　　用X[i]来表示，在第i行，皇后放在了X[i]这个位置。

　　于是我们考虑第一个条件，不能再同一行，同一列于是我们得到x[i]不能相同。剩下一个条件是不能位于对角线上，这个条件不是很明显，我们经过分析得到，设两个不同的皇后分别在j，k行上，x[j],x[k]分别表示在j,k行的那一列上。那么不在同一对角线的条件可以写为abs((j-k))!=abs(x[j]-x[k])，其中abs为求绝对值的函数。

　　于是下面我们便可以利用一个递归的调用来遍历八叉树。

　　我们首先定义一个访问某节点所有子节点的函数

void backtrack(int t){ if(t>num) //num为皇后的数目 { sum++;//sum为所有的可行的解 for(int m = 1;m<num;m++) { cout<<x[m];//这一行用输出当递归到叶节点的时候，一个可行解 } cout<<endl; } else for(int i = 1;i<=num;i++) { x[t] = i; if(place(t)) backtrack(t+1);//此处的place函数用来进行我们上面所说的条件的判断，如果成立，进入下一级递归 }}bool place(int k){ for(int j = 1;j<k;j++) if(abs(x[k] - x[j]) == abs(k-j)||x[j] == x[k]) return false; return true;}

上一篇：[BZOJ4628][BeiJing2016]IP地址可持久化线段树+字典树

下一篇：P2P的特点