數據結構c語言二叉樹的查找,數據結構c語言版二叉樹代碼

本文目錄一覽：

• 1、C語言寫二叉樹查找，幫忙給看看~不知道錯誤在哪裡
• 2、數據結構（二）：二叉搜索樹（Binary Search Tree）
• 3、數據結構C語言二叉樹
• 4、二叉樹結點的查找C語言實現

C語言寫二叉樹查找，幫忙給看看~不知道錯誤在哪裡

你的創建函數很有問題，人家一般兩種格式：

T = Creat();

或者：

Create(T); //T應該為指針，不應該為非指針

你怎麼把這兩種混用了？即是要麼在Create()里分配內存然後返回該樹的地址，要麼就是把T作為參數傳進入，再分配，但這種只能是把指針傳進去，不把指針傳進去不行，值傳遞該知道不會改變實參的內容吧？

還有，沒有分配到內存的判斷時，是應該退出的，你怎麼還繼續操作了呢？沒分配到內存再操作肯定會出現異常的

PS：本來想幫你改一下的，但複製粘貼到VS沒換行，用word改有點麻煩，你自己再改改吧

數據結構（二）：二叉搜索樹（Binary Search Tree）

二分法的查找過程是，在一個有序的序列中，每次都會選擇有效範圍中間位置的元素作判斷，即每次判斷後，都可以排除近一半的元素，直到查找到目標元素或返回不存在，所以 個有序元素構成的序列，查找的時間複雜度為 。既然線性結構能夠做到查詢複雜度為 級別，那二叉搜索樹產生又有何必要呢？畢竟二叉搜索樹的查詢複雜度只是介於 ~ 之間，並不存在查詢優勢。

二叉搜索樹是一種節點值之間具有一定數量級次序的二叉樹，對於樹中每個節點：

示例：

觀察二叉搜索樹結構可知，查詢每個節點需要的比較次數為節點深度加一。如深度為 0，節點值為 “6” 的根節點，只需要一次比較即可；深度為 1，節點值為 “3” 的節點，只需要兩次比較。即二叉樹節點個數確定的情況下，整顆樹的高度越低，節點的查詢複雜度越低。

【1】 完全二叉樹，所有節點盡量填滿樹的每一層，上一層填滿後還有剩餘節點的話，則由左向右盡量填滿下一層。如上圖BST所示，即為一顆完全二叉樹；

【2】每一層只有一個節點的二叉樹。如下圖SP_BST所示：

第【1】種情況下的查找次數分析：由上一章 二叉樹 可知，完美二叉樹中樹的深度與節點個數的關係為： 。設深度為 的完全二叉樹節點總數為 ，因為完全二叉樹中深度為 的葉子節點層不一定填滿，所以有 ，即： ，因為 為查找次數，所以完全二叉樹中查找次數為： 。

第【2】種情況下，樹中每層只有一個節點，該狀態的樹結構更傾向於一種線性結構，節點的查詢類似於數組的遍歷，查詢複雜度為 。

所以二叉搜索樹的查詢複雜度為 ~ 。

二叉搜索樹的構造過程，也就是將節點不斷插入到樹中適當位置的過程。該操作過程，與查詢節點元素的操作基本相同，不同之處在於：

由此可知，單個節點的構造複雜度和查詢複雜度相同，為 ~ 。

二叉搜索樹的節點刪除包括兩個過程，查找和刪除。查詢的過程和查詢複雜度已知，這裡說明一下刪除節點的過程。

第一種情況如下圖 s_1 所示，待刪除節點值為 “6”，該節點無子樹，刪除後並不影響二叉搜索樹的結構特性，可以直接刪除。即二叉搜索樹中待刪除節點度為零時，該節點為葉子節點，可以直接刪除；

第二種情況如下圖 s_2 所示，待刪除節點值為 “7”，該節點有一個左子樹，刪除節點後，為了維持二叉搜索樹結構特性，需要將左子樹“上移”到刪除的節點位置上。即二叉搜索樹中待刪除的節點度為一時，可以將待刪除節點的左子樹或右子樹“上移”到刪除節點位置上，以此來滿足二叉搜索樹的結構特性。

