c二叉樹的遍歷演算法

❶ 急求c語言寫二叉樹的遍歷

BinaryTree.h:

/********************************************************************
created: 2006/07/04
filename: BinaryTree.h
author: 李創
http://www.cppblog.com/converse/

purpose: 演示二叉樹的演算法
*********************************************************************/

#ifndef BinaryTree_H
#define BinaryTree_H

＃i nclude <stdlib.h>
＃i nclude <stack>

class BinaryTree
{
private:
typedef int Item;
typedef struct TreeNode
{
Item Node;
TreeNode* pRight;
TreeNode* pLeft;

TreeNode(Item node = 0, TreeNode* pright = NULL, TreeNode* pleft = NULL)
: Node(node)
, pRight(pright)
, pLeft(pleft)
{
}

}TreeNode, *PTreeNode;

public:
enum TraverseType
{
PREORDER = 0, // 前序
INORDER = 1, // 中序
POSTORDER = 2, // 後序
LEVELORDER = 3 // 層序
};

BinaryTree(Item Array[], int nLength);
~BinaryTree();

PTreeNode GetRoot()
{
return m_pRoot;
}

// 遍歷樹的對外介面
// 指定遍歷類型和是否是非遞歸遍歷,默認是遞歸遍歷
void Traverse(TraverseType traversetype, bool bRec = true);

private:
PTreeNode CreateTreeImpl(Item Array[], int nLength);
void DetroyTreeImpl(PTreeNode pTreenode);

void PreTraverseImpl(PTreeNode pTreenode); // 遞歸前序遍歷樹
void InTraverseImpl(PTreeNode pTreenode); // 遞歸中序遍歷樹
void PostTraverseImpl(PTreeNode pTreenode); // 遞歸後序遍歷樹

void NoRecPreTraverseImpl(PTreeNode pTreenode); // 非遞歸前序遍歷樹
void NoRecInTraverseImpl(PTreeNode pTreenode); // 非遞歸中序遍歷樹
void NoRecPostTraverseImpl(PTreeNode pTreenode); // 非遞歸後序遍歷樹

void LevelTraverseImpl(PTreeNode pTreenode);

PTreeNode m_pRoot; // 根結點

// 採用STL裡面的stack作為模擬保存鏈表結點的stack容器
typedef std::stack<BinaryTree::PTreeNode> TreeNodeStack;
};

#endif

BinaryTree.cpp:

/********************************************************************
created: 2006/07/04
filename: BinaryTree.cpp
author: 李創
http://www.cppblog.com/converse/

purpose: 演示二叉樹的演算法
*********************************************************************/

＃i nclude <iostream>
＃i nclude <assert.h>
＃i nclude <queue>
＃i nclude "BinaryTree.h"

BinaryTree::BinaryTree(Item Array[], int nLength)
: m_pRoot(NULL)
{
assert(NULL != Array);
assert(nLength > 0);

m_pRoot = CreateTreeImpl(Array, nLength);
}

BinaryTree::~BinaryTree()
{
DetroyTreeImpl(m_pRoot);
}

// 按照中序遞歸創建樹
BinaryTree::PTreeNode BinaryTree::CreateTreeImpl(Item Array[], int nLength)
{
int mid = nLength / 2;
PTreeNode p = new TreeNode(Array[mid]);

if (nLength > 1)
{
p->pLeft = CreateTreeImpl(Array, nLength / 2);
p->pRight = CreateTreeImpl(Array + mid + 1, nLength / 2 - 1);
}

return p;
}

void BinaryTree::DetroyTreeImpl(PTreeNode pTreenode)
{
if (NULL != pTreenode->pLeft)
{
DetroyTreeImpl(pTreenode->pLeft);
}
if (NULL != pTreenode->pRight)
{
DetroyTreeImpl(pTreenode->pRight);
}

delete pTreenode;
pTreenode = NULL;
}

// 遍歷樹的對外介面
// 指定遍歷類型和是否是非遞歸遍歷,默認是遞歸遍歷
void BinaryTree::Traverse(TraverseType traversetype, bool bRec /*= true*/)
{
switch (traversetype)
{
case PREORDER: // 前序
{
if (true == bRec)
{
std::cout << "遞歸前序遍歷樹\n";
PreTraverseImpl(m_pRoot);
}
else
{
std::cout << "非遞歸前序遍歷樹\n";
NoRecPreTraverseImpl(m_pRoot);
}
}
break;

case INORDER: // 中序
{
if (true == bRec)
{
std::cout << "遞歸中序遍歷樹\n";
InTraverseImpl(m_pRoot);
}
else
{
std::cout << "非遞歸中序遍歷樹\n";
NoRecInTraverseImpl(m_pRoot);
}
}
break;

case POSTORDER: // 後序
{
if (true == bRec)
{
std::cout << "遞歸後序遍歷樹\n";
PostTraverseImpl(m_pRoot);
}
else
{
std::cout << "非遞歸後序遍歷樹\n";
NoRecPostTraverseImpl(m_pRoot);
}
}
break;

case LEVELORDER: // 層序
{
std::cout << "層序遍歷樹\n";
LevelTraverseImpl(m_pRoot);
}
}

std::cout << std::endl;
}

