Rhythmli's blog
梁山话事人
最新推荐文章2026-08-01

二叉树，栈存储及遍历小程序

原文链接：https://blog.csdn.net/qq_39355828/article/details/110842777 (opens new window) 1.容器

#include<iostream>
#include<vector>
#include<string>
using namespace std;
int main()
{
vector<string>a;//定义一个容器
string tmp;//定义一个字符串
while(cin>>tmp)//将字符串不断放入容器
{
	a.push_back(tmp);
}
for(vector<string>::iterator iter=a.begin();iter!=a.end();++iter)//定义一个迭代器
{
	cout<<*iter<<endl;
}
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2.二叉树的顺序存储

#include<stdio.h>
#include<conio.h>
#define MAX_SIZE 1024
//定义顺序树类型
typedef char SeqTree[MAX_SIZE];
void InitSeqTree(SeqTree tree); //初始化空二叉树
void CreatSeqTree(SeqTree tree , int i); //i为数组的下标
void InitSeqTree(SeqTree tree)
{
	//将字符数组中的所有元素初始化赋值
	for(int i = 0 ; i < MAX_SIZE ; i++ )
	{
		tree[i] = '\0';
	}

}
void CreatSeqTree(SeqTree tree , int i)
{
	char ch;
	ch = getchar();
	fflush(stdin); //清空键盘缓存区
	if(ch == '^'){ //当输入^时结束节点输入
	    tree[i] = '\0';
		return;
	}
	tree[i] = ch;
    //建立完节点提示输入左子树和右子树
	printf("请输入左子树：\n");
	CreatSeqTree(tree , 2 * i + 1);
	printf("请输入右子树：\n");
	CreatSeqTree(tree , 2 * (i + 1));
}

void PrintSeqTree(SeqTree tree)
{
	for(int i = 0 ; i < MAX_SIZE ; i++)
	{
		printf("%c",tree[i]);
	}
}

int main()
{
	SeqTree tree;
	InitSeqTree(tree);
	printf("请输入根节点内容：");
	CreatSeqTree(tree,0);
	PrintSeqTree(tree);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

3.二叉树的链式存储

#include<stdio.h>
#include<conio.h>
#include <stdlib.h>
#define MAX_SIZE 1024
typedef int TElemType;
typedef struct BiTNode
{
    TElemType data;
    struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;
void CreateBiTree(BiTree *T)
{
    *T=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->data=1;
    (*T)->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->lchild->data=2;
    (*T)->rchild=NULL;
    (*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->lchild->rchild=NULL;
    (*T)->lchild->lchild->data=3;
    (*T)->lchild->lchild->lchild=NULL;
    (*T)->lchild->lchild->rchild=NULL;
}
int main()
{
    BiTree Tree;
    CreateBiTree(&Tree);
    printf("%d",Tree->lchild->lchild->data);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

3.二叉树的遍历

#include<stdio.h>
#include<stdlib.h>
typedef struct BiTNode
{
    char data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
void PreOrderTraverse(BiTree T)//二叉树的先序遍历
{
    if(T==NULL)
        return ;
    printf("%c ",T->data);
    PreOrderTraverse(T->lchild);
    PreOrderTraverse(T->rchild);
}
void InOrderTraverse(BiTree T)//二叉树的中序遍历
{
   if(T==NULL)
       return ;
   InOrderTraverse(T->lchild);
    printf("%c ",T->data);
   InOrderTraverse(T->rchild);
}
void PostOrderTraverse(BiTree T)//后序遍历
{
    if(T==NULL)
        return;
    PostOrderTraverse(T->lchild);
    PostOrderTraverse(T->rchild);
    printf("%c ",T->data);
}
void CreateBiTree(BiTree *T)
{
    char ch;
    scanf("%c",&ch);
    if(ch=='#')
        *T=NULL;
    else
    {
        *T=(BiTree  )malloc(sizeof(BiTNode));
        if(!*T)
            exit(-1);
        (*T)->data=ch;
        CreateBiTree(&(*T)->lchild);
        CreateBiTree(&(*T)->rchild);
    }
}
int main()
{
    BiTree T;
    CreateBiTree(&T);
    PreOrderTraverse (T);
    InOrderTraverse(T);
    PostOrderTraverse(T);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

4.栈

//头文件
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<malloc.h>

//宏定义
#define  TRUE  1
#define  FALSE 0
#define  OK    1
#define  ERROR 0
#define  INFEASIBLE -1
#define  OVERFLOW   -2
#define  STACK_INIT_SIZE  100
#define  STACKINCREMENT    10
typedef  int  ElemType;
typedef  int    Status;

//栈的顺序结构表示
typedef struct
{
    ElemType *base;
    ElemType  *top;
    int  stacksize;
}SqStack;

//1.构建一个空栈
Status InitStack(SqStack &S)
{
    S.base = (ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));
    if (!S.base)
        exit(OVERFLOW);//存储分配失败
    S.top = S.base;
    S.stacksize = STACK_INIT_SIZE;
    return OK;
}

//2.销毁栈
Status DestroyStack(SqStack &S)
{
    S.top = NULL;
    S.stacksize = 0;
    free(S.base);
    return OK;
}

//3.清空栈
Status ClearStack(SqStack &S)
{
    S.top = S.base;
    return OK;
}

//4.判断栈是否为空
Status StackEmpty(SqStack S)
{
    if (S.top == S.base)
        return ERROR;
    else
        return TRUE;
}

//5.求栈的长度
Status StackLength(SqStack S)
{
    if (S.top == S.base)
        return FALSE;
    else
        return (S.top - S.base);//也可以直接返回S.top - S.base
}

//6.//求栈顶元素
Status GetTop(SqStack S, ElemType &e)
{
    if (S.top == S.base)
        return FALSE;
    else
        e = *(S.top - 1);
    return e;
}
//7.栈顶插入元素
Status Push(SqStack &S, ElemType &e)
{
    if (S.top - S.base >= STACK_INIT_SIZE)
    {
        S.base = (ElemType *)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(ElemType));
        if (!S.base)
        {
            return false;
        }
        S.top = S.base + STACK_INIT_SIZE;//栈底地址可能改变，重新定位栈顶元素
        S.stacksize = S.stacksize + STACKINCREMENT;
    }
    *S.top = e;
    S.top++;
    return OK;
}

//8.删除栈顶元素
Status Pop(SqStack &S, ElemType &e)
{
    if (S.top == S.base)
        return ERROR;
    else
    {
        S.top--;
        e = *S.top;//说明：此处容易使人迷惑，实际上此元素并没真正删除，仍在S.top中，但是如果插入元素，就会被更新，就像是删除了一样
        return e;
    }
}

//9.遍历栈
Status StackTraverse(SqStack S)
{
    if (S.base == NULL)
        return ERROR;
    if (S.top == S.base)
        printf("栈中没有元素……\n");
    ElemType *p;
    p = S.top;
    while (p > S.base)
    {
        p--;
        printf("%d ",*p);
    }

    return OK;
}

//主函数检验九种操作
int main()
{
    SqStack S;
    printf("构造一个空栈……\n");
    InitStack(S);
    int i,n ;
    printf("输入栈的长度:\n");
    scanf("%d",&n);
    for (i = 1; i <= n; i++)
    {
        printf("输入栈的第%d个元素\n",i);
        ++S.top;
        scanf("%d",S.top-1);
    }
     printf("……本栈是空栈吗？？……\n");
    if (StackEmpty(S) == 1)
         printf("NO !!!\n");
    else
         printf("YES !!!\n");
     printf("……求出栈的长度……\n");
    int m;
    m = StackLength(S);
     printf("栈的长度是:\n");
     printf("%d\n",m);
     printf("遍历输出栈中的所有元素:\n");
    StackTraverse(S);
     printf("\n");
     printf("……输出栈顶元素……\n");
    int e;
    e = GetTop(S, e);
     printf("栈顶元素是:\n");
     printf("%d\n",e);
     printf("……栈顶插入元素……\n");
     printf("请输入要插入的元素的数值:\n");
    scanf("%d",&e);
    Push(S,e);
     printf("现在栈中的元素是:\n");
    StackTraverse(S);
     printf("\n");
     printf("……栈顶删除元素……\n");
    e = Pop(S,e);
     printf("被删除的元素是:\n");
    scanf("%d",&e);
     printf("现在栈中的元素是:\n");
    StackTraverse(S);
     printf("\n");
     printf("……清空栈……\n");
    ClearStack(S);
     printf("现在栈中的元素是:\n");
    StackTraverse(S);
     printf("……销毁栈……\n");
    if(DestroyStack(S)==1)
         printf("销毁栈成功\n");
    else
         printf("销毁栈失败\n");
     printf("喜您成功完成所有的功能,毕竟您那么帅!!!\n");
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188

5.排序二叉树

/*遍历，*/
    BSTNode *BST_Search(BoTriTree T,ElemType e,BSTNode *&p)
{
p=NULL;
while(T!=NULL&&key!=T->data)
{
p=T;
if(key<T->data)
T=T->lchild;
else
T=T->rchild;
}
return T;
}
/*插入*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
编辑 (opens new window)
#设计模式与算法#订阅专栏#查看详情
上次更新: 2026/08/11, 13:36:18
《C和指针》简单学习笔记
数据结构简单学习笔记

← 数据结构简单学习笔记→

最近更新
01
Spring IOC
03-31
02
Git修改分支名
08-11
03
CSS给table的tbody添加滚动条
06-29
更多文章>
Theme by Vdoing | Copyright © 2019-2026 Evan Xu | MIT License