第三種情況如下圖 s_3 所示，待刪除節點值為 “9”，該節點既有左子樹，也有右子樹，刪除節點後，為了維持二叉搜索樹的結構特性，需要從其左子樹中選出一個最大值的節點，“上移”到刪除的節點位置上。即二叉搜索樹中待刪除節點的度為二時，可以將待刪除節點的左子樹中的最大值節點“移動”到刪除節點位置上，以此來滿足二叉搜索樹的結構特性。

之前提到二叉搜索樹中節點的刪除操作，包括查詢和刪除兩個過程，這裡稱刪除節點後，維持二叉搜索樹結構特性的操作為“穩定結構”操作，觀察以上三種情況可知：

由以上查詢複雜度、構造複雜度和刪除複雜度的分析可知，三種操作的時間複雜度皆為 ~ 。下面分析線性結構的三種操作複雜度，以二分法為例：

由此可知，二叉搜索樹相對於線性結構，在構造複雜度和刪除複雜度方面佔優；在查詢複雜度方面，二叉搜索樹可能存在類似於斜樹，每層上只有一個節點的情況，該情況下查詢複雜度不佔優勢。

二叉搜索樹的節點查詢、構造和刪除性能，與樹的高度相關，如果二叉搜索樹能夠更“平衡”一些，避免了樹結構向線性結構的傾斜，則能夠顯著降低時間複雜度。二叉搜索樹的存儲方面，相對於線性結構只需要保存元素值，樹中節點需要額外的空間保存節點之間的父子關係，所以在存儲消耗上要高於線性結構。

輸出結果為：

數據結構C語言二叉樹

層次遍歷應該沒有遞歸算法

遞歸實際就是一種深度優先的算法

而層次遍歷實際是廣度優先的遍歷算法，所以遞歸不適用

比如假設有遞歸算法，現遍歷i層的開始，對i層第一個元素遍歷後需調用遞歸函數遍歷其孩子，遞歸調用完成後才繼續遍歷i層第二個元素，這樣就不是層次遍歷了

二叉樹結點的查找C語言實現

#include stdio.h

#include stdlib.h

#include malloc.h

typedef struct bitnode

{

char data;

struct bitnode *lchild, *rchild;

}bitnode, *bitree;

void createbitree(t,n)

bitnode ** t;

int *n;

{

char x;

bitnode *q;

*n=*n+1;

printf(“\n Input %d DATA:”,*n);

x=getchar();

if(x!=’\n’) getchar();

if (x==’\n’)

return;

q=(bitnode*)malloc(sizeof(bitnode));

q-data=x;

q-lchild=NULL;

q-rchild=NULL;

*t=q;

printf(” This Address is: %o, Data is: %c,\n Left Pointer is: %o, Right Pointer is: %o”,q,q-data,q-lchild,q-rchild);

createbitree(q-lchild,n);

createbitree(q-rchild,n);

return;

}

void visit(e)

bitnode *e;

{

printf(” Address: %o, Data: %c, Left Pointer: %o, Right Pointer: %o\n”,e,e-data,e-lchild,e-rchild);

}

void preordertraverse(t)

bitnode *t;

{

if(t)

{

visit(t);

preordertraverse(t-lchild);

preordertraverse(t-rchild);

return ;

}else return ;

}

void countleaf(t,c)

bitnode *t;

int *c;

{

if(t!=NULL)

{

if (t-lchild==NULL t-rchild==NULL)

{*c=*c+1;

}

countleaf(t-lchild,c);

countleaf(t-rchild,c);

}

return;

}

int treehigh(t)

bitnode *t;

{int lh,rh,h;

if(t==NULL)

h=0;

else{

lh=treehigh(t-lchild);

rh=treehigh(t-rchild);

h=(lhrh ? lh:rh)+1;

}

return h;

}

main()

{

bitnode *t; int count=0;

int n=0;

printf(“\n Please input TREE Data:\n”);

createbitree(t,n);

printf(“\n This is TREE Struct: \n”);

preordertraverse(t);

countleaf(t,count);

printf(“\n This TREE has %d leaves “,count);

printf(” , High of The TREE is: %d\n”,treehigh(t));

}