// 遞歸前序遍歷樹
void BinaryTree::PreTraverseImpl(PTreeNode pTreenode)
{
if (NULL == pTreenode)
return;

std::cout << "Item = " << pTreenode->Node << std::endl;

PreTraverseImpl(pTreenode->pLeft);

PreTraverseImpl(pTreenode->pRight);
}

// 非遞歸前序遍歷樹
void BinaryTree::NoRecPreTraverseImpl(PTreeNode pTreenode)
{
if (NULL == pTreenode)
return;

TreeNodeStack NodeStack;
PTreeNode pNode;
NodeStack.push(pTreenode);

while (!NodeStack.empty())
{
while (NULL != (pNode = NodeStack.top())) // 向左走到盡頭
{
std::cout << "Item = " << pNode->Node << std::endl; // 訪問當前結點
NodeStack.push(pNode->pLeft); // 左子樹根結點入棧
}
NodeStack.pop(); // 左子樹根結點退

棧
if (!NodeStack.empty())
{
pNode = NodeStack.top();
NodeStack.pop(); // 當前結點退棧
NodeStack.push(pNode->pRight); // 當前結點的右子樹根結點入棧
}
}
}

// 中序遍歷樹
// 中序遍歷輸出的結果應該和用來初始化樹的數組的排列順序一致
void BinaryTree::InTraverseImpl(PTreeNode pTreenode)
{
if (NULL == pTreenode)
return;

if (NULL != pTreenode->pLeft)
{
InTraverseImpl(pTreenode->pLeft);
}

std::cout << "Item = " << pTreenode->Node << std::endl;

if (NULL != pTreenode->pRight)
{
InTraverseImpl(pTreenode->pRight);
}
}

// 非遞歸中序遍歷樹
void BinaryTree::NoRecInTraverseImpl(PTreeNode pTreenode)
{
if (NULL == pTreenode)
return;

TreeNodeStack NodeStack;
PTreeNode pNode;
NodeStack.push(pTreenode);

while (!NodeStack.empty())
{
while (NULL != (pNode = NodeStack.top())) // 向左走到盡頭
{
NodeStack.push(pNode->pLeft);
}

NodeStack.pop();

if (!NodeStack.empty() && NULL != (pNode = NodeStack.top()))
{
std::cout << "Item = " << pNode->Node << std::endl;
NodeStack.pop();
NodeStack.push(pNode->pRight);
}
}
}

// 後序遍歷樹
void BinaryTree::PostTraverseImpl(PTreeNode pTreenode)
{
if (NULL == pTreenode)
return;

if (NULL != pTreenode->pLeft)
{
PostTraverseImpl(pTreenode->pLeft);
}

if (NULL != pTreenode->pRight)
{
PostTraverseImpl(pTreenode->pRight);
}

std::cout << "Item = " << pTreenode->Node << std::endl;
}

// 非遞歸後序遍歷樹
void BinaryTree::NoRecPostTraverseImpl(PTreeNode pTreenode)
{
if (NULL == pTreenode)
return;

TreeNodeStack NodeStack;
PTreeNode pNode1, pNode2;
NodeStack.push(pTreenode);
pNode1 = pTreenode->pLeft;

bool bVisitRoot = false; // 標志位,是否訪問過根結點
while (!NodeStack.empty())
{
while (NULL != pNode1) // 向左走到盡頭
{
NodeStack.push(pNode1);
pNode1 = pNode1->pLeft;
}

pNode1 = NodeStack.top();
NodeStack.pop();

if (NULL == pNode1->pRight) // 如果沒有右子樹就是葉子結點
{
std::cout << "Item = " << pNode1->Node << std::endl;
pNode2 = pNode1;
pNode1 = NodeStack.top();

if (pNode2 == pNode1->pRight) // 如果這個葉子結點是右子樹
{
std::cout << "Item = " << pNode1->Node << std::endl;
NodeStack.pop();
pNode1 = NULL;
}
else // 否則訪問右子樹
{
pNode1 = pNode1->pRight;
}
}
else // 訪問右子樹
{
if (pNode1 == pTreenode && true == bVisitRoot) // 如果已經訪問過右子樹那麼就退出
{
std::cout << "Item = " << pNode1->Node << std::endl;
return;
}
else
{
if (pNode1 == pTreenode)
{
bVisitRoot = true;
}

NodeStack.push(pNode1);
pNode1 = pNode1->pRight;
}
}
}
}

