#includeiostream
成都創(chuàng)新互聯(lián)公司專注于新市網(wǎng)站建設(shè)服務(wù)及定制，我們擁有豐富的企業(yè)做網(wǎng)站經(jīng)驗(yàn)。 熱誠(chéng)為您提供新市營(yíng)銷型網(wǎng)站建設(shè)，新市網(wǎng)站制作、新市網(wǎng)頁(yè)設(shè)計(jì)、新市網(wǎng)站官網(wǎng)定制、小程序開發(fā)服務(wù)，打造新市網(wǎng)絡(luò)公司原創(chuàng)品牌,更為您提供新市網(wǎng)站排名全網(wǎng)營(yíng)銷落地服務(wù)。
#includemap
using namespace std;
const int N=15e3+100;
struct node{
int v;//結(jié)點(diǎn)值
int l,r;//左右孩子的下標(biāo)
st()
{//初始化
l=r=-1;
}
}tree[4*N];//4倍空間,用來儲(chǔ)存二叉樹
mapint,intmp;//儲(chǔ)存數(shù)值在數(shù)組a中的下標(biāo)
int a[N];//基礎(chǔ)數(shù)組,數(shù)組tree在其基礎(chǔ)上建樹
int n=1;//1 5 8 0 0 0 6 0 0
void build_tree(int rt,int num)
{//構(gòu)建二叉樹
if(a[num]==0)
{//a[num]==0,表示空結(jié)點(diǎn)
tree[rt].v=-1;
}
else
{
if(mp.count(a[num])==0)
mp[a[num]]=rt;//儲(chǔ)存a[num]在樹中的位置
tree[rt].v=a[num];//結(jié)點(diǎn)賦值
num++;
build_tree(2*rt,num);//左孩子
num++;
build_tree(2*rt+1,num);//右孩子
}
}
/*
1 5 8 0 0 0 6 0 0
3
8 1 6
*/
int main()
{
int x=1,m=0;
do
{
cina[n++];//儲(chǔ)存結(jié)點(diǎn)值
}
while(getchar()!='\n');//回車結(jié)束輸入
build_tree(1,x);//構(gòu)建二叉樹(結(jié)構(gòu)體數(shù)組模擬)
cinm;//查詢次數(shù)
for(int i=0;im;i++)
{
int num,y;
cinnum;//查詢值
y=mp[num];//mp[num]是num在tree數(shù)組中的位置,查詢效率O(log2n)
y/=2;//左右孩子的下標(biāo)除以2，就是父節(jié)點(diǎn)的下標(biāo)
if(y==0)
{//父節(jié)點(diǎn)下標(biāo)為0，既是根節(jié)點(diǎn)
cout0endl;
}
else
{//輸出父節(jié)點(diǎn)值
couttree[y].vendl;
}
}
return 0;
}
先序非遞歸算法
【思路】
假設(shè)：T是要遍歷樹的根指針，若T != NULL
對(duì)于非遞歸算法，引入棧模擬遞歸工作棧，初始時(shí)棧為空。
問題：如何用棧來保存信息，使得在先序遍歷過左子樹后，能利用棧頂信息獲取T的右子樹的根指針？
方法1：訪問T-data后，將T入棧，遍歷左子樹；遍歷完左子樹返回時(shí)，棧頂元素應(yīng)為T，出棧，再先序遍歷T的右子樹。
方法2：訪問T-data后，將T-rchild入棧，遍歷左子樹；遍歷完左子樹返回時(shí)，棧頂元素應(yīng)為T-rchild，出棧，遍歷以該指針為根的子樹。
【算法1】
void PreOrder(BiTree T, Status ( *Visit ) (ElemType e))
{ // 基于方法一
InitStack(S);
while ( T!=NULL || !StackEmpty(S)){
while ( T != NULL ){
Visit(T-data) ;
Push(S,T);
T = T-lchild;
}
if( !StackEmpty(S) ){
Pop(S,T);
T = T-rchild;
}
}
}
【算法2】
void PreOrder(BiTree T, Status ( *Visit ) (ElemType e))
{ // 基于方法二
InitStack(S);
while ( T!=NULL || !StackEmpty(S) ){
while ( T != NULL ){
Visit(T-data);
Push(S, T-rchild);
T = T-lchild;
}
if ( !StackEmpty(S) ){
Pop(S,T);
}
}
}
進(jìn)一步考慮：對(duì)于處理流程中的循環(huán)體的直到型、當(dāng)型+直到型的實(shí)現(xiàn)。
中序非遞歸算法
【思路】
T是要遍歷樹的根指針，中序遍歷要求在遍歷完左子樹后，訪問根，再遍歷右子樹。
問題：如何用棧來保存信息，使得在中序遍歷過左子樹后，能利用棧頂信息獲取T指針？
方法：先將T入棧，遍歷左子樹；遍歷完左子樹返回時(shí)，棧頂元素應(yīng)為T，出棧，訪問T-data，再中序遍歷T的右子樹。
【算法】
void InOrder(BiTree T, Status ( *Visit ) (ElemType e))
{
InitStack(S);
while ( T!=NULL || !StackEmpty(S) ){
while ( T != NULL ){
Push(S,T);
T = T-lchild;
}
if( !StackEmpty(S) ){
Pop(S, T);
Visit(T-data);
T = T-rchild;
}
}
}
進(jìn)一步考慮：對(duì)于處理流程中的循環(huán)體的直到型、當(dāng)型+直到型的實(shí)現(xiàn)。
后序非遞歸算法
【思路】
T是要遍歷樹的根指針，后序遍歷要求在遍歷完左右子樹后，再訪問根。需要判斷根結(jié)點(diǎn)的左右子樹是否均遍歷過。
可采用標(biāo)記法，結(jié)點(diǎn)入棧時(shí)，配一個(gè)標(biāo)志tag一同入棧(0：遍歷左子樹前的現(xiàn)場(chǎng)保護(hù)，1：遍歷右子樹前的現(xiàn)場(chǎng)保護(hù))。
首先將T和tag(為0)入棧，遍歷左子樹；返回后，修改棧頂tag為1，遍歷右子樹；最后訪問根結(jié)點(diǎn)。 [Page]
typedef struct stackElement{
Bitree data;
char tag;
}stackElemType;
【算法】
void PostOrder(BiTree T, Status ( *Visit ) (ElemType e))
{
InitStack(S);
while ( T!=NULL || !StackEmpty(S) ){
while ( T != NULL ){
Push(S,T,0);
T = T-lchild;
}
while ( !StackEmpty(S) GetTopTag(S)==1){
Pop(S, T);
Visit(T-data);
}
if ( !StackEmpty(S) ){
SetTopTag(S, 1); // 設(shè)置棧頂標(biāo)記
T = GetTopPointer(S); // 取棧頂保存的指針
T = T-rchild;
}else break;
}
}
這是先序遍歷樹的代碼，什么是先序遍歷呢，一種按照根-左子樹-右子樹的順序遍歷樹就是先序遍歷。
CBTType TreeFindNode(CBTType treeNode,String data){
CBTType ptr;
if(treeNode==null){//輸入根節(jié)點(diǎn)為空時(shí)
return null;
}else{
if(treeNode.data.equals(data)){//根節(jié)點(diǎn)等于要查找的數(shù)據(jù)時(shí)
return treeNode;
}else{
if((ptr=TreeFindNode(treeNode.left,data))!=null){//從左子樹查找，為什么可以用TreeFindNode表示呢？
return ptr;
}else if((ptr=TreeFindNode(treeNode.right,data))!=null){//從右子樹查找
return ptr;
}else{
return null;
}
}
}
}
從左子樹查找，為什么可以用TreeFindNode表示呢？因?yàn)?，左子樹也可以按照先序遍歷的順序查找的，所以當(dāng)然可以用TreeFindNode表示，如果你想左子樹用中序遍歷查找，那么就不可以用TreeFindNode表示。
上述例子的查找過程：
1 --根（2，4，5）--左（3，6，7）--右
2--根（4）--左（5）--右
4--根
5--根
返回
import java.util.ArrayList;
// 樹的一個(gè)節(jié)點(diǎn)
class TreeNode {
Object _value = null; // 他的值
TreeNode _parent = null; // 他的父節(jié)點(diǎn)，根節(jié)點(diǎn)沒有PARENT
ArrayList _childList = new ArrayList(); // 他的孩子節(jié)點(diǎn)
public TreeNode( Object value, TreeNode parent ){
this._parent = parent;
this._value = value;
}
public TreeNode getParent(){
return _parent;
}
public String toString() {
return _value.toString();
}
}
public class Tree {
// 給出寬度優(yōu)先遍歷的值數(shù)組，構(gòu)建出一棵多叉樹
// null 值表示一個(gè)層次的結(jié)束
// "|" 表示一個(gè)層次中一個(gè)父親節(jié)點(diǎn)的孩子輸入結(jié)束
// 如：給定下面的值數(shù)組：
// { "root", null, "left", "right", null }
// 則構(gòu)建出一個(gè)根節(jié)點(diǎn)，帶有兩個(gè)孩子("left","right")的樹
public Tree( Object[] values ){
// 創(chuàng)建根
_root = new TreeNode( values[0], null );
// 創(chuàng)建下面的子節(jié)點(diǎn)
TreeNode currentParent = _root; // 用于待創(chuàng)建節(jié)點(diǎn)的父親
//TreeNode nextParent = null;
int currentChildIndex = 0; // 表示 currentParent 是他的父親的第幾個(gè)兒子
//TreeNode lastNode = null; // 最后一個(gè)創(chuàng)建出來的TreeNode，用于找到他的父親
for ( int i = 2; i values.length; i++ ){
// 如果null ,表示下一個(gè)節(jié)點(diǎn)的父親是當(dāng)前節(jié)點(diǎn)的父親的第一個(gè)孩子節(jié)點(diǎn)
if ( values[i] == null ){
currentParent = (TreeNode)currentParent._childList.get(0);
currentChildIndex = 0;
continue;
}
// 表示一個(gè)父節(jié)點(diǎn)的所有孩子輸入完畢
if ( values[i].equals("|") ){
if ( currentChildIndex+1 currentParent._childList.size() ){
currentChildIndex++;
currentParent = (TreeNode)currentParent._parent._childList.get(currentChildIndex);
}
continue;
}
TreeNode child = createChildNode( currentParent, values[i] );
}
}
TreeNode _root = null;
public TreeNode getRoot(){
return _root;
}
/**
// 按寬度優(yōu)先遍歷，打印出parent子樹所有的節(jié)點(diǎn)
private void printSteps( TreeNode parent, int currentDepth ){
for ( int i = 0; i parent._childList.size(); i++ ){
TreeNode child = (TreeNode)parent._childList.get(i);
System.out.println(currentDepth+":"+child);
}
if ( parent._childList.size() != 0 ) System.out.println(""+null);// 為了避免葉子節(jié)點(diǎn)也會(huì)打印null
//打印 parent 同層的節(jié)點(diǎn)的孩子
if ( parent._parent != null ){ // 不是root
int i = 1;
while ( i parent._parent._childList.size() ){// parent 的父親還有孩子
TreeNode current = (TreeNode)parent._parent._childList.get(i);
printSteps( current, currentDepth );
i++;
}
}
// 遞歸調(diào)用，打印所有節(jié)點(diǎn)
for ( int i = 0; i parent._childList.size(); i++ ){
TreeNode child = (TreeNode)parent._childList.get(i);
printSteps( child, currentDepth+1 );
}
}
// 按寬度優(yōu)先遍歷，打印出parent子樹所有的節(jié)點(diǎn)
public void printSteps(){
System.out.println(""+_root);
System.out.println(""+null);
printSteps(_root, 1 );
}**/
// 將給定的值做為 parent 的孩子，構(gòu)建節(jié)點(diǎn)
private TreeNode createChildNode( TreeNode parent, Object value ){
TreeNode child = new TreeNode( value , parent );
parent._childList.add( child );
return child;
}
public static void main(String[] args) {
Tree tree = new Tree( new Object[]{ "root", null,
"left", "right", null,
"l1","l2","l3", "|", "r1","r2",null } );
//tree.printSteps();
System.out.println(""+ ( (TreeNode)tree.getRoot()._childList.get(0) )._childList.get(0) );
System.out.println(""+ ( (TreeNode)tree.getRoot()._childList.get(0) )._childList.get(1) );
System.out.println(""+ ( (TreeNode)tree.getRoot()._childList.get(0) )._childList.get(2) );
System.out.println(""+ ( (TreeNode)tree.getRoot()._childList.get(1) )._childList.get(0) );
System.out.println(""+ ( (TreeNode)tree.getRoot()._childList.get(1) )._childList.get(1) );
}
}
java：二叉樹添加和查詢方法
package arrays.myArray;
public class BinaryTree {
private Node root;
// 添加數(shù)據(jù)
public void add(int data) {
// 遞歸調(diào)用
if (null == root)
root = new Node(data, null, null);
else
addTree(root, data);
}
private void addTree(Node rootNode, int data) {
// 添加到左邊
if (rootNode.data data) {
if (rootNode.left == null)
rootNode.left = new Node(data, null, null);
else
addTree(rootNode.left, data);
} else {
// 添加到右邊
if (rootNode.right == null)
rootNode.right = new Node(data, null, null);
else
addTree(rootNode.right, data);
}
}
// 查詢數(shù)據(jù)
public void show() {
showTree(root);
}
private void showTree(Node node) {
if (node.left != null) {
showTree(node.left);
}
System.out.println(node.data);
if (node.right != null) {
showTree(node.right);
}
}
}
class Node {
int data;
Node left;
Node right;
public Node(int data, Node left, Node right) {
this.data = data;
this.left = left;
this.right = right;
}
}
重慶分公司
重慶分公司
