建站
咨詢
售后
建站咨詢
新聞中心
求數(shù)據(jù)結構二叉樹查找結點及其父節(jié)點的代碼，謝謝?。。?/h2>
#includeiostream
成都創(chuàng)新互聯(lián)公司專注于新市網站建設服務及定制，我們擁有豐富的企業(yè)做網站經驗。 熱誠為您提供新市營銷型網站建設，新市網站制作、新市網頁設計、新市網站官網定制、小程序開發(fā)服務，打造新市網絡公司原創(chuàng)品牌,更為您提供新市網站排名全網營銷落地服務。
#includemap
using namespace std;
const int N=15e3+100;
struct node{
int v;//結點值
int l,r;//左右孩子的下標
st()
{//初始化
l=r=-1;
}
}tree[4*N];//4倍空間,用來儲存二叉樹
mapint,intmp;//儲存數(shù)值在數(shù)組a中的下標
int a[N];//基礎數(shù)組,數(shù)組tree在其基礎上建樹
int n=1;//1 5 8 0 0 0 6 0 0
void build_tree(int rt,int num)
{//構建二叉樹
if(a[num]==0)
{//a[num]==0,表示空結點
tree[rt].v=-1;
}
else
{
if(mp.count(a[num])==0)
mp[a[num]]=rt;//儲存a[num]在樹中的位置
tree[rt].v=a[num];//結點賦值
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++];//儲存結點值
}
while(getchar()!='\n');//回車結束輸入
build_tree(1,x);//構建二叉樹(結構體數(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;//左右孩子的下標除以2，就是父節(jié)點的下標
if(y==0)
{//父節(jié)點下標為0，既是根節(jié)點
cout0endl;
}
else
{//輸出父節(jié)點值
couttree[y].vendl;
}
}
return 0;
}
用JAVA語言實現(xiàn)二叉樹的層次遍歷的非遞歸算法及查找算法。
先序非遞歸算法
【思路】
假設：T是要遍歷樹的根指針，若T != NULL
對于非遞歸算法，引入棧模擬遞歸工作棧，初始時棧為空。
問題：如何用棧來保存信息，使得在先序遍歷過左子樹后，能利用棧頂信息獲取T的右子樹的根指針？
方法1：訪問T-data后，將T入棧，遍歷左子樹；遍歷完左子樹返回時，棧頂元素應為T，出棧，再先序遍歷T的右子樹。
方法2：訪問T-data后，將T-rchild入棧，遍歷左子樹；遍歷完左子樹返回時，棧頂元素應為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);
}
}
}
進一步考慮：對于處理流程中的循環(huán)體的直到型、當型+直到型的實現(xiàn)。
中序非遞歸算法
【思路】
T是要遍歷樹的根指針，中序遍歷要求在遍歷完左子樹后，訪問根，再遍歷右子樹。
問題：如何用棧來保存信息，使得在中序遍歷過左子樹后，能利用棧頂信息獲取T指針？
方法：先將T入棧，遍歷左子樹；遍歷完左子樹返回時，棧頂元素應為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;
}
}
}
進一步考慮：對于處理流程中的循環(huán)體的直到型、當型+直到型的實現(xiàn)。
后序非遞歸算法
【思路】
T是要遍歷樹的根指針，后序遍歷要求在遍歷完左右子樹后，再訪問根。需要判斷根結點的左右子樹是否均遍歷過。
可采用標記法，結點入棧時，配一個標志tag一同入棧(0：遍歷左子樹前的現(xiàn)場保護，1：遍歷右子樹前的現(xiàn)場保護)。
首先將T和tag(為0)入棧，遍歷左子樹；返回后，修改棧頂tag為1，遍歷右子樹；最后訪問根結點。 [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); // 設置棧頂標記
T = GetTopPointer(S); // 取棧頂保存的指針
T = T-rchild;
}else break;
}
}
java數(shù)據(jù)結構二叉樹查找結點操作，遞歸調用求詳細講解
這是先序遍歷樹的代碼，什么是先序遍歷呢，一種按照根-左子樹-右子樹的順序遍歷樹就是先序遍歷。
CBTType TreeFindNode(CBTType treeNode,String data){
CBTType ptr;
if(treeNode==null){//輸入根節(jié)點為空時
return null;
}else{
if(treeNode.data.equals(data)){//根節(jié)點等于要查找的數(shù)據(jù)時
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表示呢？因為，左子樹也可以按照先序遍歷的順序查找的，所以當然可以用TreeFindNode表示，如果你想左子樹用中序遍歷查找，那么就不可以用TreeFindNode表示。
上述例子的查找過程：
1 --根（2，4，5）--左（3，6，7）--右
2--根（4）--左（5）--右
4--根
5--根
返回
建立一個二叉樹，附帶查詢代碼，JAVA代碼
import java.util.ArrayList;
// 樹的一個節(jié)點
class TreeNode {
Object _value = null; // 他的值
TreeNode _parent = null; // 他的父節(jié)點，根節(jié)點沒有PARENT
ArrayList _childList = new ArrayList(); // 他的孩子節(jié)點
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ù)組，構建出一棵多叉樹
// null 值表示一個層次的結束
// "|" 表示一個層次中一個父親節(jié)點的孩子輸入結束
// 如：給定下面的值數(shù)組：
// { "root", null, "left", "right", null }
// 則構建出一個根節(jié)點，帶有兩個孩子("left","right")的樹
public Tree( Object[] values ){
// 創(chuàng)建根
_root = new TreeNode( values[0], null );
// 創(chuàng)建下面的子節(jié)點
TreeNode currentParent = _root; // 用于待創(chuàng)建節(jié)點的父親
//TreeNode nextParent = null;
int currentChildIndex = 0; // 表示 currentParent 是他的父親的第幾個兒子
//TreeNode lastNode = null; // 最后一個創(chuàng)建出來的TreeNode，用于找到他的父親
for ( int i = 2; i values.length; i++ ){
// 如果null ,表示下一個節(jié)點的父親是當前節(jié)點的父親的第一個孩子節(jié)點
if ( values[i] == null ){
currentParent = (TreeNode)currentParent._childList.get(0);
currentChildIndex = 0;
continue;
}
// 表示一個父節(jié)點的所有孩子輸入完畢
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é)點
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é)點也會打印null
//打印 parent 同層的節(jié)點的孩子
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++;
}
}
// 遞歸調用，打印所有節(jié)點
for ( int i = 0; i parent._childList.size(); i++ ){
TreeNode child = (TreeNode)parent._childList.get(i);
printSteps( child, currentDepth+1 );
}
}
// 按寬度優(yōu)先遍歷，打印出parent子樹所有的節(jié)點
public void printSteps(){
System.out.println(""+_root);
System.out.println(""+null);
printSteps(_root, 1 );
}**/
// 將給定的值做為 parent 的孩子，構建節(jié)點
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) {
// 遞歸調用
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;
}
}
當前文章：二叉樹查找代碼java 二叉樹的查詢方式
本文來源：http://fisionsoft.com.cn/article/hihejp.html