// 按照樹的層次從左到右訪問樹的結點
void BinaryTree::LevelTraverseImpl(PTreeNode pTreenode)
{
if (NULL == pTreenode)
return;

// 層序遍歷用於保存結點的容器是隊列
std::queue<PTreeNode> NodeQueue;
PTreeNode pNode;
NodeQueue.push(pTreenode);

while (!NodeQueue.empty())
{
pNode = NodeQueue.front();
NodeQueue.pop();
std::cout << "Item = " << pNode->Node << std::endl;

if (NULL != pNode->pLeft)
{
NodeQueue.push(pNode->pLeft);
}
if (NULL != pNode->pRight)
{
NodeQueue.push(pNode->pRight);
}
}
}

main.cpp

/********************************************************************
created: 2006/07/04
filename: main.cpp
author: 李創
http://www.cppblog.com/converse/

purpose: 測試二叉樹的演算法
*********************************************************************/

＃i nclude "BinaryTree.h"

＃i nclude <stdio.h>
＃i nclude <stdlib.h>
＃i nclude <time.h>
＃i nclude <iostream>

void DisplayArray(int array[], int length)
{
int i;

for (i = 0; i < length; i++)
{
printf("array[%d] = %d\n", i, array[i]);
}
}

void CreateNewArray(int array[], int length)
{
for (int i = 0; i < length; i++)
{
array[i] = rand() % 256 + i;
}
}

int main()
{
int array[10];
srand(time(NULL));

// 創建數組
CreateNewArray(array, 10);
DisplayArray(array, 10);

BinaryTree *pTree = new BinaryTree(array, 10);

// 測試前序遍歷
pTree->Traverse(BinaryTree::PREORDER);
std::cout << "root = " << pTree->GetRoot()->Node << std::endl;
std::cout << "root->left = " << pTree->GetRoot()->pLeft->Node << std::endl;
std::cout << "root->right = " << pTree->GetRoot()->pRight->Node << std::endl;
pTree->Traverse(BinaryTree::PREORDER, false);

// 測試中序遍歷
pTree->Traverse(BinaryTree::INORDER);
std::cout << "root = " << pTree->GetRoot()->Node << std::endl;
std::cout << "root->left = " << pTree->GetRoot()->pLeft->Node << std::endl;
std::cout << "root->right = " << pTree->GetRoot()->pRight->Node << std::endl;
pTree->Traverse(BinaryTree::INORDER, false);
// 測試後序遍歷
pTree->Traverse(BinaryTree::POSTORDER);
std::cout << "root = " << pTree->GetRoot()->Node << std::endl;
std::cout << "root->left = " << pTree->GetRoot()->pLeft->Node << std::endl;
std::cout << "root->right = " << pTree->GetRoot()->pRight->Node << std::endl;
pTree->Traverse(BinaryTree::POSTORDER, false);
// 測試層序遍歷
pTree->Traverse(BinaryTree::LEVELORDER);

system("pause");

delete pTree;

return 0;
}

❷ 二叉樹前序遍歷法舉例!急急急！！！

二叉樹的三種金典遍歷法

1.前序遍歷法：

前序遍歷（DLR）

前序遍歷（DLR）

前序遍歷首先訪問根結點然後遍歷左子樹，最後遍歷右子樹。在遍歷左、右子樹時，仍然先訪問根結點，然後遍歷左子樹，最後遍歷右子樹。

若二叉樹為空則結束返回，否則：

（1）訪問根結點

（2）前序遍歷左子樹

（3）前序遍歷右子樹

注意的是：遍歷左右子樹時仍然採用前序遍歷方法。

如上圖所示二叉樹

前序遍歷，也叫先根遍歷，遍歷的順序是，根，左子樹，右子樹

遍歷結果：ABDECF

中序遍歷，也叫中根遍歷，順序是左子樹，根，右子樹

遍歷結果：DBEAFC

後序遍歷，也叫後根遍歷，遍歷順序，左子樹，右子樹，根

遍歷結果：DEBFCA

2.中序遍歷法：

中序遍歷

中序遍歷（LDR）

中序遍歷首先遍歷左子樹，然後訪問根結點，最後遍歷右子樹。在遍歷左、右子樹時，仍然先遍歷左子樹，再訪問根結點，最後遍歷右子樹。即：

若二叉樹為空則結束返回，否則：

（1）中序遍歷左子樹

（2）訪問根結點

（3）中序遍歷右子樹。

注意的是：遍歷左右子樹時仍然採用中序遍歷方法。

3.後序遍歷法：

後序遍歷

簡介

後序遍歷是二叉樹遍歷的一種。後序遍歷指在訪問根結點、遍歷左子樹與遍歷右子樹三者中，首先遍歷左子樹，然後遍歷右子樹，最後遍歷訪問根結點，在遍歷左、右子樹時，仍然先遍歷左子樹，然後遍歷右子樹，最後遍歷根結點。後序遍歷有遞歸演算法和非遞歸演算法兩種。

