1。最近從網易云課堂學習了一個老師的數據結構相關的知識，了解到數據結構的應用和二分查找之間的關系，就自己想著寫一個創建二叉順序數和利用棧對二叉順序樹進行順序輸出的代碼，終于一個周末的時間寫完了。

2.寫代碼的重點在于實現邏輯，由于遞歸思想和邏輯的混亂，代碼容易出現段錯誤或者，偶爾輸出一半的結果，梳理了好久，結合前序、中序輸出推導出樹的結構，從而尋找代碼問題的形式，終于搞定了

3.因此代碼思想遠比代碼實現更重要，而代碼的思想又需要扎實的基本功，繼續努力。。。，

?4.添加：二叉排序樹的查找，利用比較大小，判斷是在左右子樹位置，從而判斷有無

　 刪除：查找刪除位置，如果是葉子節點，修改其根節點的孩子指針，如果是根節點，將其左子樹最大、或者右子樹最小替換到該位置，刪除替換元素

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct _node{
int date;
struct _node * lchild;
struct _node * rchild;
struct _node * parent;
}btreenode;

void btreenode_add(btreenode * root,btreenode * temp){
btreenode *temproot = root; //根節點臨時變量

if(temp->date > temproot->date){ //對比節點數據域
if(temproot->rchild != NULL){ //尋找插入點
temproot = temproot->rchild;
btreenode_add(temproot,temp); //插入點不為空，遞歸調用
}
else
temproot->rchild = temp;
}
else{
if(temproot->lchild != NULL){
temproot = temproot->lchild;
btreenode_add(temproot,temp);
}
else
temproot->lchild = temp;
}

}

//二叉順序樹的創建
btreenode * btreenode_creat(int num){
if(num <= 0) return NULL; //創建節點數小于0退出

srand(time(NULL)); //隨機數函數，創建頭節點并初始化
btreenode * root = (btreenode *)malloc(sizeof(btreenode));
memset(root,'\0',sizeof(root));
root->date = rand()%100+1;

root->lchild = root->rchild = root->parent = NULL;

int i;
for(i=2;i<=num;i++){ //依次添加節點
btreenode * temp = (btreenode *)malloc(sizeof(btreenode));
memset(temp,'\0',sizeof(temp));
temp->date = (rand()%100+1);

btreenode_add(root,temp);//調用添加節點函數
}

return root; //返回根節點
}

//二叉樹的中序遍歷
void mid_show(btreenode * root){

if(root->lchild != NULL)
mid_show(root->lchild);

printf("%d ",root->date);

if(root->rchild != NULL)
mid_show(root->rchild);
}
//二叉樹的先序遍歷
void fir_show(btreenode * root){

printf("%d ",root->date);

if(root->lchild != NULL)
fir_show(root->lchild);

if(root->rchild != NULL)
fir_show(root->rchild);
}
typedef struct _linkstack{ //棧結構體
btreenode * node;
struct _linkstack *next;
}linkstack;

linkstack * create(){
linkstack * ls = (linkstack *)malloc(sizeof(linkstack));
memset(ls,'\0',sizeof(ls));
ls->next = NULL;
ls->node = NULL;

return ls;
}
int is_empty(linkstack * ls){
return ls->next ==NULL ? 1 : 0;
}

void push(linkstack * ls,btreenode *node){
linkstack * temp = create();
temp->node = node;

linkstack * lstemp = ls;
while(lstemp->next != NULL){ lstemp = lstemp->next;}
lstemp->next = temp;
}

linkstack * pop(linkstack * ls){
if(is_empty(ls)){
printf("stact_is_empty\n");
return NULL;
}

linkstack *temp,*p,*q;
temp = ls;
while(temp->next->next != NULL) temp =temp->next;
p = temp;
q = p->next;
p->next = NULL;
return q;
}

?

//二叉樹使用棧實現中序輸出
void stact_show(linkstack * ls,btreenode * root){
btreenode * temp = root;
push(ls,temp); //根節點壓棧
while(temp->lchild != NULL){ //左孩子不為空壓棧
temp = temp->lchild;
push(ls,temp);
}
while( !(is_empty(ls))){//棧非空出站

temp = pop(ls)->node;
printf("%d ",temp->date);
if(temp->rchild !=NULL) //出站節點有右孩子，遞歸調用自身壓棧出棧
stact_show(ls,temp->rchild);
}
}
int main(int argc, const char *argv[])
{
btreenode * root = btreenode_creat(10);
printf("1first show. ************************\n");
fir_show(root);
printf("\n");

printf("2.midddle show ************************\n");
mid_show(root);
printf("\n");

printf("3.stact_show ************************\n");
linkstack * ls = create();
stact_show(ls,root);
printf("\n");
return 0;
}

轉載于:https://www.cnblogs.com/huiji12321/p/11262880.html

總結

以上是生活随笔為你收集整理的step3 . day7数据结构之二叉顺序数的创建和二叉树的栈形式遍历的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。