創建二叉樹演算法
⑴ 數據結構-二叉樹的創建
如果要在內存中建立一個如下左圖這樣的樹，wield能讓每個結點確認是否有左右孩子，我們對它進行擴展，變成如下右圖的樣子，也就是將二叉樹中的每個結點的空指針引出一個虛結點，其值為一個特定值，比如」#」，稱之為擴展二叉樹。擴展二叉樹就可以做到一個遍歷序列確定一棵二叉樹了。如前序遍歷序列為AB#D##C##。
//創建樹方法二
intCreateTree2(BiTree*t)
{
charch;
scanf("%c",&ch);
if(ch=='#')
{
(*t)=NULL;
}
else
{
(*t)=(BiTree)malloc(sizeof(BitNode));
if((*t)==NULL)
{
fprintf(stderr,"malloc()errorinCreateTree2.
");
returnERROR;
}
(*t)->data=ch;
CreateTree2(&((*t)->lchild));
CreateTree2(&((*t)->rchild));
}
returnOK;
}
其實建立二叉樹，也是利用了遞歸的原理。只不過在原來應該列印結點的地方，改成生成結點、給結點賦值的操作而已。因此，完全可以用中序或後序遍歷的方式實現二叉樹的建立，只不過代碼里生成結點和構造左右子樹的代碼順序交互一下即可。
⑵ 二叉樹如何建立
先序遞歸創建二叉樹，並對其進行 先序、中序、後序遍歷
#include<malloc.h> // malloc()等
#include<stdio.h> // 標准輸入輸出頭文件，包括EOF(=^Z或F6)，NULL等
#include<stdlib.h> // atoi()，exit()
#include<math.h> // 數學函數頭文件，包括floor()，ceil()，abs()等
#define ClearBiTree DestroyBiTree // 清空二叉樹和銷毀二叉樹的操作一樣
typedef struct BiTNode
{
int data; // 結點的值
BiTNode *lchild,*rchild; // 左右孩子指針
}BiTNode,*BiTree;
int Nil=0; // 設整型以0為空
void visit(int e)
{ printf("%d ",e); // 以整型格式輸出
}
void InitBiTree(BiTree &T)
{ // 操作結果：構造空二叉樹T
T=NULL;
}
void CreateBiTree(BiTree &T)
{ // 演算法6.4：按先序次序輸入二叉樹中結點的值(可為字元型或整型，在主程中定義)，
// 構造二叉鏈表表示的二叉樹T。變數Nil表示空(子)樹。修改
int number;
scanf("%d",&number); // 輸入結點的值
if(number==Nil) // 結點的值為空
T=NULL;
else // 結點的值不為空
{ T=(BiTree)malloc(sizeof(BiTNode)); // 生成根結點
if(!T)
exit(OVERFLOW);
T->data=number; // 將值賦給T所指結點
CreateBiTree(T->lchild); // 遞歸構造左子樹
CreateBiTree(T->rchild); // 遞歸構造右子樹
}
}
void DestroyBiTree(BiTree &T)
{ // 初始條件：二叉樹T存在。操作結果：銷毀二叉樹T
if(T) // 非空樹
{ DestroyBiTree(T->lchild); // 遞歸銷毀左子樹，如無左子樹，則不執行任何操作
DestroyBiTree(T->rchild); // 遞歸銷毀右子樹，如無右子樹，則不執行任何操作
free(T); // 釋放根結點
T=NULL; // 空指針賦0
}
}
void PreOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始條件：二叉樹T存在，Visit是對結點操作的應用函數。修改演算法6.1
// 操作結果：先序遞歸遍歷T，對每個結點調用函數Visit一次且僅一次
if(T) // T不空
{ Visit(T->data); // 先訪問根結點
PreOrderTraverse(T->lchild,Visit); // 再先序遍歷左子樹
PreOrderTraverse(T->rchild,Visit); // 最後先序遍歷右子樹
}
}
void InOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始條件：二叉樹T存在，Visit是對結點操作的應用函數
// 操作結果：中序遞歸遍歷T，對每個結點調用函數Visit一次且僅一次
if(T)
{ InOrderTraverse(T->lchild,Visit); // 先中序遍歷左子樹
Visit(T->data); // 再訪問根結點
InOrderTraverse(T->rchild,Visit); // 最後中序遍歷右子樹
}
}
void PostOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始條件：二叉樹T存在，Visit是對結點操作的應用函數
// 操作結果：後序遞歸遍歷T，對每個結點調用函數Visit一次且僅一次
if(T) // T不空
{ PostOrderTraverse(T->lchild,Visit); // 先後序遍歷左子樹
PostOrderTraverse(T->rchild,Visit); // 再後序遍歷右子樹
Visit(T->data); // 最後訪問根結點
}
}
void main()
{
BiTree T;
InitBiTree(T); // 初始化二叉樹T
printf("按先序次序輸入二叉樹中結點的值,輸入0表示節點為空，輸入範例：1 2 0 0 3 0 0\n");
CreateBiTree(T); // 建立二叉樹T
printf("先序遞歸遍歷二叉樹：\n");
PreOrderTraverse(T,visit); // 先序遞歸遍歷二叉樹T
printf("\n中序遞歸遍歷二叉樹：\n");
InOrderTraverse(T,visit); // 中序遞歸遍歷二叉樹T
printf("\n後序遞歸遍歷二叉樹：\n");
PostOrderTraverse(T,visit); // 後序遞歸遍歷二叉樹T
}
⑶ 1、創建一棵二叉樹，以二叉鏈表作存儲結構，實現先根遍歷演算法 2、創建一棵二叉樹，實現先根遍歷演算法、中根
你需要的東西這裡面都包含了，你自己看哪裡用得上就摘一段下來吧。
// 數據結構.cpp : 定義控制台應用程序的入口點。
//
#include "stdafx.h"
int _tmain(int argc, _TCHAR* argv[])
{
return 0;
}
#include<stdio.h>
#include<stdlib.h>
#define MAX 20
#define NULL 0
typedef char ElemType;
typedef int Status;
typedef enum{link,thread} pointertag;
typedef struct BiTNode
{
ElemType data;
struct BiTNode *lchild,*rchild;
pointertag Ltag,Rtag;
}BiTNode,*BiTree;
BiTree pre;
Status CreateBiTree(BiTree *T)//按前序構建二叉樹。
{
char ch;
ch=getchar();
if(ch=='#')
*T=NULL;
else
{
*T=(BiTree)malloc(sizeof(BiTNode));
(*T)->data=ch;
(*T)->Ltag=(*T)->Rtag=link;
CreateBiTree(&(*T)->lchild);
CreateBiTree(&(*T)->rchild);
}
return 1;
}
Status CreateBiTree1(BiTree *T)//按中序輸入構建二叉樹。
{
char ch;
ch=getchar();
if(ch=='#')
*T=NULL;
else
{
*T=(BiTree)malloc(sizeof(BiTNode));
CreateBiTree(&(*T)->lchild);
(*T)->data=ch;
CreateBiTree(&(*T)->rchild);
}
return 1;
}
void MidOrder(BiTree T)//遞歸中序輸出。
{
if(T)
{
MidOrder(T->lchild);
printf("%2c",T->data);
MidOrder(T->rchild);
}
}
void PreOrder(BiTree T)//前序輸出。
{
if(T)
{
printf("%2c",T->data);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
void EndOrder(BiTree T)//後序輸出。
{
if(T)
{
EndOrder(T->lchild);
EndOrder(T->rchild);
printf("%2c",T->data);
}
}
void MidOrder1(BiTree T)//非遞歸中序輸出。
{
int i=0;
BiTree p,s[100];
p=T;
do
{
while(p)
{
s[i++]=p;
p=p->lchild;
}
if(i>0)
{
p=s[--i];
printf("%2c",p->data);
p=p->rchild;
}
}while(i>0||p!=NULL);
}
void Levle(BiTree T)//按層次遍歷二叉樹。
{
BiTree Queue[MAX],b;
int front,rear;
front=rear=0;
if(T)
{
Queue[rear++]=T;
while(front!=rear)
{
b=Queue[front++];
printf("%2c",b->data);
if(b->lchild!=NULL)
Queue[rear++]=b->lchild;
if(b->rchild!=NULL)
Queue[rear++]=b->rchild;
}
}
}
int depth(BiTree T)//求二叉樹的深度。
{
int dep1,dep2;
if(T==NULL)return 0;
else
{
dep1=depth(T->lchild);
dep2=depth(T->rchild);
return dep1>dep2?dep1+1:dep2+1;
}
}
void InThreading(BiTree p)//線索化。
{
if(p)
{
InThreading(p->lchild);
if(p->lchild=NULL){p->Ltag=thread;p->lchild=pre;}
if(pre->rchild==NULL){pre->Rtag=thread;pre->rchild=p;}
pre=p;
InThreading(p->rchild);
}
}
Status InorderThreading(BiTree *Thrt,BiTree T)//中序遍歷二叉樹T，並將其線索化。
{
(*Thrt)=(BiTree)malloc(sizeof(BiTNode));
(*Thrt)->Ltag=link;
(*Thrt)->Rtag=thread;
(*Thrt)->rchild=*Thrt;
if(T==NULL)
(*Thrt)->lchild=*Thrt;
else
{
(*Thrt)->lchild=T;
pre=*Thrt;
InThreading(T);
pre->rchild=(*Thrt);
pre->Rtag=thread;
(*Thrt)->rchild=pre;
}
return 1;
}
Status InorderTraverse(BiTree Thrt)//中序遍歷線索二叉樹Thrt,Thrt指向頭結點。
{
BiTree p;
p=Thrt->lchild;
while(p!=Thrt)
{
while(p->Ltag==link)p=p->lchild;
printf("%2c",p->data);
while(p->Rtag==thread&&p->lchild!=Thrt)
{
p=p->rchild;
printf("%2c",p->data);
}
p=p->rchild;
}
return 1;
}
void main()
{
BiTree T=NULL,Thrt=NULL;
printf("創建一個二叉樹\n");
CreateBiTree(&T);
//InorderThreading(&Thrt,T);
//InorderTraverse(Thrt);
//printf("中序遍歷的結果是：");
//MidOrder(T);
//printf("\n");
printf("先序遍歷的結果是：");
PreOrder(T);
printf("\n");
/*printf("後序遍歷的結果是：");
EndOrder(T);
printf("\n");
printf("按層次遍歷二叉樹的結果是：");
Levle(T);
printf("\n");
printf("深度輸出為：%d",depth(T));
printf("\n");*/
}
⑷ 二叉樹的建立
// 中序遍歷偽代碼：非遞歸版本，用棧實現，版本2
void InOrder2(TNode* root)
{
Stack S;
if( root != NULL )
{
S.push(root);
}
while ( !S.empty() )
{
TNode* node = S.pop();
if ( node->bPushed )
{ // 如果標識位為true,則表示其左右子樹都已經入棧，那麼現在就需要訪問該節點了
Visit(node);
}
else
{ // 左右子樹尚未入棧，則依次將 右節點，根節點，左節點 入棧
if ( node->right != NULL )
{
node->right->bPushed = false; // 左右子樹均設置為false
S.push(node->right);
}
node->bPushed = true; // 根節點標志位為true
S.push(node);
if ( node->left != NULL )
{
node->left->bPushed = false;
S.push(node->left);
}
}
}
}
對比先序遍歷，這個演算法需要額外的增加O(n)的標志位空間。另外，棧空間也擴大，因為每次壓棧的時候都壓入根節點與左右節點，因此棧空間為O(n)。時間復雜度方面，每個節點壓棧兩次，作為子節點壓棧一次，作為根節點壓棧一次，彈棧也是兩次。因此無論從哪個方面講，這個方法效率都不及InOrder1。
後序
void postOrder(TreeNode<T> *root)
{
stack<TreeNode<T>*> st;
TreeNode<T> *p = root;
TreeNode<T> *pre = NULL;//pre表示最近一次訪問的結點
while(p || st.size()!=0)
{
//沿著左孩子方向走到最左下 。
while(p)
{
st.push(p);
p = p->left;
}
//get the top element of the stack
p = st.top();
//如果p沒有右孩子或者其右孩子剛剛被訪問過
if(p->right == NULL || p->right == pre)
{
/ isit this element and then pop it
cout << "visit: " << p->data << endl;
st.pop();
pre = p;
p = NULL;
}
else
{
p = p->right;
}
}//end of while(p || st.size()!=0)
}
怎麼樣
⑸ java構建二叉樹演算法
//******************************************************************************************************//
//*****本程序包括簡單的二叉樹類的實現和前序,中序,後序,層次遍歷二叉樹演算法,*******//
//******以及確定二叉樹的高度,制定對象在樹中的所處層次以及將樹中的左右***********//
//******孩子節點對換位置,返回葉子節點個數刪除葉子節點,並輸出所刪除的葉子節點**//
//*******************************CopyRight By phoenix*******************************************//
//************************************Jan 12,2008*************************************************//
//****************************************************************************************************//
public class BinTree {
public final static int MAX=40;
private Object data; //數據元數
private BinTree left,right; //指向左,右孩子結點的鏈
BinTree []elements = new BinTree[MAX];//層次遍歷時保存各個節點
int front;//層次遍歷時隊首
int rear;//層次遍歷時隊尾
public BinTree()
{
}
public BinTree(Object data)
{ //構造有值結點
this.data = data;
left = right = null;
}
public BinTree(Object data,BinTree left,BinTree right)
{ //構造有值結點
this.data = data;
this.left = left;
this.right = right;
}
public String toString()
{
return data.toString();
}//前序遍歷二叉樹
public static void preOrder(BinTree parent){
if(parent == null)
return;
System.out.print(parent.data+" ");
preOrder(parent.left);
preOrder(parent.right);
}//中序遍歷二叉樹
public void inOrder(BinTree parent){
if(parent == null)
return;
inOrder(parent.left);
System.out.print(parent.data+" ");
inOrder(parent.right);
}//後序遍歷二叉樹
public void postOrder(BinTree parent){
if(parent == null)
return;
postOrder(parent.left);
postOrder(parent.right);
System.out.print(parent.data+" ");
}// 層次遍歷二叉樹
public void LayerOrder(BinTree parent)
{
elements[0]=parent;
front=0;rear=1;
while(front<rear)
{
try
{
if(elements[front].data!=null)
{
System.out.print(elements[front].data + " ");
if(elements[front].left!=null)
elements[rear++]=elements[front].left;
if(elements[front].right!=null)
elements[rear++]=elements[front].right;
front++;
}
}catch(Exception e){break;}
}
}//返回樹的葉節點個數
public int leaves()
{
if(this == null)
return 0;
if(left == null&&right == null)
return 1;
return (left == null ? 0 : left.leaves())+(right == null ? 0 : right.leaves());
}//結果返回樹的高度
public int height()
{
int heightOfTree;
if(this == null)
return -1;
int leftHeight = (left == null ? 0 : left.height());
int rightHeight = (right == null ? 0 : right.height());
heightOfTree = leftHeight<rightHeight?rightHeight:leftHeight;
return 1 + heightOfTree;
}
//如果對象不在樹中,結果返回-1;否則結果返回該對象在樹中所處的層次,規定根節點為第一層
public int level(Object object)
{
int levelInTree;
if(this == null)
return -1;
if(object == data)
return 1;//規定根節點為第一層
int leftLevel = (left == null?-1:left.level(object));
int rightLevel = (right == null?-1:right.level(object));
if(leftLevel<0&&rightLevel<0)
return -1;
levelInTree = leftLevel<rightLevel?rightLevel:leftLevel;
return 1+levelInTree;
}
//將樹中的每個節點的孩子對換位置
public void reflect()
{
if(this == null)
return;
if(left != null)
left.reflect();
if(right != null)
right.reflect();
BinTree temp = left;
left = right;
right = temp;
}// 將樹中的所有節點移走,並輸出移走的節點
public void defoliate()
{
String innerNode = "";
if(this == null)
return;
//若本節點是葉節點，則將其移走
if(left==null&&right == null)
{
System.out.print(this + " ");
data = null;
return;
}
//移走左子樹若其存在
if(left!=null){
left.defoliate();
left = null;
}
//移走本節點，放在中間表示中跟移走...
innerNode += this + " ";
data = null;
//移走右子樹若其存在
if(right!=null){
right.defoliate();
right = null;
}
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
BinTree e = new BinTree("E");
BinTree g = new BinTree("G");
BinTree h = new BinTree("H");
BinTree i = new BinTree("I");
BinTree d = new BinTree("D",null,g);
BinTree f = new BinTree("F",h,i);
BinTree b = new BinTree("B",d,e);
BinTree c = new BinTree("C",f,null);
BinTree tree = new BinTree("A",b,c);
System.out.println("前序遍歷二叉樹結果: ");
tree.preOrder(tree);
System.out.println();
System.out.println("中序遍歷二叉樹結果: ");
tree.inOrder(tree);
System.out.println();
System.out.println("後序遍歷二叉樹結果: ");
tree.postOrder(tree);
System.out.println();
System.out.println("層次遍歷二叉樹結果: ");
tree.LayerOrder(tree);
System.out.println();
System.out.println("F所在的層次: "+tree.level("F"));
System.out.println("這棵二叉樹的高度: "+tree.height());
System.out.println("--------------------------------------");
tree.reflect();
System.out.println("交換每個節點的孩子節點後......");
System.out.println("前序遍歷二叉樹結果: ");
tree.preOrder(tree);
System.out.println();
System.out.println("中序遍歷二叉樹結果: ");
tree.inOrder(tree);
System.out.println();
System.out.println("後序遍歷二叉樹結果: ");
tree.postOrder(tree);
System.out.println();
System.out.println("層次遍歷二叉樹結果: ");
tree.LayerOrder(tree);
System.out.println();
System.out.println("F所在的層次: "+tree.level("F"));
System.out.println("這棵二叉樹的高度: "+tree.height());
}
⑹ 二叉樹的創建與訪問演算法的設計
Node{
Node* left;
Node* right;
int value;
};
void traverse(Node* tree)
{
if( !tree) return;
traverse(tree->left);
traverse(tree->right);
// do something here on tree->value -> e.g.
printf("%d\n", tree->value);
}
Finish entering tree elements by yourself.
⑺ 請問C語言如何創建二叉樹
創建二叉樹的源程序如下：
#include <cstdlib>
#include <stdio.h>
typedef struct node
{ //樹的結點
int data;
struct node* left;
struct node* right;
} Node;
typedef struct
{ //樹根
Node* root；
} Tree;
void insert(Tree* tree, int value)//創建樹
{
Node* node=(Node*)malloc(sizeof(Node));//創建一個節點
node->data = value;
node->left = NULL;
node->right = NULL;
if (tree->root == NULL)//判斷樹是不是空樹
{
tree->root = node;
}
else
{//不是空樹
Node* temp = tree->root;//從樹根開始
while (temp != NULL)
{
if (value < temp->data)//小於就進左兒子
{
if (temp->left == NULL)
{
temp->left = node;
return;
}
else
{//繼續判斷
temp = temp->left;
}
}
else {//否則進右兒子
if (temp->right == NULL)
{
temp->right = node;
return;
}
else {//繼續判斷
temp = temp->right;
}
}
}
}
return；
}
void inorder(Node* node)//樹的中序遍歷
{
if (node != NULL)
{
inorder(node->left);
printf("%d ",node->data);
inorder(node->right);
}
}
int main()
{
Tree tree;
tree.root = NULL;//創建一個空樹
int n;
scanf("%d",&n);
for (int i = 0; i < n; i++)//輸入n個數並創建這個樹
{
int temp;
scanf("%d",&temp);
insert(&tree, temp);
}
inorder(tree.root);//中序遍歷
getchar();
getchar();
return 0;
}
(7)創建二叉樹演算法擴展閱讀：
簡單二叉樹定義範例：此樹的順序結構為：ABCDE
#include <cstdlib>
#include <stdio.h>
#include <string>
int main()
{
node* p = newnode;
node* p = head;
head = p;
string str;
cin >> str;
creat(p, str, 0)//默認根結點在str下標0的位置
return 0;
}
//p為樹的根結點（已開辟動態內存）,str為二叉樹的順序存儲數組ABCD##E或其他順序存儲數組，r當前結點所在順序存儲數組位置
void creat(node* p, string str, int r)
{
p->data = str[r];
if (str[r * 2 + 1] == '#' || r * 2 + 1 > str.size() - 1)p->lch = NULL；
else
{
p->lch = newnode;
creat(p->lch, str, r * 2 + 1);
}
if (str[r * 2 + 2] == '#' || r * 2 + 2 > str.size() - 1)p->rch = NULL;
else
{
p->rch = newnode;
creat(p->rch, str, r * 2 + 2);
}
}
⑻ 二叉樹基本演算法
#include <iostream.h>
typedef struct BiTNode
{
char data;
int bit;
struct BiTNode *lchild,*rchild,*parent;
}BiTNode;
void InitBT(BiTNode *&t)//1、初始化，不帶頭結點
{
t=NULL;
}
/*void InitBT(BiTNode *t)//初始化，帶頭結點
{
t=new BiTNode;
t->lchild=t->rchild=t->parent=NULL;
}*/
int EmptyBT(BiTNode *t)//判斷隊空
{
if(t==0)
return 1;
else
return 0;
}
BiTNode *creatBT(BiTNode *t,int b)//2、創建二叉樹
{
BiTNode *p;
char ch;
cin>>ch;
if(ch=='#')return 0;
else
{
p=new BiTNode;
p->data=ch;
p->parent=t;
p->bit=b;
t=p;
t->lchild=creatBT(t,0);
t->rchild=creatBT(t,1);
}
return t;
}
void preorder(BiTNode *t)//3、先序遍歷
{
if(!EmptyBT(t))
{
cout<<t->data;
preorder(t->lchild);
preorder(t->rchild);
}
}
void inorder(BiTNode *t)//中序遍歷
{
if(!EmptyBT(t))
{
inorder(t->lchild);
cout<<t->data;
inorder(t->rchild);
}
}
void postorder(BiTNode *t)//後序遍歷
{
if(!EmptyBT(t))
{
postorder(t->lchild);
postorder(t->rchild);
cout<<t->data;
}
}
void coutBT(BiTNode *t,int &m,int &n,int &i)//4、計算二叉樹中葉子結點、度為2的結點和度為1的結點的個數
{
if(!EmptyBT(t))
{
if((t->lchild==0) && (t->rchild==0))
m++;//葉子結點
else if((t->lchild!=0) && (t->rchild!=0))
i++;//度為2的結點
else
n++;//度為1的結點
coutBT(t->lchild,m,n,i);
coutBT(t->rchild,m,n,i);
}
}
void coutNode(BiTNode *t,int &k)//5、求二叉樹中結點個數
{
if(!EmptyBT(t))
{
k++;
coutNode(t->lchild,k);
coutNode(t->rchild,k);
}
}
int BTdepth(BiTNode *t)//6、求二叉樹的深度
{
int i,j;
if(EmptyBT(t))
return 0;
else
{
i=BTdepth(t->lchild);
j=BTdepth(t->rchild);
return (i>j?i:j)+1;
}
}
int Xdepth(BiTNode *t,char x)//7、查找x的層數
{
int num1,num2,n;
if(t==NULL)
return 0;
else{
if(t->data==x)
return 1;
num1=Xdepth(t->lchild,x);
num2=Xdepth(t->rchild,x);
n=num1+num2;
if(num1!=0||num2!=0)
n++;
return n;
}
}
static int flag;
void SearchChild(BiTNode *t,int k)//8、查找第k個結點的左右孩子
{
if(!EmptyBT(t))
{
if(k==0)
{
cout<<"位置不能為0!"<<endl;
return;
}
else
{
flag++;
if(flag==k)
{
if(t->lchild==0)
cout<<"無左孩子! ";
else
cout<<"左孩子為："<<(t->lchild->data)<<" ";
if(t->rchild==0)
cout<<"無右孩子!"<<endl;
else
cout<<"右孩子為："<<(t->rchild->data)<<endl;
}
else
{
SearchChild(t->lchild,k);
SearchChild(t->rchild,k);
}
}
}
}
int Xancestor(BiTNode *t,char x)//9、查找x結點祖先
{
int n,num1,num2;
if(t==NULL)
return 0;
else
{
if(t->data==x)
return 1;
num1=Xancestor(t->lchild,x);
num2=Xancestor(t->rchild,x);
n=num1+num2;
if(n!=0)
{
n++;
cout<<t->data<<" "<<endl;
}
}
}
void BTNodePath(BiTNode *t)//10、輸出所有葉子結點路徑
{
if(!EmptyBT(t))
{
if((t->lchild==0) && (t->rchild==0))
{
cout<<t->data<<"的路徑為：";
for(BiTNode *p=t;p!=0;p=p->parent)
cout<<p->data;
cout<<endl;
}
else
{
BTNodePath(t->lchild);
BTNodePath(t->rchild);
}
}
}
void BTNodebit(BiTNode *t)//11、輸出所有葉子結點編碼
{
if(!EmptyBT(t))
{
if((t->lchild==0) && (t->rchild==0))
{
cout<<t->data<<"的編碼為：";
for(BiTNode *p=t;p->parent!=0;p=p->parent)
cout<<p->bit;
cout<<endl;
}
else
{
BTNodebit(t->lchild);
BTNodebit(t->rchild);
}
}
}
void main()
{
BiTNode *t;
int m,n,i,d,q,k;
char x;
cout<<"1、初始化..."<<endl;
InitBT(t);
cout<<"2、創建二叉樹..."<<endl;
t=creatBT(t,0);
cout<<"3.1、先序遍歷..."<<endl;
preorder(t);
cout<<endl;
cout<<"3.2、中序遍歷..."<<endl;
inorder(t);
cout<<endl;
cout<<"3.3、後序遍歷..."<<endl;
postorder(t);
cout<<endl;
m=n=i=0;
cout<<"4、計算葉子結點，度為1的結點和度為2的結點的個數..."<<endl;
coutBT(t,m,n,i);
cout<<"葉子結點個數為："<<m<<endl;
cout<<"度為1的結點個數為："<<n<<endl;
cout<<"度為2的結點個數為："<<i<<endl;
q=0;
cout<<"5、計算結點個數..."<<endl;
coutNode(t,q);
cout<<"結點個數為："<<q<<endl;
d=0;
cout<<"6、計算深度..."<<endl;
d=BTdepth(t);
cout<<"深度為："<<d<<endl;
cout<<"7、求x的層數..."<<endl;
cout<<"輸入x：";
cin>>x;
if(Xdepth(t,x)==0)
cout<<"x不存在！"<<endl;
else
cout<<Xdepth(t,x)<<endl;
cout<<"8、輸入要查找孩子的結點在先序遍歷中的位置k（不等於0）：";
cin>>k;
SearchChild(t,k);
if(k>flag)
cout<<"位置超出長度!"<<endl;
cout<<"9、查詢結點的所有祖先，請輸入結點x：";
cin>>x;
int num;
num=Xancestor(t,x);
if(num==0)
cout<<"結點不存在！"<<endl;
if(num==1)
cout<<"根結點無祖先！"<<endl;
cout<<"10、輸出所有葉子結點路徑（葉→根）："<<endl;
BTNodePath(t);
cout<<"11、輸出所有葉子結點編碼（葉→根）："<<endl;
BTNodebit(t);
}
⑼ 怎樣理解遞歸建立二叉樹演算法
遞歸=傳遞+回歸，即任務的下放和結果的回收。
這個需要自己慢慢體會，其實所有遞歸演算法實質上都是一樣的，理解了就萬變不離其宗了。
create（node
*root）
{
root=new
node；
寫上關於root的信息//初始化root節點
if(root滿足自定義的條件)//自定義一個遞歸的條件，即傳遞和回歸的界限，這是必須的。
{
create(root->lchild);//建左子樹
create(root->rchild);//建右子樹
}
}
總體上來看，建一顆樹，每一次調用creat（）都是只創建一個節點，把剩下的任務下放給create（root->lchild)和create(root->rchild)
，而這兩個也會重復第一個create（root）的做法，實質體現的是任務的不斷下放，當達到最後的回歸的界限的，結果又將不斷回收，對應的是函數的不斷返回，實質是退棧的過程。這個過程其實經歷了一個不斷進棧和不斷出棧的過程，對應的是任務的不斷下放和不斷提交，最後棧空，即告全部任務完成！