遞歸演算法

演算法描述：

（1）若二叉樹為空，結束

（2）後序遍歷左子樹

（3）後序遍歷右子樹

（4）訪問根結點

偽代碼

PROCEDUREPOSTRAV(BT)

IFBT<>0THEN

{

POSTRAV(L(BT))

POSTRAV(R(BT))

OUTPUTV(BT)

}

RETURN

c語言描述

structbtnode

{

intd;

structbtnode*lchild;

structbtnode*rchild;

};

voidpostrav(structbtnode*bt)

{

if(bt!=NULL)

{

postrav(bt->lchild);

postrav(bt->rchild);

printf("%d",bt->d);

}

}

非遞歸演算法

演算法1（c語言描述）：

voidpostrav1(structbtnode*bt)

{

structbtnode*p;

struct

{

structbtnode*pt;

inttag;

}st[MaxSize];

}

inttop=-1;

top++;

st[top].pt=bt;

st[top].tag=1;

while(top>-1)/*棧不為空*/

{

if(st[top].tag==1)/*不能直接訪問的情況*/

{

p=st[top].pt;

top--;

if(p!=NULL)

{

top++;/*根結點*/

st[top].pt=p;

st[top].tag=0;

top++;/*右孩子結點*/

st[top].pt=p->p->rchild;

st[top].tag=1;

top++;/*左孩子結點*/

st[top].pt=p->lchild;

st[top].tag=1;

}

}

if(st[top].tag==0)/*直接訪問的情況*/

{

printf("%d",st[top].pt->d);

top--;

}

}

}

演算法2：

voidpostrav2(structbtnode*bt)

{

structbtnode*st[MaxSize],*p;

intflag,top=-1;

if(bt!=NULL)

{

do

{

while(bt!=NULL)

{

top++;

st[top]=bt;

bt=bt->lchild;

}

p=NULL;

flag=1;

while(top!=-1&&flag)

{

bt=st[top];

if(bt->rchild==p)

{

printf("%d",bt->d);

top--;

p=bt;

}

else

{

bt=bt->rchild;

flag=0;

}

}

}while(top!=-1)

printf(" ");

}

}

老曹回答必屬佳作記得給分謝謝合作！

❸ 二叉樹的層次遍歷演算法

二叉樹的層次遍歷演算法有如下三種方法：

給定一棵二叉樹，要求進行分層遍歷，每層的節點值單獨列印一行，下圖給出事例結構：

之後大家就可以自己畫圖了，下面給出程序代碼：

[cpp] view plain

void print_by_level_3(Tree T) {

vector<tree_node_t*> vec;

vec.push_back(T);

int cur = 0;

int end = 1;

while (cur < vec.size()) {

end = vec.size();

while (cur < end) {

cout << vec[cur]->data << " ";

if (vec[cur]->lchild)

vec.push_back(vec[cur]->lchild);

if (vec[cur]->rchild)

vec.push_back(vec[cur]->rchild);

cur++;

}

cout << endl;

}

}

最後給出完成代碼的測試用例：124##57##8##3#6##

[cpp] view plain

#include<iostream>

#include<vector>

#include<deque>

using namespace std;

typedef struct tree_node_s {

char data;

struct tree_node_s *lchild;

struct tree_node_s *rchild;

}tree_node_t, *Tree;

void create_tree(Tree *T) {

char c = getchar();

if (c == '#') {

*T = NULL;

} else {

*T = (tree_node_t*)malloc(sizeof(tree_node_t));

(*T)->data = c;

create_tree(&(*T)->lchild);

create_tree(&(*T)->rchild);

}

}

void print_tree(Tree T) {

if (T) {

cout << T->data << " ";

print_tree(T->lchild);

print_tree(T->rchild);

}

}

int print_at_level(Tree T, int level) {

if (!T || level < 0)

return 0;

if (0 == level) {

cout << T->data << " ";

return 1;

}

return print_at_level(T->lchild, level - 1) + print_at_level(T->rchild, level - 1);

}

void print_by_level_1(Tree T) {

int i = 0;

for (i = 0; ; i++) {

if (!print_at_level(T, i))

break;

}

cout << endl;

}

void print_by_level_2(Tree T) {

deque<tree_node_t*> q_first, q_second;

q_first.push_back(T);

while(!q_first.empty()) {

while (!q_first.empty()) {

tree_node_t *temp = q_first.front();

q_first.pop_front();

cout << temp->data << " ";

if (temp->lchild)

q_second.push_back(temp->lchild);

if (temp->rchild)

q_second.push_back(temp->rchild);

}

cout << endl;

q_first.swap(q_second);

}

}

void print_by_level_3(Tree T) {

vector<tree_node_t*> vec;

vec.push_back(T);

int cur = 0;

int end = 1;

while (cur < vec.size()) {

end = vec.size();

while (cur < end) {

cout << vec[cur]->data << " ";

if (vec[cur]->lchild)

vec.push_back(vec[cur]->lchild);

if (vec[cur]->rchild)

vec.push_back(vec[cur]->rchild);

cur++;

}

cout << endl;

}

}

int main(int argc, char *argv[]) {

Tree T = NULL;

create_tree(&T);

print_tree(T);

cout << endl;

print_by_level_3(T);

cin.get();

cin.get();

return 0;

}

❹ 設二叉樹以二叉鏈表存儲，試設計演算法，實現二叉樹的層序遍歷。

按層次遍歷演算法如下：
#include <iostream>
using namespace std;

typedef struct treenode { //樹結點結構
int data;
struct treenode *left;
struct treenode *right;
}TreeNode;

typedef struct stack{ //棧結點結構
TreeNode *node;
struct stack *next;
}STACK;

void Traversal(TreeNode *root)
{
STACK *head = NULL;
STACK *tail = NULL;
if (root != NULL) //根結點入棧
{
head = new STACK();
head->next = NULL;
head->node = root;
tail = head;
}
while(head != NULL)
{
STACK *temp;
if (head->node->left != NULL) //棧頂結點的左結點入棧
{
temp = new STACK();
temp->next = NULL;
temp->node = head->node->left;
tail->next = temp;
tail = temp;
}

if (head->node->right != NULL) //棧頂結點的右結點入棧
{
temp = new STACK();
temp->next = NULL;
temp->node = head->node->right;
tail->next = temp;
tail = temp;
}
cout<<head->node->data<<endl; //結點出棧
temp = head;
head = head->next;
delete(head);
}
}

❺ 遍歷二叉樹

遍歷方案：
1．遍歷方案
從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結點及左、右子樹這三個基本部分組成。因此，在任一給定結點上，可以按某種次序執行三個操作：
（1）訪問結點本身(N)，
（2）遍歷該結點的左子樹(L)，
（3）遍歷該結點的右子樹(R)。
以上三種操作有六種執行次序：
NLR、LNR、LRN、NRL、RNL、RLN。
注意：
前三種次序與後三種次序對稱，故只討論先左後右的前三種次序。
2．三種遍歷的命名
根據訪問結點操作發生位置命名：
① NLR：前序遍歷(PreorderTraversal亦稱(先序遍歷))
——訪問結點的操作發生在遍歷其左右子樹之前。
② LNR：中序遍歷(InorderTraversal)
——訪問結點的操作發生在遍歷其左右子樹之中(間)。
③ LRN：後序遍歷(PostorderTraversal)
——訪問結點的操作發生在遍歷其左右子樹之後。
注意：
由於被訪問的結點必是某子樹的根，所以N(Node)、L(Left subtree)和R(Right subtree)又可解釋為根、根的左子樹和根的右子樹。NLR、LNR和LRN分別又稱為先根遍歷、中根遍歷和後根遍歷。
遍歷演算法
1．中序遍歷的遞歸演算法定義：
若二叉樹非空，則依次執行如下操作：
(1)遍歷左子樹；
(2)訪問根結點；
(3)遍歷右子樹。
2．先序遍歷的遞歸演算法定義：
若二叉樹非空，則依次執行如下操作：
(1) 訪問根結點；
(2) 遍歷左子樹；
(3) 遍歷右子樹。
3．後序遍歷得遞歸演算法定義：
若二叉樹非空，則依次執行如下操作：
(1)遍歷左子樹；
(2)遍歷右子樹；
(3)訪問根結點。
4．中序遍歷的演算法實現
用二叉鏈表做為存儲結構，中序遍歷演算法可描述為：
void InOrder(BinTree T)
{ //演算法里①~⑥是為了說明執行過程加入的標號
① if(T) { // 如果二叉樹非空
② InOrder(T->lchild)；
③ printf("％c"，T->data)； // 訪問結點
④ InOrder(T->rchild);
⑤ }
⑥ } // InOrder
遍歷序列
1．遍歷二叉樹的執行蹤跡
三種遞歸遍歷演算法的搜索路線相同（如下圖虛線所示）。
具體線路為：
從根結點出發，逆時針沿著二叉樹外緣移動，對每個結點均途徑三次，最後回到根結點。
2．遍歷序列
A
/ \
B C
/ / \
D E F
圖
（1） 中序序列（inorder traversal）
中序遍歷二叉樹時，對結點的訪問次序為中序序列
【例】中序遍歷上圖所示的二叉樹時，得到的中序序列為：
D B A E C F
（2） 先序序列（preorder traversal）
先序遍歷二叉樹時，對結點的訪問次序為先序序列
【例】先序遍歷上圖所示的二叉樹時，得到的先序序列為：
A B D C E F
（3） 後序序列（postorder traversal）
後序遍歷二叉樹時，對結點的訪問次序為後序序列
【例】後序遍歷上圖所示的二叉樹時，得到的後序序列為：
D B E F C A
（4）層次遍歷（level traversal）二叉樹的操作定義為：若二叉樹為空，則退出，否則，按照樹的結構，從根開始自上而下，自左而右訪問每一個結點，從而實現對每一個結點的遍歷
注意：
（1）在搜索路線中，若訪問結點均是第一次經過結點時進行的，則是前序遍歷；若訪問結點均是在第二次(或第三次)經過結點時進行的，則是中序遍歷(或後序遍歷)。只要將搜索路線上所有在第一次、第二次和第三次經過的結點分別列表，即可分別得到該二叉樹的前序序列、中序序列和後序序列。
（2）上述三種序列都是線性序列，有且僅有一個開始結點和一個終端結點，其餘結點都有且僅有一個前趨結點和一個後繼結點。為了區別於樹形結構中前趨(即雙親)結點和後繼(即孩子)結點的概念，對上述三種線性序列，要在某結點的前趨和後繼之前冠以其遍歷次序名稱。
【例】上圖所示的二叉樹中結點C，其前序前趨結點是D，前序後繼結點是E；中序前趨結點是E，中序後繼結點是F；後序前趨結點是F，後序後繼結點是A。但是就該樹的邏輯結構而言，C的前趨結點是A，後繼結點是E和F。
二叉鏈表的構造
1． 基本思想
基於先序遍歷的構造，即以二叉樹的先序序列為輸入構造。
注意：
先序序列中必須加入虛結點以示空指針的位置。
【例】
建立上圖所示二叉樹，其輸入的先序序列是：ABD∮∮∮CE∮∮F∮∮。
2． 構造演算法
假設虛結點輸入時以空格字元表示，相應的構造演算法為：
void CreateBinTree (BinTree *T)
{ //構造二叉鏈表。T是指向根指針的指針，故修改*T就修改了實參(根指針)本身
char ch；
if((ch=getchar())=='') *T=NULL； //讀人空格，將相應指針置空
else{ //讀人非空格
*T=(BinTNode *)malloc(sizeof(BinTNode))； //生成結點
(*T)->data=ch；
CreateBinTree(&(*T)->lchild)； //構造左子樹
CreateBinTree(&(*T)->rchild)； //構造右子樹
}
}
注意：
調用該演算法時，應將待建立的二叉鏈表的根指針的地址作為實參。
【例】
設root是一根指針(即它的類型是BinTree)，則調用CreateBinTree(&root)後root就指向了已構造好的二叉鏈表的根結點。
二叉樹建立過程見http://student.zjzk.cn/course_ware/data_structure/web/flashhtml/erchashujianli.htm
下面是關於二叉樹的遍歷、查找、刪除、更新數據的代碼(遞歸演算法):
[code]
#include <iostream>
using namespace std;
typedef int T;
class bst{
struct Node{
T data;
Node* L;
Node* R;
Node(const T& d, Node* lp=NULL, Node* rp=NULL):data(d),L(lp),R(rp){}
};
Node* root;
int num;
public:
bst():root(NULL),num(0){}
void clear(Node* t){
if(t==NULL) return;
clear(t->L);
clear(t->R);
delete t;
}
~bst(){clear(root);}
void clear(){
clear(root);
num = 0;
root = NULL;
}
bool empty(){return root==NULL;}
int size(){return num;}
T getRoot(){
if(empty()) throw "empty tree";
return root->data;
}
void travel(Node* tree){
if(tree==NULL) return;
travel(tree->L);
cout << tree->data << ' ';
travel(tree->R);
}
void travel(){
travel(root);
cout << endl;
}
int height(Node* tree){
if(tree==NULL) return 0;
int lh = height(tree->L);
int rh = height(tree->R);
return 1+(lh>rh?lh:rh);
}
int height(){
return height(root);
}
void insert(Node*& tree, const T& d){
if(tree==NULL)
tree = new Node(d);
else if(ddata)
insert(tree->L, d);
else
insert(tree->R, d);
}
void insert(const T& d){
insert(root, d);
num++;
}
Node*& find(Node*& tree, const T& d){
if(tree==NULL) return tree;
if(tree->data==d) return tree;
if(ddata)
return find(tree->L, d);
else
return find(tree->R, d);
}
bool find(const T& d){
return find(root, d)!=NULL;
}
bool erase(const T& d){
Node*& pt = find(root, d);
if(pt==NULL) return false;
combine(pt->L, pt->R);
Node* p = pt;
pt = pt->R;
delete p;
num--;
return true;
}
void combine(Node* lc, Node*& rc){
if(lc==NULL) return;
if(rc==NULL) rc = lc;
else combine(lc, rc->L);
}
bool update(const T& od, const T& nd){
Node* p = find(root, od);
if(p==NULL) return false;
erase(od);
insert(nd);
return true;
}
};
int main()
{
bst b;
cout << "input some integers:";
for(;;){
int n;
cin >> n;
b.insert(n);
if(cin.peek()=='\n') break;
}
b.travel();
for(;;){
cout << "input data pair:";
int od, nd;
cin >> od >> nd;
if(od==-1&&nd==-1) break;
b.update(od, nd);
b.travel();
}
}
[/code]

❻ 求二叉樹遍歷演算法C語言實現的

Status
PreOrderTraverse
(
BiTree
T,
Status
(
*Visit
)
(
TElemType
e
)
)
{
//
採用二叉鏈表存儲結構，Visit
是對數據元素操作的應用函數，先序遍歷二叉樹
T
的遞歸演算法。
if
(
T
)
{
//
若
T
不為空
if
(
Visit
(
T->data
)
)
//
調用函數
Visit
if
(
PreOrderTraverse
(
T->lchild,
Visit
)
)
//
遞歸調用左子樹
if
(
PreOrderTraverse
(
T->rchild,
Visit
)
)
return
OK;
//
遞歸調用右子樹
return
ERROR;
}
else
return
OK;
}
//
PreOrderTraverse

❼ c語言編程實現二叉樹的三種遍歷演算法 並針對一個二叉樹列出三種遍歷序列。功能要求：實現三種遍歷演算法、

#include<stdio.h>
#include<malloc.h>

typedefstructBTree{
chardata;
structBTree*lChild;
structBTree*rChild;
}BinTree;

BinTree*CreateTree(BinTree*p){
charch;
scanf("%c",&ch);
if(ch=='#')returnNULL;
p=(BinTree*)malloc(sizeof(BinTree));
p->data=ch;
p->lChild=CreateTree(p->lChild);
p->rChild=CreateTree(p->rChild);
returnp;
}

intSumLeaf(BinTree*T){
intsum=0,m,n;
if(T){
if((!T->lChild)&&(!T->rChild))
sum++;
m=SumLeaf(T->lChild);
n=SumLeaf(T->rChild);
sum+=m+n;
}
returnsum;
}

voidQianXu(BinTree*T){
if(T){
printf("%c,",T->data);
QianXu(T->lChild);
QianXu(T->rChild);
}
}

voidZhongXu(BinTree*T){
if(T){
ZhongXu(T->lChild);
printf("%c,",T->data);
ZhongXu(T->rChild);
}
}

voidHouXu(BinTree*T){
if(T){
HouXu(T->lChild);
HouXu(T->rChild);
printf("%c,",T->data);
}
}

intDepth(BinTree*T){
intdep=0,depl,depr;
if(!T)dep=0;
else{
depl=Depth(T->lChild);
depr=Depth(T->rChild);
dep=1+(depl>depr?depl:depr);
}
returndep;
}

voidFreeTree(BinTree*T){
if(T){
FreeTree(T->lChild);
FreeTree(T->rChild);
free(T);
}
}

intmain(){
BinTree*Tree=NULL;
Tree=CreateTree(Tree);
//前序遍歷
printf("QianXuTraversal:");
QianXu(Tree);
printf("
ZhongXuTraversal:");
ZhongXu(Tree);
printf("
HouXuTraversal:");
HouXu(Tree);

printf("
Leaf'snumber:%d
",SumLeaf(Tree));
printf("Tree'sDepth:%d",Depth(Tree));

FreeTree(Tree);
return0;
}

❽ 二叉樹先序非遞歸遍歷C語言演算法

#include "stdio.h"
#include "stdlib.h"
#define STACK_INIT_SIZE 10 //棧的初始長度
#define STACKINCREMENT 5 //棧的追加長度

typedef struct bitree{
char data;
struct bitree *lchild,*rchild;
}bitree; //二叉樹結點定義

typedef struct {
bitree **base;
bitree **top;
int stacksize;
}sqstack; // 鏈棧結點定則寬義top棧頂 base棧底 且棧元素是指向二叉樹結點的二級指針
//建立一個空棧
int initstack(sqstack *s)
{s->base=(bitree *)malloc(STACK_INIT_SIZE*sizeof(bitree)); //棧底指向開辟空間
if(!s->base) exit(1); //拋出異常
s->top=s->base; //棧頂=棧尾 表示棧空
s->stacksize=STACK_INIT_SIZE; //棧長度為開辟空間大小
return 1;
}
//進棧
int push(sqstack *s,bitree *e)
{if(s->top-s->base>=s->stacksize) //如果棧滿 追加開辟空間
{s->base=(bitree *)realloc (s->base,(s->stacksize+STACKINCREMENT)* sizeof(bitree));
if(!s->base) exit(1); //拋出異常
s->top=s->純盯枯base+s->stacksize; //感覺這一句沒用
s->stacksize+=STACKINCREMENT;}
*(s->top)=e;s->top++; //進棧 棧頂後移
return 1;
}
//出棧
int pop(sqstack *s,bitree **e)
{if(s->top==s->base) return 0; //棧空 返回0
--s->top;*e=*(s->top); //做洞棧頂前移 取出棧頂元素給e
return 1;}
//取棧頂
int gettop(sqstack *s,bitree **e) //去棧頂元素 注意top指向的是棧頂的後一個
{if(s->top==s->base) return 0; //所以 s->top-1
*e=*(s->top-1);
return 1;
}
/*------------------------非遞歸-----先序建立二叉樹----------------------------------*/
bitree *createprebitree()
{char ch;bitree *ht,*p,*q;
sqstack *s;
s=malloc(sizeof(bitree)); //加上這一句為s 初始化開辟空間
ch=getchar();
if(ch!='#'&&ch!='\n') /* 輸入二叉樹先序順序 是以完全二叉樹的先序順序
不是完全二叉樹的把沒有的結點以#表示 */
{ht=(bitree *)malloc(sizeof(bitree));
ht->data=ch;
ht->lchild=ht->rchild=NULL;
p=ht;
initstack(s);
push(s,ht); //根節點進棧
while((ch=getchar())!='\n') // 算
{if(ch!='#') {q=(bitree *)malloc(sizeof(bitree)); // 法
q->data=ch; //
if(p==*(s->top-1)) p->lchild=q; // 核
else p->rchild=q; //
push(s,q);p=q; // 心
} //
else {if(p==*(s->top-1)) p->lchild=NULL; // 的
else p->rchild=NULL; //
pop(s,&p);} // 步
//
} // 驟
return ht;
}
else return NULL;
}
/*--------------------------遞歸---------先序建立二叉樹-------------------------------*/
void CreateBiTree(bitree **T) {
//按先序次序輸入二叉樹中的結點的值（一個字元），空格字元表示空樹，
//構造二叉鏈表表示二叉樹
char ch;
scanf("%c",&ch);
if(ch=='#') *T=NULL;
else{
*T=(bitree * )malloc(sizeof(bitree));
if(!*T) exit(1);
(*T)->data=ch; //生成根結點
CreateBiTree(&(*T)->lchild); //構造左子樹
CreateBiTree(&(*T)->rchild); //構造右子樹
}
}
/*--------------------------非遞歸-------中序建立二叉樹-------------------------------*/
/*--------------------------遞歸---------中序建立二叉樹-------------------------------*/
/*--------------------------非遞歸-------後序建立二叉樹-------------------------------*/
/*--------------------------遞歸---------後序建立二叉樹-------------------------------*/

/*-----------------------非遞歸------先序輸出二叉樹------------------------------*/
void preordertraverse(bitree *h)
{sqstack m;
initstack(&m);
while(h||m.base!=m.top)
{if(h) {push(&m,h);printf("%c",h->data);h=h->lchild;}
else{pop(&m,&h);
h=h->rchild;}
}
}
/*------------------------非遞歸-----中序輸出二叉樹----------------------------*/
void inordertraverse(bitree *h)
{sqstack m;
initstack(&m);
while(h||m.base!=m.top)
{if(h) {push(&m,h);h=h->lchild;}
else {
pop(&m,&h);
printf("%c",h->data);
h=h->rchild;
}
}
}
/*---------------------非遞歸----後序遍歷二叉樹----------------------------------*/
void postordertraverse(bitree *h)
{
sqstack m;
initstack(&m);
while(h||m.base!=m.top)
{if(h) {
push(&m,h);
h=h->lchild;}
else {
bitree *r; //使用r結點表示訪問了右子樹 代替標志域
gettop(&m,&h);
if(h->rchild&&h->rchild!=r)
{h=h->rchild;
push(&m,h);
h=h->lchild;}
else{pop(&m,&h);
printf("%c",h->data);
r=h;h=NULL;}
}
}
}
//層次遍歷二叉樹 用隊列 哈哈以後做
/*-------------------------------主過程-------------------------------*/
int main()
{bitree *ht;
printf("先序非遞歸建立一個二叉樹:");
if((ht=createprebitree())!=NULL) //非遞歸建立
//CreateBiTree(&ht);
//if(ht!=NULL) //遞歸建立
{
printf("先序遍歷輸出二叉樹:");
preordertraverse(ht);
putchar('\n');
printf("中序遍歷輸出二叉樹:");
inordertraverse(ht);
putchar('\n');
printf("後序遍歷輸出二叉樹:");
postordertraverse(ht);
putchar('\n');
}
else printf("空二叉樹\n");
}